[DB/자료구조]B+ tree(B+ 트리)란?

B-tree란?

---

• B-트리는 트리형 자료구조, 이진트리를 확장해서 더 많은 child node를 가질 수 있게한 일종으로 Balanced-Tree이다.
• 즉 삽입과 삭제가 일어나도 최대한 균형을 유지해 이진탐색의 효율을 살리는 트리이다.

특징

---

• 모든 leaf node가 루트로부터 같은 거리
• 각 노드별로 가능한 children 중 적어도 절반은 가지고 있다(웬만하면 balance되어있는)
• 루트 노드는 예외
• B+ 트리는 B-tree를 개량한 트리로 Inner Node에는 Key만 저장하고 Leaf Node에 Key와 Data를 함께 저장한다.
• 데이터 접근 시간복잡도가 O(1)인 hash table보다 부등호 연산에 효율적 등호 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않음

B+ Tree Index란?

• B+ Tree 자료구조를 활용한 데이터베이스 인덱싱

특징

---

• 수직적 탐색(조건에 만족하는 첫번째 레코드를 찾음)과 수평적 탐색(리프노드에서 조건에 맞는 레코드를 찾음)
• insertion, deletion 때 at least half full → balance tree 형태를 유지
• 삽입 삭제 시 자동으로 구조를 유지, 주기적으로 재구성할 필요가 없음
• 위를 위해서 약간의 overhead가 있음
• file organization: 블록에 레코드를 저장하면 삭제, 삽입시 순서대로 정렬되고 block 공간이 비효율하게 사용될 수 있음 → leaf node에 인덱스가 아닌 records를 저장하면 B+노드 관리가 쉬워짐.

구조

---

• 각각의 노드는 pointer와 key 값이 번갈아 반복되는 구조
• leaf node의 pointer들은 다음 칸의 key 값에 해당하는 데이터의 실제 위치를 저장, 마지막 pointer는 다음 leaf node의 위치를 저장
• Non-leaf Node(리프노드 전까지 중간 노드, index node라고도 함)는 child node의 위치를 저장
• key 값을 기준으로 왼쪽 pointer는 key 값보다 작은값의 노드를, 오른쪽 pointer는 key 값보다 크거나 같은값의 노드를 지정
• leaf node(레코드를 지정, 마지막 pointer를 이용해 leaf node들을 체인으로 묶어주기도 함)
• n = 5, pointer의 개수, 밸류는 반절이상. 2개-4개

Search

• search performance : at least half full이 큰 장점, 데이터 수가 많아도 높이가 낮음

Insertion

• node가 풀이 아닐 때까지 위에 노드까지 split해줌 → worst case로 높이 하나 늘어남
• delete 경우 at least half full 하지 않으면 merge or redistrubute(해줄 때 적절히 분배해줌)

---

다시 살펴보기, B-tree, B+tree