Indexing(2)

3. $B^{+}$-tree index 파일

index 순차 파일 구조의 주요 단점은 파일이 커질수록 index를 찾아서 그 데이터를 연속으로 스캔하는 성능이 감소하는 것이다.

$B^{+}$-tree index 구조는 데이터의 삽입과 삭제에도 불구하고 성능을 유지하는 몇몇 index 구조 중 가장 널리 사용된다. $B^{+}$-tree index는 트리의 루트에서 단말 노드까지 모든 경로의 길이가 같은 균형 트리(balanced tree) 형태이다.

1) $B^{+}$-tree의 구조

$B^{+}$-tree index는 다단계 index이지만 다단계 index 순차 파일과는 다른 구조를 가진다. 그림 14.7은 $B^{+}$-tree의 전형적인 노드를 보여준다.

n-1개의 search key 값 $K_{1}, K_{2},..,K_{n-1}$과 n개의 포인터 $P_{1}, P_{2},..,P_{n}$을 포함한다. 노드 안의 search key 값은 정렬된 순서로 유지된다.

단말 노드의 구조

그림 14.8은 instructor 파일의 $B^{+}$-tree에서의 단말 노드를 보여준다. 이때 n은 4이고 search key는 name 이다.

각 단말 노드는 n-1개까지의 값을 가질 수 있는데 단말 노드는 적어도 $\left \lceil (n - 1)/2 \right \rceil$개의 값을 포함해야 한다. 본 예제의 $B^{+}$-tree에서 n=4이기 때문에 각 단말 노드는 적어도 2개, 많아도 3개의 값을 가진다.

$L_{i}$와 $L_{j}$가 단말 노드이고 i < j라면 $L_{i}$에 있는 모든 search key 값은 $L_{j}$에 있는 모든 search key 값보다 작거나 같다. 만약 $B^{+}$-tree가 밀집 index로 사용된다면, 단말 노드에 모든 search key 값이 나타나야 한다.

각 단말 노드는 search key 값을 기초로 선형 순서로 되어 있다. 그래서 단말 노드를 search key 순서로 서로 연결하기 위해 $P_{n}$을 사용한다. 이 순서는 파일의 연속적인 처리를 능률적으로 할 수 있게 해준다.

비단말 노드의 구조

비단말 노드는 단말 노드 상에서 다단계 희소 index를 형성한다. 비단말 노드 구조는 모든 포인터가 트리 노드에 대한 포인터인 것을 제외하고는 단말 노드의 구조와 동일하다. 비단말 노드는 n개까지의 포인터를 가질 수 있고, 적어도 $\left \lceil n/2 \right \rceil$개의 포인터를 갖고 있어야 한다.

m개의 포인터를 포함하고 있는 노드를 생각해보자. i=2,3,...m-1일 때 포인터 $P_{i}$는 $K_{i}$보다는 작고 $K_{i-1}$보다는 크거나 같은 search key 값을 포함하는 하위 트리를 가리킨다. 예를 들어 아래의 예시에서 Einstein 다음 포인터가 Einstein보다는 크거나 같고 Gold 보다는 작은 search key 값을 포함하는 하위 트리를 가리키는 것이다.

루트 노드는 다른 비단말 노드와 달리 $\left \lceil n/2 \right \rceil$개 보다 더 적은 포인터를 가질 수 있다. 그러나 하나의 노드로 구성된 트리가 아닌 경우 루트 노드는 적어도 두 개의 포인터를 갖고 있어야 한다.

그림 14.9는 instructor 파일(n=4)의 완전 $B^{+}$-tree를 보여준다. 그림 14.10은 n=6인 instructor 파일의 다른 $B^{+}$-tree를 보여준다. n=4인 트리보다 트리의 높이가 작은 것을 확인할 수 있다.

2) $B^{+}$-tree 상에서의 질의

search key 값 V를 가지는 모든 레코드를 찾기 원한다고 가정하자. 직관적으로 이 과정은 트리의 루트에서부터 시작해 트리 안에 존재하는 특정 값을 포함하는 단말 노드에 도달할 때까지 아래 방향으로 탐색한다. 그 과정은 다음과 같다.

