다단계 인덱스

다단계 인덱스(Multilevel Index)는 인덱스 파일이 너무 커서 한 번에 다루기 어려울 때, 그 인덱스 자체를 하나의 정렬된 파일로 보고 그 위에 다시 인덱스를 쌓아 올린 여러 단계의 인덱스 구조이다.

개요

단일 단계 인덱스도 데이터 파일보다는 훨씬 작지만, 레코드가 많으면 인덱스가 여러 디스크 블록을 차지하고 그 안을 이진 탐색하는 데에도 여러 번의 디스크 접근이 든다. 인덱스는 탐색 키 순서로 정렬된 파일이므로, 그 위에 희소 인덱스를 하나 더 만들 수 있다. 이것을 되풀이해 맨 위 단계가 한 블록에 들어갈 때까지 쌓은 것이 다단계 인덱스이다. Silberschatz 는 아래쪽의 원래 인덱스를 내부 인덱스(inner index), 그 위의 희소 인덱스를 외부 인덱스(outer index)라 부른다.

단계 번호와 마스터 인덱스

Elmasri·Navathe 는 단계를 아래에서부터 센다.

• 1단계(first level, 기저 단계) - 데이터 파일을 직접 가리키는 원래 인덱스이다.
• 2단계 - 1단계 인덱스의 블록마다 엔트리를 하나씩 둔 인덱스이다.
• 맨 위 단계(top level) - 엔트리가 한 블록에 다 들어가는 단계이다. 이 단계를 마스터 인덱스라고 부르며, 보통 주기억장치에 올려 둔다.

따라서 3단계로 이루어진 다단계 인덱스에서 데이터 파일을 가리키는 것은 1단계, 마스터 인덱스는 3단계이다. "마스터 인덱스가 1단계이고 데이터 파일을 가리키는 인덱스가 3단계"라는 설명은 번호를 거꾸로 붙인 것이다. 검색은 번호와 반대로 마스터 인덱스에서 시작해 1단계로 내려온 뒤 데이터 블록에 닿는다.

단계 수와 접근 횟수

한 블록에 들어가는 인덱스 엔트리 수를 팬아웃(fo)이라 하면, 단계가 하나 올라갈 때마다 엔트리 수가 1/fo 로 준다. 1단계 엔트리가 r1 개이면 필요한 단계 수 t 는 log_fo(r1) 을 올림한 값이다. 레코드 하나를 찾는 데 드는 블록 접근은 단계마다 한 번씩 t 번, 여기에 데이터 블록 한 번이 더해진다. 예를 들어 1단계 엔트리가 30,000개이고 팬아웃이 68이면 2단계는 442개, 3단계는 7개로 한 블록에 들어가므로 t = 3 이고, 레코드 하나를 찾는 데 블록 4번을 읽는다.

갱신 문제와 B+ 트리

모든 단계가 정렬된 파일이므로 레코드를 넣거나 뺄 때 여러 단계를 함께 고쳐야 한다. 이 부담을 줄이려고 블록마다 빈자리를 남겨 두고 쪼개고 합치는 동적 다단계 인덱스가 나왔고, 그것이 B 트리와 B+ 트리이다. 실제 DBMS 의 인덱스는 대부분 B+ 트리 형태의 다단계 인덱스이다.

단일 단계 인덱스와 구별하기

구분	단일 단계 인덱스	다단계 인덱스
구조	인덱스 파일 하나	인덱스 위에 인덱스를 쌓은 트리
검색 비용	인덱스 블록 수 b 에 대해 log₂b 번	단계 수 t 번(팬아웃이 밑)
위 단계의 성격	해당 없음	모두 희소 인덱스
갱신	한 파일만 고친다	여러 단계를 고친다(B+ 트리로 완화)

같이 보기

• 희소 인덱스
• 밀집 인덱스
• 클러스터링 인덱스
• B+ 트리
• 색인 순차 파일
• 데이터베이스 인덱스