[Oracle] 오라클 인덱스 구조 - B*Tree Index

B*Tree Index (B: Balanced)

- 인덱스 Root에서  Leaf Block까지 어떤 값으로 탐색하더라도 읽는 Block 수가 동일

  (Root로 부터 모든 Leaf Block 까지의 높이가 동일)

 

위 그림을 보면서 처음에 Root Block과 Branch Block에 있는 KEY 값 때문에 헷갈렸는데

저기에 나타난 KI나 BER, FO, JONES 등등의 값은 테이블 레코드 값이라기 보다는 범위를 의미한다.

다시 말해 KI는 > KI 를 의미하고 BER는 > BER 를 의미한다.

 

Root Block & Branch Block

- 저장 엔트리: {KEY:DBA(하위 노드의 Data Block Address)}

* 여기에 저장된 KEY 값은 테이블 레코드의 KEY 값이 아닌 하위 노드의 범위를 의미
* 레코드의 수 = 하위 레벨 Block 수
* 데이터가 많아질수록 Depth가 늘어남
* 단, lmc에는 KEY 값이 없음
※ lmc (LeftMostChild): 키 값을 가진 첫번째 엔트리보다 작은 값, 다른 엔트리와 별도 장소에 저장

Leaf Block

- 저장 엔트리: {KEY:RowID(DBA+LOC)}

* 여기에 저장된 KEY 값은 테이블 레코드의 KEY 값을 의미(ORDER BY KEY, RowID)
* Leaf Node의 인덱스 레코드와 Table 레코드는 1:1 관계
* 각각의 Leaf Block은 이전과 다음 Block의 Address를 가지고 있음

 

인덱스 생성 과정

- PGA에서 인덱스를 정렬하다 공간이 부족할 경우 Temp Segment를 생성하여 인덱스를 정렬

  (Temp Segment를 위해 필요한 공간은 인덱스 컬럼의 현재 정렬 상태에 따라 달라지는데 최악은 인덱스 컬럼이 완벽하게 내림차순 되어있는 경우임)

- 정렬된 데이터를 차례대로 Leaf Block에 채움
  (단, Block을 다 채우지 않고 PCTFREE 설정값만큼 비워둠)

- Branch Block 및 Root Block 생성

* 인덱스의 궁극적인 목적은 빠른 속도이므로 인덱스의 Depth는 작을수록 좋음
  (인덱스 컬럼 수가 적을수록, Block의 크기가 클수록, PCTFREE 설정값이 작을수록 하나의 인덱스 Block에 많은 인덱스 Row가 저장될 수 있음)