인덱스 Index - (1)

1. 디스크 읽기 방식

컴퓨터의 CPU나 Memory처럼 전기적 특성을 가진 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만 디스크 같은 기계식 장치의 성능은 상당히 제한적으로 발전했다. (e.g. HDD, Hard Disk Drive) 최근에는 SSD가 많이 활용되고 있지만 여전히 데이터 저장 매체는 컴퓨터에서 가장 느린 부분이라는 사실에는 변함이 없다. 그래서 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O (Input / Output)를 줄이느냐가 관건일 때가 상당히 많다. 

 

2. 랜덤 (Random) I/O, 순차 (Sequential) I/O

I/O라는 표현은 하드 디스크 드라이브의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미하는데 랜덤과 순차의 차이점이 있다. 
순차 I/O는 헤더가 한번 이동 된 후에 여러 데이터를 순차적으로 처리하고 랜덤 I/O는 헤더가 여러번 움직여서 여러 데이터를 처리하는 것을 의미한다. 그래서 같은 데이터 크기라면 순차 I/O가 랜덤 I/O보다 속도가 빠르다. 즉, 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정된다고 볼 수 있다. 데이터 베이스의 대부분의 작업은 이러한 작은 데이터를 빈번히 읽고 쓰기 때문에 MySQL 서버에는 그룹 커밋이나 바이너리 로그 버퍼 또는 InnoDB 로그 버퍼 등의 기능이 내장돼 있다. SSD는 랜덤 I/O와 순차 I/O의 차이가 없을 것으로 예측하지만 실제로는 랜덤 I/O의 성능이 떨어진다.

사실 쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 그다지 많지 않다. 일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적이라고 할 수 있다. 즉 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다.

참고로 인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하며 풀 테이블 스캔은 순차 I/O를 사용한다. 

 

3. 인덱스란?

보통 책의 맨 끝장에 있는 '찾아보기'(색인)을 인덱스를 이해시킬 때 많이 사용한다. '찾아보기'가 인덱스에 비유된다면 책의 내용은 데이터에 해당한다고 볼 수 있다. 책의 '찾아보기'를 통해 알아낸 페이지 번호는 데이터 파일에 저장된 레코드의 주소에 비유될 것이다. 그래서 칼럼 혹은 칼럼들의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 저장해 두는 것이 인덱스이다. 책의 '찾아보기'와 DBMS 인덱스의 공통점 가운데 중요한 것이 바로 정렬이다. 데이터를 최대한 빠르게 찾을 수 있게 'ㄱ', 'ㄴ', 'ㄷ', ... 과 같은 순서로 미리 정렬해서 보관한다. 그래서 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾을 수 있다. 즉 INSERT, UPDATE, DELETE 문장의 처리가 느려지지만 SELECT 문장은 빠르게 처리할 수 있다. 
여기서도 알 수 있듯이 테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 수정(INSERT, UPDATE, DELETE) 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하느냐에 따라 결정해야 한다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 무조건 인덱스로 생성하게 되면 데이터 수정 능력이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과만 불러올 수 있다.

 

4. B-Tree (Balanced Tree) 인덱스

B-Tree 인덱스 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘으로서 상당히 오래전에 도입된 알고리즘이며 그만큼 최적화가 잘 되어 있다. B-Tree 인덱스는 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다. 전문 검색과 같은 특수한 요건이 아닌 경우 대부분 B-Tree를 사용한다.

그림(1) B-Tree 인덱스의 구조

B-Tree는 트리 구조의 최상위에 하나의 루트 노드(Root Node)가 존재하고 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 리프 노드(Leaf Node)라고 하며 중간에 위치한 노드는 브랜치 노드(Branch Node)라고 한다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

그림(1)에서와 같이 인덱스의 키 값은 모두 정렬돼 있지만 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다. 많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않다. 만약 테이블의 레코드를 전혀 삭제하거나 변경하지 않고 INSERT만 수행한다면 맞을 수도 있다. 하지만 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT된 순서로 저장되는 것은 아니다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장된다. 

그림(2) InnoDB의 B-Tree의 리프 노드와 테이블 데이터 레코드

InnoDB 스토리지 엔진을 사용하는 테이블에서는 프라이머리 키(PK)가 ROWID의 역할을 한다. PK를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다. 그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 못해서 성능이 떨어질 것처럼 보이지만 장단점을 가지고 있다. (인덱스 리프 노드에서 데이터 파일 사이에 루트, 브랜치, 리프 노드 구조가 또 존재한다.)

인덱스 키 Babette를 찾으려고 할 때 프라이머리 키값이 10128인 것을 인덱스 리프 노드(가장 왼쪽)에서 확인을 하였다. 데이터 파일 루트 노드(분홍색)에서 인덱스 키값 11043은 10128보다 큰 값이기 때문에 인덱스 키 10057의 자식 노드 2를 확인하였다. 데이터 파일 브랜치 노드 (노란색)에서 2번 페이지를 찾았고 인덱스 키값 10418은 10128보다 큰 값이기 때문에 인덱스 키 10057의 자식 노드 4를 확인하였다. 데이터 파일 리프 노드(가장 오른쪽)에서 4번 페이지를 찾았고 4번 페이지에서 PK값이 10128을 찾았다.