1. 현재의 노드를 조사하여 V보다 큰 search key $K_{i}$를 만족시키는 가장 작은 i를 찾는다.
   a. i를 찾은 경우: $K_{i}$가 V와 같다면 $P_{i+1}$가 다음 노드를 가리킨다. $K_{i}$가 V보다 크다면, $P_{i}$가 다음 노드를 가리킨다.
   b. i를 찾지 못한 경우: V > $K_{m-1}$이며 이때 $P_{m}$이 다음 노를 가리키게 된다.
2. 단말 노드에 도달할 때까지 1~2번 과정을 반복하면서 트리의 아래를 탐색한다.
3. 단말 노드에 도달했을 때는 다음 과정을 따른다.
   a. 단말 노드에서 search key 값이 V와 같으며 $K_{i}$가 그 첫 번째 값인 경우, 포인터 $P_{i}$가 search key $K_{i}$를 가진 레코드를 가리킨다.
   b. V를 가지는 search key가 단말 노드에서 발견되지 않으면, 릴레이션의 V의 key 값을 가진 레코드가 없는 것이다.
4. search key 값 V를 가진 레코드의 개수에 따라 그 이후 동작이 달라진다.
   a. 레코드가 하나인 경우: 해당 레코드를 반환하고 종료
   b. 레코드가 여러 개인 경우: 노드 L의 남아있는 key로 움직인다. 만약 노드 L이 V보다 더 큰 search key 값을 적어도 하나 포함한다면 더 이상 V와 일치하는 레코드들은 없게 된다. 그렇지 않은 경우엔 $P_{n}$이 가리키는 다음 단말 노드로 이동해야 한다. 이런 식으로 V보다 큰 search key 값을 찾을 때까지 단말 노드 사이를 이동하며 탐색을 이어가야 한다.

$B^{+}$-tree vs balanced binary tree

• $B^{+}$-tree
  노드가 적게 액세스되어야 하므로 일반적으로 하나의 노드는 디스크 블록과 동일한 크기로 만들어진다. 보통 디스크 블록의 크기는 4KB이다. search key의 크기가 32byte이고 디스크 포인터의 크기가 8byte라면 n은 약 100이 된다. n이 100이고, 파일에 1,000,000개의 search key 값이 있다면 검색하는 데 단지 $\left \lceil log_{\left \lceil n/2 \right \rceil}(N) \right \rceil$, 즉 4개의 노드가 액세스 된다. 그래서 검색하기 위해 기껏해야 4개의 블록만 디스크로부터 읽어오면 된다. 트리의 루트 노드는 보통 많이 액세스 되어 buffer에 있을 가능성이 있으므로 실제로는 3개 혹은 더 적은 블록만 읽어도 된다.

• balanced binary tree
  $B^{+}$-tree와 가장 큰 차이점은 한 노드의 크기와 트리의 높이이다. 이진 트리는 각 노드가 작고 많아야 2개의 포인터를 갖고 있다. 그래서 $B^{+}$-tree는 굵고 짧은 반면, 이진트리는 가늘고 길다. 균형 이진 트리는 검색을 위한 경로의 길이가 $\left \lceil log_{2}(N) \right \rceil$일 수 있다. 레코드의 개수가 1,000,000개일 때 균형 이진 트리는 약 20개의 노드를 액세스한다. 각 노드가 다른 블록에 있다면 검색을 처리하기 위해 20개의 블록을 읽는다.

3) $B^{+}$-tree 갱신의 복잡도

$B^{+}$-tree상에서 삽입과 삭제 연산이 복잡할지라도 상대적으로 적은 디스크 I/O 연산을 요구한다. 이는 디스크 I/O 연산이 매우 비싸기 때문에 상당한 이익이다.

삽입이나 삭제의 최악의 경우에 요구되는 입력 연산의 수는 $\left \lceil log_{\left \lceil n/2 \right \rceil}(N) \right \rceil$에 비례한다. 이때 n은 한 노드 안에 있는 포인터의 최대 개수이고, N은 index된 파일에 있는 레코드의 개수이다.

참고

Database System Concepts 11장