[데이터베이스] 다단계 인덱스

다단계 인덱스 개념

---

다단계 인덱스

다단계 인덱스란? 

단일 단계 인덱스의 경우 인덱스 자체가 너무 커지면 탐색하는데 너무 오래걸림 
이때 인덱스 엔트리 탐색 시간을 줄이기 위해 단일 단계 인덱스에 대해 다시 인덱스를 정의하는데 이를 다단계 인덱스라고 함
다단계 인덱스는 가장 상위 단계의 인덱스가 한 블록이 들어갈 때 까지 이 과정을 반복하는 것
가장 상위 단계의 인덱스를 마스터 인덱스라 하는데, 한 블록에 불과하기에 주 메모리에 상주할 수 있음

 

다단계 인덱스의 단점 

• 모든 다단계 인덱스의 엔트리들은 순서 화일로 이루어짐 
• 따라서 새로운 인덱스 엔트리를 추가하거나, 기존의 인덱스 엔트리를 삭제하면 과정이 굉장히 복잡해짐
• 하지만 데이터베이스 응용에서 갱신보다 검색 비율이 월등히 높으므로, 모든 DBMS에선 다단계 인덱스로 유지함 

 

다단계 인덱스의 형태 

• 사진처럼 다단계 인덱스는 트리 형태로 구성되며, B+ 트리를 사용함
• 각 노드는 다수의 자식 노드를 가지며, 각 노드는 한개의 디스크 블록을 차지함 
• 일반적으로 한 블록에 자식 노드에 대한 수백 개의 포인터를 저장할 수 있음
• 추가될 인덱스 엔트리들을 위해 각 인덱스 블록에 예비 공간을 남겨둠  

 

Reference 

ORACLE을 기반으로 하는 데이터베이스 배움터, 홍의경 지음, 생능 출판