[파일구조] - B 트리

1. 개요

B 트리는 대용량의 파일을 효율적으로 관리하기 위한 자료구조로써, 산업 분야에서 데이터베이스 시스템에 전반적으로 사용되고 있는 de facto 표준이다. 가끔 이진 탐색 트리(binary search tree)와 B 트리를 혼동하는 경우가 있는데, 두 종류의 트리는 완전히 다른 구조와 연산을 갖고 있다. 

인덱스를 이용하는 파일 시스템에서 가장 큰 문제는 '어떻게 하면 메모리에 올릴 수 없을 정도로 큰 용량의 인덱스에 효율적으로 접근할 것인가?'이다. 파일 시스템에서 인덱스를 이용하는 가장 근본적인 이유는 파일 전체를 이진 탐색(binary search)하여 레코드를 찾는 것보다 인덱스를 이용하는 것이 더 빠르기 때문이다. 따라서, B 트리는 아래의 두 가지 요구사항을 반드시 충족해야 한다.

• 인덱스를 검색하여 레코드에 접근하는 것은 반드시 데이터 파일에서 이진 탐색을 이용하여 레코드를 찾는 것보다 빨라야 한다.
• Insertion, deletion 연산을 효율적이고 빠르게 수행할 수 있어야 한다.

2. B 트리의 특징

B 트리는 하나의 노드에 여러개의 데이터를 저장할 수 있으며, 하나의 노드에 최대로 저장할 수 있는 데이터의 수를 order라고 한다. 만약 어떠한 B 트리의 order가 $m$일 때, B 트리는 다음과 같은 속성을 갖는다.

• 각 노드는 최대 $m$개의 자식을 가질 수 있다.
• Root node와 leaf node를 제외한 모든 노드는 반드시 $[m/2]$개의 자식 노드를 가져야 한다.
• 높이가 1 이상인 B 트리의 root node는 반드시 두 개 이상의 자식 노드를 가져야 한다.
• 모든 leaf node는 같은 레벨에 위치해야 한다. 즉, leaf node와 root node의 거리는 모두 같아야 한다.

3. B 트리의 생성

B 트리는 기존의 트리와는 다르게 트리의 가장 아래쪽인 leaf node에서 root node의 방향으로 트리를 생성한다. 만약 다음과 같은 순서로 문자가 입력된다고 하면 B 트리는 아래와 같이 생성된다.

1) C, S, D, T 입력

2) A 입력

3) M, P, I 입력

4) B, W, N, G, U 입력

5) R 입력

6) K, E 입력

7) H, O, L, J, Y, Q, Z 입력

8) F 입력

9) X, V 입력