B-트리, B+트리, B*트리
데이터베이스 및 파일 시스템에서 데이터 검색을 최적화하기 위해 자주 사용되는 다양한 균형 트리(Balanced Tree) 구조가 있다. 이 글에서는 B-트리, B+트리, B*트리의 개념, 구조, 특성, 그리고 각 트리의 장단점을 자세히 설명한다. 또한 이 외에도 사용되는 다른 균형 트리에 대해서도 간략히 언급한다.
B-트리 (B-Tree)
개념
B-트리는 다진 트리(Multi-way Tree)로, 데이터 검색, 삽입, 삭제 작업을 효율적으로 수행할 수 있도록 설계된 균형 트리이다. B-트리는 디스크 I/O 효율성을 높이기 위해 자주 사용된다.
구조
- 각 노드는 최대
m-1개의 키와m개의 자식을 가질 수 있다 (m은 트리의 차수). - 각 노드는 최소
⌈m/2⌉개의 자식을 가져야 한다. - 모든 리프 노드는 같은 깊이에 있다.
- 키들은 노드 내에서 오름차순으로 정렬된다.
장단점
- 장점: 검색, 삽입, 삭제 작업의 시간 복잡도가 O(log n)으로 일정하다.
- 단점: 모든 노드에 키와 자식 포인터를 저장하므로 공간 효율이 낮을 수 있다.
B+트리 (B+Tree)
개념
B+트리는 B-트리의 변형으로, 데이터 검색과 범위 검색에 더욱 최적화된 트리 구조이다. 리프 노드 간에 연결 리스트 형태로 연결되어 있어 순차적 데이터 접근이 용이하다.
구조
- 내부 노드는 오직 키와 자식 포인터만 포함하며, 실제 데이터는 리프 노드에만 저장된다.
- 리프 노드에는 모든 키와 데이터가 저장되며, 리프 노드 간에는 연결 리스트 형태로 연결되어 있다.
- 모든 리프 노드는 같은 깊이에 있다.
장단점
- 장점: 범위 검색과 순차 접근이 매우 효율적이다.
- 단점: 내부 노드와 리프 노드가 분리되어 있어 삽입, 삭제 시 오버헤드가 발생할 수 있다.
B트리 (BTree)
개념
B*트리는 B+트리의 변형으로, 공간 활용을 최적화하고 노드 분할 빈도를 줄이기 위해 고안된 트리 구조이다.
구조
- B+트리와 유사하지만, 노드 분할 시 기존 노드와 새로운 노드에 키를 분배하여 노드 사용률을 높인다.
- 각 노드는 최소
2/3채워져 있어야 한다 (B+트리는1/2채워져야 함).
장단점
- 장점: 공간 활용률이 높아 노드 분할 빈도가 낮고, 디스크 I/O 효율성이 높다.
- 단점: 구현이 상대적으로 복잡하며, 삽입과 삭제 연산이 복잡할 수 있다.
다른 균형 트리
AVL 트리 (AVL Tree)
- 구조: 자가 균형 이진 탐색 트리로, 각 노드의 좌우 서브트리 높이 차이가 최대 1이다.
- 장점: 모든 연산의 시간 복잡도가 O(log n)으로 일정하다.
- 단점: 빈번한 재밸런싱으로 삽입과 삭제가 비효율적일 수 있다.
레드-블랙 트리 (Red-Black Tree)
- 구조: 자가 균형 이진 탐색 트리로, 노드가 레드와 블랙으로 칠해져 균형을 유지한다.
- 장점: AVL 트리보다 삽입과 삭제가 효율적이다.
- 단점: 검색 속도가 AVL 트리보다 다소 느릴 수 있다.
2-3 트리 (2-3 Tree)
- 구조: 각 노드가 2개 또는 3개의 자식을 가지며, 모든 리프 노드가 같은 깊이에 있는 트리.
- 장점: 균형을 유지하기 쉽고, 삽입과 삭제 연산이 간단하다.
- 단점: B-트리보다 덜 일반적이며, 큰 데이터 집합에는 적합하지 않을 수 있다.
예제 코드 (Python)
B-트리 예제 코드
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # 최소 차수 (t)
self.leaf = leaf # 노드가 리프 노드인지 여부
self.keys = [] # 키 리스트
self.children = [] # 자식 노드 리스트
class BTree:
def __init__(self, t):
self.root = BTreeNode(t, True) # 루트 노드를 생성
self.t = t # 최소 차수 (t)
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1: # 루트가 꽉 찼을 때
new_root = BTreeNode(self.t, False)
new_root.children.append(self.root)
self.split_child(new_root, 0)
self.root = new_root
self.insert_non_full(self.root, k)
def split_child(self, x, i):
t = self.t
y = x.children[i]
z = BTreeNode(t, y.leaf)
x.children.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.children = y.children[t: 2 * t]
y.children = y.children[0: t - 1]
def insert_non_full(self, x, k):
if x.leaf:
i = len(x.keys) - 1
x.keys.append(0)
while i >= 0 and k < x.keys[i]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
i = len(x.keys) - 1
while i >= 0 and k < x.keys[i]:
i -= 1
i += 1
if len(x.children[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k > x.keys[i]:
i += 1
self.insert_non_full(x.children[i], k)
# B-트리 사용 예제
btree = BTree(3)
btree.insert(10)
btree.insert(20)
btree.insert(5)
btree.insert(6)
btree.insert(12)
btree.insert(30)
btree.insert(7)
btree.insert(17)결론
B-트리, B+트리, B*트리는 데이터베이스와 파일 시스템에서 데이터 검색을 최적화하기 위해 사용되는 균형 트리 구조이다. 각 트리는 고유의 장단점을 가지고 있으며, 특정 사용 사례에 따라 적합한 트리를 선택할 수 있다.
Get your hands dirty