-
B-tree 자료구조 알아보기DataStructure 2023. 10. 30. 21:18728x90반응형
- 목차
B-tree 자료구조 알아보기.
B-tree 자료구조는 Balanced Tree 의 약자인 균형이 잡힌 트리 자료구조입니다.
여기서 Balance 라는 의미는 B-tree 에게 있어서 가장 중요한 특징인데요.
빠른 조회 속도와 데이터의 효율적인 저장을 위해서 고안된 방식입니다.
몇가지 사례를 들어 B-tree 의 Balance 를 설명해보겠습니다.
먼저 B-tree 자료구조는 최소한의 Depth (Height) 를 지향합니다.
즉, B-tree 자료구조는 일반적인 트리 자료구조에 비해서 높이가 짧습니다.
이는 조회시에 빠른 속도로 데이터를 조회할 수 있게 합니다.
이를 구현하기 위해서 하나의 노드가 지닐 수 있는 데이터의 갯수를 최대한 늘립니다.
하나의 노드가 하나의 데이터를 가지는 것보다 하나 이상의 데이터를 가지게하여 탐색 속도를 늘립니다.
< 일반적인 BST >
일반적인 BST 에서 8이라는 값을 조회하기 위해서 depth 3 까지 탐색을 이어갑니다.Root(5) depth: 1 => 1Child(4), 2Child(6) depth: 2 => 1-1Child(3), 2-1Child(7) depth: 3 => 1-1-1Child(2), 2-1-1Child(8)
< B-tree >
Degree 가 2인 B-tree 인 경우. (Degree 에 대한 설명은 아래에서 이어가겠습니다.)
아래와 같이 depth 1 에서 조회가 가능합니다.// degree : 2 Root(2,4,6) depth: 1 => 1Child(1), 2Child(3), 3Child(5), 4Child(7,8)
B-tree 는 Self-Balancing 기능을 가집니다.
일반적인 자료구조들은 Skewed 상태가 되기 쉽습니다.
즉, 한 방향으로 데이터들이 편향되기 쉽죠.
예를 들어,
< 편향된 BST >Root(1) Depth: 1 => Child(2) Depth: 2 => Child(3) Depth: 3 => Child(4) Depth: 4 => 4Child(5) Depth: 5 => 1Child(6) Depth: 6 => 1Child(7) Depth: 7 => 1Child(8) 1 2 3 4 5 6 7 8
< B-tree >// degree : 2 Root(2,4,6) depth: 1 => 1Child(1), 2Child(3), 3Child(5), 4Child(7,8) (2, 4, 6) (1) (3) (5) (7,8)
위의 사례들처럼 B-tree 는 데이터의 추가/삭제 시에 자체적인 균형을 잡는 기능이 내포되어 있습니다.
관련된 설명을 이어지는 글에서 상세히 설명하겠습니다.
degree 에 대해서.
degree 는 B-tree 자료구조가 가지는 제약사항들 중의 하나입니다.
이러한 제약사항은 B-tree 자료구조가 데이터 조회와 변형 시에 가장 좋은 효율을 낼 수 있도록 합니다.
degree 는 하나의 노드가 가지는 key 와 자식 노드의 수를 제한합니다.
( key 는 하나의 노드가 가지는 데이터들을 의미합니다. )
만약 B-tree 자료구조의 degree 가 t 인 경우에,
최소 자식노드의 수는 t,
최대 자식노드의 수는 2 * t 이 됩니다.
그리고 하나의 노드가 가지는 데이터의 수는 최소 t - 1 부터 최대 2 * t - 1 까지의 값을 가지게 됩니다.
예를 들어보겠습니다.
degree 가 2 인 B-tree 는 최소 1개에서 최대 3개의 key 를 가집니다.
그리고 최소 2개에서 최대 4개의 자식 노드를 가집니다.
key 의 갯수 범위: t - 1 ~ 2 * t - 1 = 2 - 1 ~ 2 * 2 - 1 = 1 ~ 3
자식 노드 갯수 범위: t ~ 2 * t = 2 ~ 2 * 2 = 2 ~ 4
< 1 부터 10 까지 B-tree 삽입 예시 >// 1,2,3,4,5 추가 Root(2) child(1) child(3,4,5) // 6 추가 Root(2,4) child(1) child(3) child(5,6) // 7 추가 Root(2,4) child(1) child(3) child(5,6,7) // 8 추가 Root(2,4,6) child(1) child(3) child(5) child(7,8) // 9, 10 추가 Root(4) 1child(2) 2child(6) 1-1child(1) 1-2child(3) 2-1child(5) 2-2child(7,8,9) Root(4) 1child(2) 2child(6,8) 1-1child(1) 1-2child(3) 2-1child(5) 2-2child(7) 2-3child(9,10)
위 예시는 1 부터 10 까지 데이터를 B-tree 에 삽입하는 예시입니다.
degree 의 제약사항처럼 key 의 갯수와 자식노드의 수는 범위 제약을 어기지 않습니다.
degree 가 3 인 B-tree 의 예시입니다.
degree 가 3 인 경우에는 하나의 노드가 2개에서 5개의 key를 가집니다.
그리고 3개에서 6개의 자식노드를 가질 수 있습니다.
< 1 부터 12 까지 삽입하는 예시 >// 1,2,3,4,5 추가 Root(1,2,3,4,5) // 6,7,8 추가 Root(3) child(1,2) child(4,5,6,7,8) // 9추가 Root(3,6) child(1,2) child(4,5) child(7,8,9) // 10,11 추가 Root(3,6) child(1,2) child(4,5) child(7,8,9,10,11) // 12 추가 Root(3,6,9) child(1,2) child(4,5) child(7,8) child(10,11,12)Root Node 와 Leaf Node 의 예외.
모든 노드가 Degree 에 따른 갯수 제한이 있는 것은 아닙니다.
오직 Internal Node 가 해당 제약 사항을 적용받는 대상인데요.
Root Node 와 Leaf Node 는 구조적으로 해당 제약을 덜 받습니다.
Root Node 와 Leaf Node 의 제약사항에 대해서 알아보도록 하겠습니다.Root Node.
Root Node 는 최소 자식 노드와 최소 key 갯수에 대한 제약을 받지 않습니다.
왜냐하면 초기 상태의 B-tree 는 데이터가 부족한 상태이기 때문에 Degree 에 따른 최소갯수를 맞출 수 없습니다.
Degree 가 3인 B-tree 는 최소 2개의 key 와 최소 3개의 자식 노드를 가져야합니다.
하지만 데이터가 최소 11 개의 데이터가 삽입되기 전까진 제약사항을 지킬 수 없습니다.
( 하나의 노드는 5개 이상의 key 를 가지므로 11개의 데이터가 삽입되면 구조적으로 Node Split 이 두번 발생 )Leaf Node.
Leaf Node 는 트리 구조의 제일 하위에 존재하는 노드입니다.
Leaf Node 는 애초에 자식 노드를 가지지 않기 때문에 자식 노드에 대한 제한이 없습니다.
Node Split.
Node Split 은 B-tree 의 Self-Balancing 의 핵심입니다.
Node Split 은 key 의 최대 갯수 이상으로 데이터가 추가되었을 때에 발생하며,
하나의 노드가 두개의 노드로 나뉘어지고,
각각의 노드가 key 를 나누어가지게 됩니다.
하나의 노드가 최대 갯수 이상의 key 를 가지게 되는 상태을 overfull 이라고 합니다.
즉, overfull 상태의 노드가 Node Split 의 대상 노드가 되죠.
아래 예시들은 각 Degree 에서 overfull 상태를 보여줍니다.
< Degree 2 인 B-tree 의 overfull >
// 1,3,5 추가 // Root Node overfull Root(1,3,5) // 7 추가 // Node Split 발생 Root(3) Child(1) Child(5,7) // 9 추가 // child node overfull Root(3) Child(1) Child(5,7,9) // 11 추가 // Node Split 발생 Root(3,7) Child(1) Child(5) Child(9,11)
< Degree 3 인 B-tree 의 overfull >// 1,3,5,7,9 추가 // Root Node overfull Root(1,3,5,7,9) // 11 추가 // Node Split 발생 Root(5) Child(1,3) Child(7,9,11) // 13,15 추가 // Child Node overfull Root(5) Child(1,3) Child(7,9,11,13,15) // 17 추가 // Node Split 발생 Root(5,11) Child(1,3) Child(7,9) Child(13,15,17)
위와 같은 방식으로 overfull Node 는 Node Split 이 발생하게 됩니다.관련 예시.
< B-tree 파이썬 코드 >class BTreeNode: def __init__(self, leaf=True): self.keys = [] self.children = [] self.leaf = leaf class BTree: def __init__(self, t): self.root = BTreeNode() self.t = t def insert(self, key): root = self.root if len(root.keys) == (2 * self.t) - 1: new_root = BTreeNode(leaf=False) new_root.children.append(root) self._split_child(new_root, 0) self.root = new_root self._insert_non_full(new_root, key) else: self._insert_non_full(root, key) def _insert_non_full(self, node, key): i = len(node.keys) - 1 if node.leaf: node.keys.append(None) while i >= 0 and key < node.keys[i]: node.keys[i + 1] = node.keys[i] i -= 1 node.keys[i + 1] = key else: while i >= 0 and key < node.keys[i]: i -= 1 i += 1 if len(node.children[i].keys) == (2 * self.t) - 1: self._split_child(node, i) if key > node.keys[i]: i += 1 self._insert_non_full(node.children[i], key) def _split_child(self, parent, index): t = self.t child = parent.children[index] new_child = BTreeNode(leaf=child.leaf) parent.keys.insert(index, child.keys[t - 1]) parent.children.insert(index + 1, new_child) new_child.keys = child.keys[t: (2 * t) - 1] child.keys = child.keys[0: t - 1] if not child.leaf: new_child.children = child.children[t: 2 * t] child.children = child.children[0: t] def search(self, key, node=None): if node is None: node = self.root i = 0 while i < len(node.keys) and key > node.keys[i]: i += 1 if i < len(node.keys) and key == node.keys[i]: return True elif node.leaf: return False else: return self.search(key, node.children[i]) def display(self, node=None, level=0): if node is None: node = self.root print(f"Level {level}: {node.keys}") level += 1 if not node.leaf: for child in node.children: self.display(child, level) # Usage example: if __name__ == "__main__": b_tree = BTree(2) keys = [3, 8, 1, 4, 2, 6, 7] for key in keys: b_tree.insert(key) b_tree.display() print("Search for key 4:", b_tree.search(4)) print("Search for key 5:", b_tree.search(5))1 부터 6 까지 데이터가 추가되는 경우.
1,2,3,4,5,6 // 1 추가 Root(1) // 2 추가 Root(1,2) // 3 추가 Root(1,2,3) // 4 추가 Root(2) 1-1Child(1), 1-2Child(3,4) // 5 추가 Root(2) 1-1Child(1), 1-2Child(3,4,5) // 6 추가 Root(2,4) 1-1Child(1), 1-2Child(3), 1-3Child(5,6)7 이 추가되는 경우.
leaf node 의 경우에는 key 의 갯수가 2 * t - 1 인 최댓값에 이르더라도 당장 Node Split 되지는 않습니다.
이는 leaf node 의 예외 규칙입니다.Root(2,4) 1-1Child(1), 1-2Child(3), 1-3Child(5,6) // 7 추가 Root(2,4) 1-1Child(1), 1-2Child(3), 1-3Child(5,6,7)8 이 추가되는 경우.
8이 추가되는 적절한 위치의 노드는 3Child 노드입니다.
하지만 3Child 노드는 Overfull 상태입니다.
5,6,7 인 3개의 key 가 존재하기 때문입니다. (2 * t - 1 == 3)
따라서 3Child 노드는 Node Split 이 작동하며,
Median Key : 6, Left Subset : [5], Right Subset : [7,8]
이 됩니다.
따라서 4Child 노드가 새롭게 생성되고, 7,8 이라는 key 를 가집니다.
기존의 3Child 노드는 Left Subset 인 5 를 key 로 가지며,
Median Key 인 6 은 Parent Node 인 Root Node 로 보내집니다.// 7이 추가된 상태 Root(2,4) 1Child(1), 2Child(3), 3Child(5,6,7) // 8 추가 Root(2,4) 1Child(1), 2Child(3), 3Child(5,6,7,8) // 8 추가된 이후에 Node Split Root(2,4,6) 1Child(1), 2Child(3), 3Child(5), 4Child(7,8)9 가 추가되는 경우.
9가 추가될때, Root Node 는 Overfull 상태입니다.
Root Node 가 Overfull 상태이면, Root Node 의 Split 가 우선적으로 선행됩니다.
Root(2,4,6) 이 Split 되면, Root(4), 1Child(2), 2Child(6) 와 같이 분리가 됩니다.
그리고 Root(2,4,6) 가 가지는 Child Node 들은 적절하게 1Child(2), 2Child(6) 하위에 분배됩니다.
1Child(2) -> 1-1Child(1), 1-2Child(3)
2Child(6) -> 2-1Child(5), 2-1Child(7,8)// 8 이 추가된 상태. Root(2,4,6) 1Child(1), 2Child(3), 3Child(5), 4Child(7,8) // 9 가 추가될 때, // Root 노드가 Overfull 상태라서 Root Node 의 Split 이 선행됨. Root(4) 1Child(2), 2Child(6) 1-1Child(1), 1-2Child(3), 2-1Child(5), 2-1Child(7,8) // 9 가 추가. Root(4) 1Child(2), 2Child(6) 1-1Child(1), 1-2Child(3), 2-1Child(5), 2-1Child(7,8,9)
반응형