INDEX의 기본 개념_B*트리 구조와 탐색 방법

B*트리 구조와 탐색 방법

 

 인덱스를 생성할 때 별다른 옵션을 정의하지 않으면 B*트리 구조의 인덱스가 만들어진다. 트리(Tree)는 원하는 데이터를 빠르게 찾기 위해 사용되는 대표적인 자료구조다.

 

B*트리는 균형이 잡혀 있고 근접한 리프 노드가 연결된 구조다.

 

B*트리는 그림과 같이 루트(Root), 브랜치(Branch), 리프(Leaf) 세 가지 유형의 블록으로 구성되어 있다.

 인덱스를 구성하는 블록은 인덱스 블록이라고 한다. 인덱스 블록은 서로 연결되어 있다. 루트 블록은 자 신의 하위 브랜치 블록과 연결되어 있고, 브랜치 블록은 다시 자신의 하위 브랜치 블록과 연결되어 있거 나, 리프 블록과 연결되어 있다. 실제 브랜치 블록은 여러 단계일 수 있고, 리프 블록 밑으로는 다른 인덱 스 블록은 없다.

 

- 루트 블록

  : 최상위에 단 하나만 존재

  : 하위 브랜치 블록의 인덱스 키 값과 주소를 가지고 있다.

- 브랜치 블록

  : 루트와 리프의 중간에 위치, 브랜치는 여러 층이 있을 수 있다.

  : 하위 브랜치의 인덱스 키 값과 주소 또는 하위 리프의 키 값과 주소를 가지고 있다.

- 리프 블록

  : 최하위에만 위치

  : 인덱스 키 값과 데이터의 로우 위치(ROWID)를 가지고 있다.

  : 리프 블록은 인덱스 키 값 순으로 정렬되어 있다.

 

ORD_YMD 컬럼에 대한 B*트리 구조의 인덱스를 자세하게 그려보면 다음과 같다.

B01, B02' 와 같이 이해를 위해 인덱스 블록의 주소 값을 간단하게 표현했다. ORD_YMD 컬럼으로 구성 된 인덱스이므로 모든 인덱스 블록이 ORD_YMD 값을 가지고 있다. 이처럼 인덱스를 구성하는 컬럼을 인덱스 키 값이라고 한다.

 루트 블록과 브랜치 블록은 각자 자신의 하위 인덱스 블록을 찾아갈 수 있는 인덱스 키 값과 주소를 가지 고 있다. 리프 블록은 인덱스 키 값과 실제 데이터가 저장된 로우 주소(ROWID)를 가지고 있다. 그리고 리 프 블록은 인덱스 키 값 순으로 정렬되어 있다.

 

B*트리 구조를 이용해 데이터를 찾아가는 과정은 다음과 같다.

 

(1) 루트 블록

 

다음은 ORD_YMD로 구성된 인덱스의 루트 블록이다. 그림에서 루트 블록은 세 개의 브랜치 블록(B05, B06, B01)을 찾아갈 수 있다. 찾으려는 '20170104'는 빈값보다 크고 '20170601'보다는 작다. 그러므로 브랜치 블록 중에 B05 블록으로 이동해야 한다.

(2) 브랜치 블록

 

 다음 그림은 루트 블록에서 이동한 B05 브랜치 블록이다.

그림에서 B05 블록은 하위에 세 개의 리프 블록(B02, B10, B21)을 가지고 있다. 찾으려는 '20170104'는 B10의 '20170102'보다 크고 B21의 '20170104'보다 작거나 같다. 그러므로 B10으로 이동해야 한다. B10 의 뒷부분에도 '20170104'가 일부 있을 수 있기때문에 B21로는 이동하지 않는다.

(3) 리프 블록 스캔

 

 다음 그림은 B10 블록의 마지막 부분에 '20170104'가 있다. 만약에 브랜치 블록에서 B21로 이동했다면 B10의 마지막에 저장된 '20170104'는 찾지 못한다. B10과 B21 블록은 리프 블록이다. 리프 블록은 인덱 스에서 최하위 블록이므로 더는 하위 블록이 없다.

 인덱스를 검색해서 리프 블록에 도달하면 이제는 리프 블록을 차례대로 스캔해야 한다. 스캔 작업은 찾 으려는 값보다 큰 값을 발견하기 전까지 수행한다. 여기서는 B10 블록의 첫 번째 데이터에서 시작해 B21 블록의 '20170105'를 만날 때까지 스캔이 진행된다.

 이때 리프 블록을 스캔하면서 ROWID를 참고해 실제 테이블에 접근하는 작업을 수행한다.(ROWID는 데 이터가 실제 저장된 주소 값이다.) ROWID를 이용해 데이터를 찾아내는 과정은 실행계획에 'TABLE ACCESS BY INDEX ROWID'라는 오퍼레이션으로 나타난다.