[데이터베이스] 저장 장치 관리 및 인덱싱: 인덱싱

 

$B^{+}$-트리 인덱스

---

 

$B^{+}$-트리는 다음과 같은 속성을 만족하는 루트 트리(rooted tree)이다.

 

트리의 루트 노드(root node)에서 단말 노드(leaf node)까지 모든 경로(path)의 길이가 같다.

(균형 트리(balanced tree)이다.)

 

루트 노드나 단말 노드가 아닌 각 노드는 $\left \lceil n/2 \right \rceil$에서 n 사이의 자식(children)을 가진다.

 

단말 노드는 $\left \lceil (n - 1)/2 \right \rceil$에서 (n - 1)사이의 자식을 가진다.

 

만약 루트 노드가 단말 노드가 아니면, 루트 노드는 2에서 n사이의 자식을 가진다.

 

만약 루트 노드가 단말 노드이면, 루트 노드는 0에서 (n-1)사이의 자식을 가진다.

 

 

 

 

- $B^{+}$-트리의 구조

 

Database System Concepts by Silbershatz A. & Korth H. F. & Sudarshan S.

 

$K_{i}$는 검색 키 값(search-key value)이다.

 

$P_{i}$는 단말 노드가 아닌 하위 노드의 포인터 혹은 단말 노드의 레코드 또는 레코드 버킷에 대한 포인터이다.

 

노드 안의 검색 키 값은 정렬된 순서로 유지된다. ($K_{1} < K_{2} < K_{3} < ... < K_{n-1}$)

 

 

 

단말 노드의 특성은 다음과 같다.

 

i = 1, 2, ... n - 1일 때, 포인터 $P_{i}$는 검색 키 값 $K_{i}$를 가지는 파일 레코드를 가리킨다.

 

$L_{i}$, $L_{j}$가 단말 노드이고, i < j이면, $L_{i}$의 모든 검색 키 값은 $L_{j}$의 모든 검색 키 값보다 작거나 같아야 한다.

 

포인터 $P_{n}$은 단말 노드를 검색 키 순서로 서로 연결하기 위해서 검색 키 순서에 따라 다음 단말 노드를 가리키는 포인터이다.

 

 

 

비단말 노드의 특성은 다음과 같다.

 

$B^{+}$-트리에서 비단말 노드는 다계층 희소 인덱스(multi-level sparse index)를 형성한다.

(희소 인덱스: 레코드 그룹 혹은 데이터 블록에 대해 하나의 엔트리가 만들어지는 인덱스)

 

m개의 포인터를 가지는 비단말 노드에서,

 

1. 포인터 $P_{1}$의 서브 트리의 모든 검색 키는 $K_{1}$ 보다 작은 값을 가진다.

 

2. 2  ≤ i ≤ n - 1에서, 포인터 $P_{i}$의 서브 트리의 모든 검색 키는 $K_{i-1}$보다 크거나 같고, $K_{i}$보다 작은 값을 가진다.

 

3. 포인터 $P_{n}$의 서브 트리의 모든 검색 키는 $K_{n-1}$ 보다 크거나 같은 값을 가진다.

 

 

 

예시) 

 

Database System Concepts by Silbershatz A. &amp; Korth H. F. &amp; Sudarshan S.

 

 

단말 노드는 3개에서 5개 사이의 자식을 가질 수 있다. ($\left \lceil (n - 1)/2 \right \rceil$ ~ (n - 1))

 

루트 노드가 아닌 비단말 노드는 3개에서 6개 사이의 자식을 가질 수 있다.($\left \lceil n/2 \right \rceil$ ~ n)

 

루트 노드는 적어도 두 개 이상의 자식을 가져야 한다.

 

 

 

 

 

 

비고유 검색 키(Non-Unique Search Key)

---

 

 

- 비고유 검색 키를 지원하기 위한 두 가지 대안

 

 

1. 별도의 블록에 버킷을 유지하는 방법 (bad idea)

 

버킷은 검색 키 값과 포인터로 구성된 튜플의 리스트로 구성되어 있다.

 

긴 리스트를 다루기 위한 추가 코드가 필요하다.

 

특정 검색 키 값이 여러 번 발생하고, 해당 검색 키 값을 가지는 레코드 중 하나가 삭제될 때, 해당하는 튜플을 삭제는 비용이 많이 든다.

 

공간 오버헤드가 적고, query에 추가 비용이 발생하지 않는다.

 

 

 

2. record-identifier를 추가해서 검색 키를 고유하게 만드는 방법 (widely used)

 

추가 공간 오버헤드가 발생한다.

 

레코드 추가 및 삭제 코드가 비교적 단순하다.