[오라클 DB] 다단계 인덱스

 

다단계 인덱스

 

인덱스 자체가 클 경우에는 인덱스를 탐색하는 시간조차 오래 걸릴 수 있다. ( 데이터 파일에 대한 인덱스 파일이 여타 다른 데이터 파일만큼 큰 경우 )

이러한 경우 인덱스 엔트리를 탐색하는 시간을 줄이기 위해 단일 단계 인덱스를 디스크 상의 하나의 순서 파일로 간주하고, 단일 단계 인덱스에 대해 다시 인덱스를 정의할 수 있다.

 

다단계 인덱스는 가장 상위 단계의 모든 인덱스 엔트리들이 한 블록에 들어갈 수 있을 때까지 이런 과정을 반복하며, 최종 과정을 거쳐 가장 상위 단계의 인덱스가 만들어지면 해당 인덱스를 마스터 인덱스(Master Index)라고 부른다.

마스터 인덱스는 한 블록으로 이루어지기 때문에 주기억 장치에 상주할 수 있다.

 

대부분의 다단계 인덱스는 B+트리를 사용한다.

 

다단계 인덱스 예시

 

위 예시에서 볼 수 있듯, 데이터 파일에 대한 인덱스 파일 또한 여타 다른 데이터 파일처럼 무수히 클 경우, 해당 인덱스 파일에 대한 또 다른 인덱스 파일을 계속 생성하여 한 블록 내에 모든 인덱스 엔트리가 들어갈 수 있을 때까지 인덱스 파일을 생성한다.

 

다단계 인덱스 성능 예시

 

가정
파일에 레코드가 10,000,000개 있고, 각 레코드의 길이가 200바이트이고, 블록 크기가 4,096 바이트이면 블록킹 인수는 ⌊ 4,096 / 200 ⌋ = 20인 파일을 가정해보자.

 

이 가정 값들은 이전 포스팅 글의 히프 파일 성능 예시 ~ 보조 인덱스 성능 예시의 값들과 같다.

 

- 1단계 인덱스의 블록 수는 2,942
- 2단계 인덱스의 블록 수는 ⌈ 2,942 / 170 ⌉ = 18
- 3단계 인덱스의 블록 수는 ⌈ 18 / 170 ⌉ = 1 -> 주기억 장치에 상주할 수 있음

원하는 레코드를 탐색할 때, 3단계 인덱스는 주기억 장치에 상주하므로 디스크 접근이 필요 없고, 2단계 인덱스를 구성하는 18개 블록 중에서 한 블록, 2,942개의 1단계 인덱스 블록 중에서 한 블록, 데이터 파일의 500,000개의 블록 중에서 한 블록 등 총 3번의 디스크 접근만 하면 된다.
따라서 탐색 시간은 3 X 10ms = 30ms이다.

기본 인덱스를 단일 단계 인덱스로 구성한 경우의 130ms와 비교하면 인덱스를 탐색하는 시간이 1/4.3 정도밖에 안 걸린다.