B-Tree란?
•
다진 탐색 트리(이진 탐색 트리(BST) X)
◦
하나의 노드에 여러 데이터를 저장
◦
한 노드가 여러 자식 노드를 가질 수 있음
•
균형 트리 : 모든 리프 노드가 동일 레벨
그림에는 표현이 안되었지만, 각 노드에는 실질 데이터를 포함할 수도 있음. 일반적으로 키는 데이터를 찾기 위한 인덱스로 활용되므로, ‘키를 알면 키에 대응되는 데이터도 알 수 있다’를 이해할 것
•
B트리의 각 노드 : 하나 이상의 키 값이 존재, 각 키들이 오름차순으로 정렬
•
각 키 사이에 자식 노드(or 서브트리)의 위치를 저장하고 있으며, 키가 자식 노드(or 서브트리)가 가질 수 있는 값의 범위를 나타내는 역할 수행
◦
이진탐색트리(BST)의 경우, 왼쪽 자식 노드의 크기가 오른쪽 자식 노드의 크기보다 작듯이
◦
각 자식 노드의 값이 왼쪽 자식 노드(서브트리)부터 오른쪽 자식 노드(서브트리)까지 정렬되어있는 셈
•
키 사이사이에 자식 노드가 존재하기에, 키가 N개인 노드가 가질 수 있는 자식 노드 수는 반드시 (N+1)개
M차 B트리
•
B트리(다진 탐색 트리)는 한 노드가 가질 수 있는 자식 노드의 수의 최대/최소가 정해져 있음
•
한 노드가 가질 수 있는 최대 자식 노드의 개수가 M개인 트리
◦
M차 B트리가 가질 수 있는 키 개수
▪
최소 [M/2] - 1개
▪
최대 M - 1개
◦
M차 B트리가 가질 수 있는 자식 노드 개수
▪
최소 : [M/2]개
▪
최대 : M개
•
[] : 올림기호 의미
•
EX : 5차 B트리의 한 노드는 최대 5개의 자식 노드를 가질 수 있고, 최소 3개의 자식 노드를 가질 수 있음
사례, 장점
•
B트리는 데이터베이스나 파일시스템처럼 대량의 데이터를 기반으로 탐색, 접근, 저장을 수행할 때 활용
◦
DB, FS : 입출력 연산 횟수를 최소화하는 것이 좋음
▪
입출력연산 → 메모리 접근에 비해 수행 속도가 느리기 때문
◦
OS는 블록 단위로 보조기억장치를 읽고 씀
▪
한 노드에 블록 단위의 여러 데이터를 저장할 수 있는 B트리가 보조기억장치에 대한 입출력 연산을 줄일 수 있어 성능 면에서 이득
코드로 확인해볼까요?
import math
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # 최소 차수
self.leaf = leaf
self.keys = []
self.children = []
def insert_non_full(self, key):
i = len(self.keys) - 1
# left == True -> 리프 노드라는 소리
if self.leaf:
# 키를 적절한 위치에 삽입
self.keys.append(None) # 공간 확보
# 키를 삽입할 위치 찾기 : 오름차순 정렬
while i >= 0 and key < self.keys[i]:
self.keys[i+1] = self.keys[i]
i -= 1
self.keys[i+1] = key
else:
# 자식 노드로 이동
while i >= 0 and key < self.keys[i]:
i -= 1
i += 1
# 자식 노드가 가득 찼다면 분할
if len(self.children[i].keys) == (2 * self.t) - 1:
self.split_child(i)
if key > self.keys[i]:
i += 1
self.children[i].insert_non_full(key)
def split_child(self, i):
t = self.t # 최소 차수
y = self.children[i] # 분할할 자식 노드
z = BTreeNode(y,t, leaf=y.leaf) # 새로 만들 오른쪽 자식 노드
self.keys.insert(i, y.keys[t-1]) # 부모 노드에 중간 키 삽입
self.children.insert(i + 1, z) # 새로 만든 z 노드를 부모의 자식 리스트에 추가
# 키 분배
z.keys = y.keys[t:]
y.keys = y.keys[:t-1]
# 자식 노드 분배(리프가 아닌경우)
if not y.leaf:
z.children = y.children[t:]
y.children = y.children[:t]
def __str__(self, level=0):
result = " " * level + str(self.keys) + "\n"
for child in self.children:
result += child.__str__(level + 1)
return result
Python
복사
참고자료