[자료구조] B-tree와 B+tree

 

이진트리 종류

• 정이진트리 Full Binary Tree
  트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우 (한국의 교재에선 포화이진트리라고 번역된 게 있는데 둘은 다른 개념이다.)
• 포화이진트리 Perfect Binary Tree
  말 그대로 마지막 레벨까지 노드가 꽉 찬 트리, (2^N-1)개의 노드를 가진다.
• 완전이진트리 Complete Binary Tree
  마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 찬 트리, 마지막 레벨은 왼쪽부터 채워져야 한다.
• 균형이진트리 Balanced Binary Tree
  말단 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 균형이 깨지면 별도의 로직을 통해 다시 균형을 잡게 된다.

포화이진트리, 완전이진트리, 정이진트리는 이상적인만큼 현실에서 잘 찾아볼 수 없다. 하지만 균형이진트리는 한 쪽으로 쏠릴 수 있는 현실에서 트리의 높이를 균형적으로 유지시켜 줄 수 있기 때문에 AVL 트리, 레드블랙 트리, B-Trees 등등에서 사용된다.

 

비효율적인 Unbalanced BST, O(N)

 

 

---

 

앞으로 다룰 B-Trees는 균형이진"탐색"트리이므로 자동으로 정렬이 이루어진다! 이진 탐색 트리라는 것은 부모 노드를 기준으로 왼쪽 노드는 부모보다 작은 값, 오른쪽 노드는 부모보다 큰 값을 갖는 트리이다.

 

 

B-tree

데이터베이스와 파일시스템에서 널리 사용되는 트리 자료구조 일종이다. B-Tree는 이진트리를 확장한 하나의 노드가 하나 이상의 value(Key라고 부른다)와 두 개 이상의 자식 노드를 가질 수 있다. 

항상 O(logN)을 보장한다

 

가장 왼쪽 자식 노드의 Key들은 부모 노드의 1번째 key보다 값이 작고 두 번째 자식 노드는 부모의 1번 key보다 크고 2번 key보다 작다. Order 5라고 불리는데, 이 트리가 최대 4개의 key를 갖고 있어서 key 별로 최대 5개의 노드를 가질 수 있기 때문이다. 

 

Order M인 B-Tree라고 할 때

• 모든 노드는 최대 M개의 자식 노드를 가질 수 있다.
• k개의 자식 노드를 갖는 내부 노드(non-leaf node)는 k-1개의 key를 갖는다.
• 루트 노드는 말단 노드가 아니면, 최소 2개의 자식 노드를 갖는다.
• 모든 내부 노드(루트 제외)는 최소 ⌈M/2⌉ 노드를 갖는다.
• 모든 말단 노드는 같은 레벨에 존재한다.

B-Tree에 삽입하기

1. 삽입할 말단 노드를 찾는다.
2. 해당 말단 노드가 M-1개 미만의 key를 갖고 있다면 순서에 맞게 삽입한다.
3. 해당 말단 노드가 이미 가득 차있다면, 중간 key 값을 부모 노드로 올리고 값을 삽입한다. 만약 부모도 M개의 key 값을 가지면 같은 방식을 반복한다.

 

 

B+Tree

B-Tree는 모든 노드가 레코드 포인터를 가져야 하는 단점이 있다. 이런 단점을 보완한 알고리즘이 B+Tree이다. 같은 레벨의 key 값이 정렬되어 있고, 같은 레벨의 Sibling 노드가 연결리스트로 연결되어 있다.

 

 

 

https://www.cs.usfca.edu/~galles/visualization/BTree.html

https://www.youtube.com/watch?v=C_q5ccN84C8&ab_channel=FullstackAcademy