B-tree란?
B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다.
즉, 하나의 노드에 하나의 데이터를 저장하는 다른 Self-Balanced Tree와 달리, 하나의 노드에 여러개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더 획기적으로 줄이도록 고안된 트리입니다.
(B-tree와 B+tree, B*tree가 있지만 일반적으로 B tree라 함은 B-tree를 의미합니다.)
이렇게 고안된 트리를 유지하기 위한 몇가지 규칙이 있습니다.
1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다.
첫번째 노드의 데이터 갯수를 2개로 잡았다면, 그 자식 노드의 수는 3개여야 합니다.
2. 노드 안 데이터는 정렬되어야 한다.
한 노드 안의 데이터는 오름차순으로 정렬됩니다.
3. 자식 노드의 데이터는 부모 노드의 데이터에 따라 배치된다.
부모 노드의 데이터를 기준으로 자식 노드를 정렬하여 나눕니다.
예시로 1, 2, 3, 4, 5, 6, 7, 8의 값에 대해, 부모 노드의 데이터에 3, 6이 들어간다면
3 | 6
| | |
1 | 2 4 | 5 7 | 8
과 같은 형태로 자식 노드는 3보다 작은 값, 3과 6 사이의 값, 6보다 큰 값으로 이루어진 3개의 자식 노드가 생깁니다.
4. 루트 노드가 리프 노드가 아닌 경우 항상 2개 이상의 자식을 갖는다.
5. M차 B-tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가지고 있어야 한다.
노드가 가질 수 있는 최대 자식의 수를 M이라 할 때, 이를 M차 B-tree라 합니다.
4차 B-tree에서, 루트와 리프를 제외한 노드 각각의 데이터는 최소 2개여야 한다는 의미입니다.
6. 모든 리프 노드의 높이는 같아야 한다.
7. 리프 노드의 데이터 수는 M보다 작아야 한다.
4차 B-tree에서, 리프 노드에 들어가는 데이터 수는 3 이하여야 한다는 의미입니다.
B-tree의 연산
탐색
B-tree는 탐색 시 루트노드에서부터 하향식으로 탐색합니다.
자식 노드의 데이터는 부모 노드의 데이터에 따라 오름차순으로 배치되므로,이를 활용한 대소비교를 통해 알맞은 브랜치를 따라 값을 찾을 때까지 하향하며 탐색해갑니다.
삽입
B-tree의 삽입 과정은 탐색과 달리 리프노드에서부터 상향식으로 찾아갑니다.
데이터를 넣을 적절한 리프 노드를 탐색하여 노드에 값을 삽입하면 되는데,
이때 위에서 언급한 B-tree의 조건인 "리프 노드의 데이터 수는 M보다 작아야 한다" 를 만족시켜야 된다는 점에 유의해야 합니다. 노드에 들어있는 데이터 수가 M-2 이하라면 그냥 삽입하면 되지만, M-1이라면 값이 삽입될 시 데이터 수가 M이 되면서 B-tree의 조건을 위배하게 됩니다.
이 경우, 해당 값을 부모 노드로 올리며 그 자식 노드들은 새로 분리를 해줍니다. 이 과정을 B-tree의 조건을 만족할 때까지 재귀적으로 수행합니다. 이 과정은 최대 루트 노드의 위까지 수행될 수 있습니다.
삭제
노드를 삭제하는 과정은 조금 더 복잡한데, 삭제 시 B-tree의 조건인 아래 3가지
- 루트 노드와 리프 노드를 제외한 노드는 2개 이상의 자식을 가져야 한다.
- 각 노드는 M/2 ~ M-1개의 데이터를 가질 수 있다.
- 각 노드의 데이터 수가 k라면 자식 노드의 수는 k+1이여야 한다.
를 만족하도록 트리를 재구조화해야 합니다. 이때 경우에 따라 값이 삭제된 노드의 나머지 데이터를 분할하거나, 부모 노드로 올린 뒤 나머지 자식 노드를 B-tree의 조건에 맞게 재배치하는 등의 작업이 필요합니다.
만약 현재 node와 자식 node가 모두 데이터 수가 최소인 경우, 트리의 높이를 줄여야 할 수도 있습니다. 삭제된 데이터의 자식 노드를 합치고 부모 노드를 내려 이를 자식으로 연결하는 등의 재구조화가 필요합니다.
B*tree란?
B*tree는 균형을 유지하기 위한 연산에서 노드의 생성과 부가적인 연산을 최소화하기 위해 등장하게 되었습니다.
기존 B-tree에서 자식 노드가 최소 M/2개의 데이터를 가져야 했던 점이 M*2/3개로 바뀌었고, 노드가 가득 찼을 때 분열하지 않고 형제 노드로 재배치를 하게 된다는 차이점이 있습니다.
B+tree란?
B+Tree는 B-Tree의 확장 개념입니다. B-Tree의 경우 중간 노드들의 데이터에 key와 value를 담을 수 있지만, B+tree의 경우 중간 노드에는 key만 두고, value는 담지 않습니다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리는 Linked list로 연결되는 방식입니다. 이러한 방식의 장점은 리프 노드를 제외하면 value를 담지 않기에 메모리를 더 확보할 수 있습니다. 또한 트리의 높이 또한 낮아지게 되며, 탐색 시 리프 노드의 데이터만 살피므로 B-Tree보다 탐색에 매우 유리합니다.
B+tree 구현 예제 (Python)
아래 조건을 만족하는 B+tree를 구현하라.
- B+트리의 한 노드에 저장할 수 있는 최대 키의 갯수는 31개이며, 자녀 노드를 가르키는 포인터는 최대 32개
- insert과 range 검색 연산 지원
- 입력 파일은 여러개의 integer 집합인 input.txt
import time
class TreeNode:
def __init__(self, max_keys):
self.max_keys = max_keys
self.keys = []
self.children = []
self.is_leaf_node = True
self.next = None
def insert_key(self, key):
if key in self.keys:
print(f"{key} 값이 존재하여 삽입할 수 없음")
return False
if self.is_leaf_node:
self.keys.append(key)
self.keys.sort()
else:
for i, key_value in enumerate(self.keys):
if key < key_value:
return self.children[i].insert_key(key)
return self.children[-1].insert_key(key)
return True
def split(self):
mid_index = self.max_keys // 2
if self.is_leaf_node:
# if leaf node
new_node = TreeNode(self.max_keys)
new_node.keys = self.keys[mid_index:]
new_node.is_leaf_node = True
new_node.next = self.next
self.next = new_node
self.keys = self.keys[:mid_index]
# Return the new sibling and the lowest key of the new sibling
return new_node, new_node.keys[0]
else:
# elif Internal node
new_node = TreeNode(self.max_keys)
new_node.keys = self.keys[mid_index+1:]
new_node.children = self.children[mid_index+1:]
new_node.is_leaf_node = False
self.keys = self.keys[:mid_index]
self.children = self.children[:mid_index+1]
# Return the new sibling and the middle key
return new_node, self.keys[mid_index]
def is_full(self):
return len(self.keys) >= self.max_keys
def range_search(self, min_key, max_key):
result = []
node = self
while not node.is_leaf_node:
node = node.children[0]
while node:
for key in node.keys:
if min_key <= key <= max_key:
result.append(key)
node = node.next
return result
class BplusTree:
def __init__(self, order):
self.root = TreeNode(order)
def insert(self, key):
if not self.root.insert_key(key):
return
if self.root.is_full():
new_root, mid_key = self.root.split()
new_root_node = TreeNode(self.root.max_keys)
new_root_node.keys = [mid_key]
new_root_node.children = [self.root, new_root]
new_root_node.is_leaf_node = False
self.root = new_root_node
def Range(self, min_key, max_key):
found_keys = self.root.range_search(min_key, max_key)
if not found_keys:
print("값을 알 수 없음")
else:
return found_keys
bpt = BplusTree(32)
# open file
with open("input.txt", "r") as file:
lines = file.readlines()
keys = []
for line in lines:
elements = line.split(", ")
for i in range(len(elements)):
key = int(elements[i])
keys.append(key)
# insert
start = time.time()
for key in keys:
bpt.insert(key)
insert_t = time.time()-start
# Range
start = time.time()
print(' - Range result')
result = bpt.Range(1, 100) #change
if result:
print(', '.join(map(str, result)))
else:
pass
range_t = time.time()-start
print("insert time: ", insert_t)
print("range time: ", range_t)'CS > Data structure' 카테고리의 다른 글
| [자료구조] Red-Black tree란? / Red-Black tree의 원리 및 활용 (0) | 2023.05.29 |
|---|---|
| [자료구조] Splay tree란? / Splay tree의 원리 및 활용 (0) | 2023.05.25 |
| [자료구조] AVL tree란? / AVL tree의 연산 방법 및 활용 (0) | 2023.05.23 |
| [자료구조] Graph란? / DFS와 BFS / 활용 및 예제 (백준 1260) (1) | 2023.03.21 |
| [자료구조] HashTable이란? / Chaining과 Open Addressing의 차이 / 예제 (백준 17219) (1) | 2023.03.13 |
