인덱스의 중요성

MySQL의 인덱스는 기본적으로 B+트리라는 데이터 구조다. B+ 트리는 B트리에서 파생된 데이터 구조다.

이분트리와 B트리 비교해보기

이분트리는 노드가 반드시 하나로 정해져 있지만, B트리는 m=5처럼 개수가 정해진다. B트리는 이 수를 조정함으로써 (4) 크기를 4KB등으로 할 수 있다. 즉, 각 노드의 크기를 적당한 사이즈로 정할 수 있다. 이 점이 B트리의 장점이다.

여기서 노드의 크기라는 것이 3장에서 설명한 디스크의 페이좌 매우 밀접한 관계가 있다. (4)의 노드 1개로 디스크의 1블록만큼을 할당하면, B트리로 디스크 상에 저장했을 때 (5)를 1블록, 6을 1블록과 같이 각 노드를 딱 1블록만큼으로 해서 저장할 수 있다.

트리에서 검색을 할 때는 노드에서 노드로 트리를 순회한다. B트리의 경우, 각 노드를 블록에 모아서 저장되도록 구성할 수 있으므로 디스크 Seek 발생횟수를 노드를 찾아갈 때만으로 최소화할 수 있다. OS가 한 번에 읽어내서 메모리에 캐싱하게 되므로 같은 노드 내의 데이터는 디스크 Seek 없이 탐색할 수 있다.

한편, 이분트리는 특정 노드를 모아서 1블록에 저장하는 등의 작업이 어렵다. 그러므로 이분트리를 디스크 상에 저장하는데 있어서 디스크 구조에 최적화할 수가 없다. 그 결과, 디스크 상의 이분트리를 검색하려고 하면 여기저기 블록에 분산되어 있는 데이터를 읽어야 하므로 디스크 Seek 횟수가 많아지게 된다.

인덱스의 효과의 예

데이터 건수가 1,000건 정도라면 오히려 트리를 먼저 순회하는 오버헤드가 더 커서 그냥 처음부터 찾아 내려가는 편이 더 빠른 경우가 많다. 그러나 크기가 커지면 인덱스 없이는 시작부터 엑세스할 수 없는 상황이 되므로 실로 인덱스는 중요하다. 한편, MySQL은 레코드 총 건수를 보고 인덱스를 사용하지 않는 편이 더 빠르다라고 판단되면, 사용하지 않는 최적화 작업을 내부에서 어느 정도 수행해준다.

[보충] 인덱스의 작용

MySQL 인덱스 사양에는 약간의 특성이 있는데, 인덱스를 걸어놓고 있는 칼럼을 대상으로 한 쿼리라도 던지는 SQL에 따라서는 그것이 사용되거나 사용되지 않기도 한다.

• 기본적으로 인덱스가 사용되는 것은 ...
  -> where, order by, group by의 조건에 의해 지정된 칼럼

• 인덱스로서 작용하는 것은 ...
  -> 명시적으로 추가한 인덱스
  -> Primary Key, UNIQUE 제약

• MySQL 인덱스의 함정
  -> 복수 칼럼에 동시에 인덱스를 태우고자 할 경우는 복합 인덱스를 사용해야만 한다.

문제가 바로 복수의 칼럼이 인덱스 작용의 대상이 되는 경우다.

select *
from entry
where url like 'http://d.hatena.ne.jp/%'
order by timestamp

쿼리가 있다고 하자. url과 timestamp 각각에 인덱스를 설정했다고 하면 이 경우에 어떻게 될까? url과 timestamp의 인덱스 양쪽이 모두 사용되어 url 인덱스에서 고속으로 url을 검색하고, 범위가 좁혀진 레코드를 timestamp 인덱스에서 고속으로 정렬해주는 걸 기대했지만 그렇게 되지는 않는다. 이 경우는 어느 한쪽의 인덱스만 사용된다.

MySQL은 한 번의 쿼리에서 하나의 인덱스만 사용한다는 특성을 갖고 있는 것이 그 원인이다. 위 쿼리에서 url과 timestamp 양쪽의 인덱스를 태우고자 할 경우는 (url, timestamp)를 쌍으로 한 복합 인덱스를 설정해둘 필요가 있다.

인덱스가 작용하는지 확인하는 법

explain select url from entry where eid = 9615899;

possible_keys에 뭐를 대상으로 인덱스가 걸렸는지 확인할 수 있다. 인덱스의 작용법이라는 의미에서 Extra 열도 중요하다.

explain 명령에서 속도에 유의하라

인덱스의 작용법이라는 의미에서는 Extra 열도 중요하다. Extra에는 Using where 이외에 Using filesort나 Using temporary와 같은 항목이 나올 경우가 있다. 각각 레코드 정렬에 외부 정렬(외부 파일을 이용한 정렬)이나 임시 테이블이 필요하다는 의미다. 기본적으로는 Using filesort나 Using temporary가 나오는 것이 그다지 틀이 좋은 쿼리가 아니다.