데이터베이스 인덱스

인덱스란

인덱스는 데이터의 저장(INSERT, UPDATE, DELETE)의 성능을 희생하고, 그 대신 데이터의 조회(SELECT) 성능을 높이는 기능이다.

 

흔히, 인덱스는 책의 맨 끝에 있는 "찾아보기"로 비유되고, "찾아보기"를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장되어 있는 레코드의 주소에 비유된다.

책의 "찾아보기"는 독자가 원하는 내용을 빠르게 찾을 수 있도록 도와주며, 만약 "찾아보기"가 없다면 독자는 원하는 내용을 찾기 위해 첫 장부터 찾아나가야 하기 때문에 원하는 내용을 찾기까지 오랜 시간이 걸릴 것이다.

 

DBMS에서도 데이터베이스 테이블의 모든 데이터를 조회해서 원하는 결과를 가져오려면 시간이 너무 오래 걸리게 된다.

그래서 책의 "찾아보기" 기능처럼 원하는 데이터를 빠르게 가져올 수 있도록 하기 위해 컬럼(혹은 컬럼들)의 값과 해당 레코드가 저장된 주소를 <key, value> 쌍으로 인덱스를 만들어둔다.

 

또한 책의 "찾아보기"의 특징 중 주목할만 한 부분은 사용자가 원하는 키워드를 빠르게 찾아나갈 수 있도록 가다나 순, 혹은 ABC 순으로 정렬되어 있다는 것이다. DBMS의 인덱스 또한 이와 마찬가지로 컬럼의 값을 주어진 순서로 정렬해서 저장한다.

 

인덱스를 정렬해서 저장했을 때의 Trade-off

데이터가 정렬되어 있다면 새로운 값을 저장할 때마다 항상 정렬해야 하므로 저장하는 과정이 다소 오래 걸릴 수 있다는 단점이 있지만, 반대로 데이터를 정렬해서 저장하기 때문에 원하는 값을 빠르게 찾아올 수 있다는 장점이 있다.

즉, 인덱스는 데이터의 저장 성능을 희생하고, 데이터의 조회 성능을 높이는 기능인 것이라고 할 수 있다.

 

B-Tree 인덱스

데이터베이스에서 가장 일반적으로 사용되는 인덱싱 알고리즘으로, Balanced Tree 구조를 가지는 인덱스이다.

B-Tree는 트리 구조의 최상위에 하나의 루트 노드와 가장 하단에 있는 리프 노드, 루트 노드와 리프 노드 중간에 있는 브랜치 노드로 구성되어 있다.

데이터베이스에서 인덱스와 실제 데이터가 저장된 레코드는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

아래는 B-Tree 인덱스의 각 노드와 데이터 파일의 관계를 표현한 것이다.

B-Tree 인덱스의 구조

인덱스는 테이블의 키 컬럼만 가지고 있기 때문에 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다.

 

위 그림으로 예시를 들어보면, 먼저 위 예시는 세컨더리 인덱스이다.

인덱스를 역할별로 구분해보면 프라이머리 키 인덱스와 세컨더리 인덱스로 구분할 수 있다.
프라이머리 키 인덱스는 각 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스를 의미하며, 세컨더리 인덱스는 프라이머리 키를 제외한 나머지 모든 인덱스를 말한다.
참고로 InnoDB 스토리지 엔진에서 프라이머리 키 인덱스는 리프 노드에 실제 레코드들이 저장되어 있고, 세컨더리 인덱스는 리프 노드에 프라이머리 키 값이 저장되어 있다.

세컨더리 인덱스이기 때문에 실제 레코드를 읽기 위해서는 다음과 같이 리프 노드에 저장되어 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장되어 있는 레코드를 읽을 수 있게 된다.

즉, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 한 번 더 타야한다.

 

B-Tree 인덱스 키 추가 및 삭제

인덱스 키 추가

새로운 키 값이 B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색하고, 저장될 위치가 결정되면 리프 노드에 키 값과 대상 레코드의 주소 정보를 저장한다.

만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되어야 하는데, 이는 상위 브랜치 노드에까지 영향을 미치기 때문에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.

보통 테이블에 레코드를 추가하는 작업 비용을 1이라고 하면, 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 예측한다.

 

인덱스 키 삭제

B-Tree의 키 값 삭제는 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 

삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

 

인덱스 키 변경

B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

InnoDB 스토리지 엔진을 사용하면 인덱스 키의 추가, 삭제 및 변경 작업 모두 체인지 버퍼를 활용하여 바로 디스크에 쓰는 것이 아니라 지연 처리할 수 있다.

 

B-Tree 인덱스 사용에 영향을 미치는 요소

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 

인덱스도 이러한 페이지로 관리되는데, 인덱스의 키 값이 커지면 한 페이지에 담을 수 있는 인덱스 키 값의 개수가 적어지게 되고, 이에 따라 동일한 분량의 SELECT 쿼리를 날리더라도 더 많은 인덱스 페이지를 디스크로부터 읽어야 하기 때문에 그만큼 느려지게 된다.

또한 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미하는데, 이렇게 되면 InnoDB 버퍼 풀에 캐시해둘 수 있는 인덱스 정보가 줄어들게 되어 자연스레 메모리의 효율이 떨어지는 결과를 가져온다.

 

B-Tree의 깊이

B-Tree 인덱스의 깊이는 상당히 중요하지만 직접 제어할 방법은 없다.

B-Tree의 깊이도 인덱스 키 값의 크기와 관련이 있는데, 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지에 담을 수 있는 인덱스 키 값의 개수가 적어지고, 이로 인해 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져 디스크 읽기가 더 많이 필요해지게 된다.

 

선택도(기수성)

인덱스에서 선택도(Selectivity) 혹은 기수성(Cardinality)은 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.

인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고, 동시에 선택도 또한 떨어진다. 

인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

 

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4 ~ 5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다.

즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20 ~ 25%를 넘어서면 인덱스를 이용하지 않고, 풀 테이블 스캔 후 필요한 레코드만 필터링하는 것이 더 효율적이다.

 

Reference

Real MySQL