인덱스의 유형과 특징(1. B-Tree index)

 

인덱스는 우리가 테이블에서 특정한 칼럼을 기준으로 정렬을 미리 시켜놓은 목차 같은 개념이다. 그렇기에 인덱스를 지정한 컬럼을 대상으로 검색을 할 때에는 인덱스를 통해서 더 적은 비용으로 데이터를 찾을 수 있기에 성능 향상에 있어서는 인덱스는 필수적이다. 

그렇다면 인덱스는 어떤 종류들이 있을까? 

B-Tree 인덱스, 리버스 키 인덱스, 비트맵 인덱스, 함수기반 인덱스가 있지만 이 글에서는 B-Tree 인덱스에 대해서만 설명을 하겠다.  클러스터 인덱스에 대해서는 https://khdscor.tistory.com/46 를 참고하길 바란다. 

데이터 저장구조와 특징(클러스터링 팩터)

 

B-Tree 인덱스

먼저 가장 기본적이면서도 자주 사용되는 B-Tree 인덱스에 대해서 살펴보겠다. 

B-Tree 인덱스는 관계형 데이터베이스에서 가장 일반적으로 사용되는 인덱스라 할 수 있다. 

B는 Binary냐 이 이론을 처음 만든 사람이냐 여러 설이 있지만 가장 보편적인 것은 Binary에서 따온 것이다. 즉, 균형 있는 나무 인덱스라는 뜻으로 해석할 수 있다.  한번 아래 사진을 봐보자.

 

출처: 새로쓴 대용량 데이터베이스 솔루션

 

 

위 사진처럼 중간부터 좌우로 하나씩 가지가 뻗어나가는 형택이다. 중심이 되는 블록을 Root Block, 중간 블록들을 Branch Block, 잎사귀에 해당하는 리프 블록 Leaf Block으로 이루어져 있다. 깊이가 깊어질수록 데이터의 개수가 기하급수적으로 증가하기 때문에 대량의, 혹은 범위 처리를 할 때 액세스 속도의 차이는 소량을 할 때와 큰 차이가 없을 것이다. 

데이터를 검색할 때 인덱스를 경유하게 될텐데 먼저 루트 블록에서 출발하여 브랜치 블록을 지나 리프 블록을 찾는다. 유일 스캔이면 바로 테이블을 액세스하고 끝나지만 범위 스캔일 때는 리프 블록을 계속해서 스캔한다. 

그렇다면 인덱스가 생성되는 과정은 어떻게 되는 것일까? 아래의 사진을 한번 봐보자.

 

출처: 새로쓴 대용량 데이터베이스 솔루션

 

 

먼저 테이블을 액세스하여 정렬을 수행한다. 정렬된 결과를 인덱스 세그먼트에 저장하고 리프 블록에 로우를 저장한다. 만약 리프 블록이 최대 용량에 도달하면 브랜치 블록을 생성하여 블록 헤더에 기존 블록의 DBA(Data Block Aderss)를 기록하고, 새로 할당된 블록에 대한 시작 값과 그 블록의 DBA로 구성된 브랜치 블록의 로우를 만든다. 이때 생성된 브랜치 블록은 자신이 최상위이므로 루트 블록이 된다. 

위와 같은 방법으로 리프블록과 브랜치 블록에 인덱스 로우를 쌓는다. 그러다 브랜치 블록에 용량이 꽉 차면 새로운 브랜치 블록을 할당하고 처음과 같이 추가된 브랜치 블록의 최초 리프 블록 정보는 헤더에만 기록된다. 

브랜치 블록이 새로 생겨났으므로 이들의 정보를 저장하기 위한 상위 레벨의 브랜칯 블록이 필요한데 이 블록이 최상위 레벨이므로 루트 블록이 된다. 이때도 앞에서와 비슷하게 최초의 브랜치 블록 정보는 루트 블록의 헤더에만 기록된다. 

위와 같은 과정이 계속 반복되며 인덱스가 완성되는 것이다. 

 

이와 같은 방식이기에 하나의 인덱스 블록에 많은 로우가 저장될수록 리프 블록은 감소하고 브랜치 블록의 증가를 둔화시켜주며 브랜치 블록의 깊이도 같이 감소한다. 그렇기에 인덱스 블록에 보다 많은 로우를 담을 수 있는데 첫 번째 방식으로는 가능하면 최대한 인덱스 컬럼의 수를 줄인다.

두 번째는 키 압축(Key compression)을 활용하는 방식이다. 유일 인덱스가 아닌 경우 대부분 키값이 중복되어 있다. 특히 두 개 이상의 컬럼을 기준으로 하는 결합 인덱스에서는 중복이 더 발생할 수밖에 없다. 만약 이러한 경우에는 한 블록에 똑같은 로우가 여러 개 발생할 것이다. 이러한 상황은 압축을 통해서 해결할 수 있다. 아래의 예시처럼 중복이 발생하는 컬럼의 순번을 지정함으로써 해당 컬럼까지를 압축할 수 있다. 

 

CREATE INDEX ord_customer_idx
ON orders (customer_id, sales_id)
COMPRESS 1;

 

 

이렇게 인덱스의 생성에 대해 살펴보았다. 그렇다면 이미 인덱스가 만들어진 상태에서 데이터의 삽입이 일어나면 어떻게 되는 것일까? 만약 각 리프 노드의 처음이나 마지막 순서에 해당하는 로우가 삽입된다면 새로운 리프노드가 생성되며 삽입되는 로우만을 가지게 된다. 하지만 만약 중간 순서에 해당하는 로우가 삽입되면 2/3만 채우도록 하면서 분할이 일어나게 된다. 그리고 새로 입력되는 로우가 정렬상 새로 만든 리프 노드나 분할된 리프 노드에 위치하게 된다면 새로운 리프 노드가 생성되거나 분할이 일어나지 않을 수도 있다. 하지만 계속해서 삽입이 일어나면 결국 용량을 꽉 채우지 않은 리프 노드가 매우 많아져서 저장공간이 크게 늘어날 수 있다. 이런 문제를 해결하기 위해서는 인덱스를 '재생성'하는 방법밖에 없다. 그렇기에 정기적으로 인덱스를 재생성해주는 것이 중요하다. 

 

그렇다면 데이터의 삭제나 갱신할 때에는 어떨까? 로우를 삭제하면 테이블의 로우는 삭제되지만 인덱스의 로우는 삭제되지 않고 삭제됬다는 표시만 추가된다. 그렇기에 이는 저장공간의 낭비뿐만 아니라 스캔해야 할 블록이 증가하는 것이다. 

갱신할 때에는 삭제 후 삽입이 발생한다. 인덱스 로우가 정렬되어 저장되어야 하므로 어쩔 수 없이 발생하는 현상이다. 그렇기에 가능하면 인덱스 컬럼은 수정이나 삭제가 덜 일어나는 컬럼으로 선택하는 것이 좋다. 

이처럼 인덱스는 삽입, 수정, 삭제시 저장공간을 과도하게 소비하게 되므로 DML이 많이 일어나는 테이블은 정기적으로 재생성할 필요가 있다. 

 

참고

새로쓴 대용랑 데이터베이스 솔루션 - 이화식