[자료구조] B-Tree & B+ Tree

📋 목차

• B-Tree란?
• B-Tree 특징
• B+ Tree란?
• B+ Tree 특징
• B-Tree와 B+ Tree 비교
• B-Tree 이용 사례

---

1️⃣ B-Tree란?

B-Tree

• 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조
• 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 자료구조의 일종

→ 탐색 성능을 높이기 위해 균형있게 높이를 유지하는 균형 트리입니다.

→ (단, B-Tree는 ‘이진 트리’가 아님 !)

 

2️⃣ B-Tree 특징

• 노드의 데이터 수가 N이면, 자식 수는 N+1
• 각 노드의 데이터는 정렬된 상태이어야 함
• 루트 노드는 적어도 2개 이상의 자식을 가져야 함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어야 함 (M=노드 내 최대 데이터 수)
• 외부(단말) 노드로 가는 경로의 길이는 모두 같다
• 입력 자료는 중복될 수 없음
• 이진 트리 구조의 간결함 + 균형 → 검색/삽입/삭제 모두 O(logN)

 

3️⃣ B+ Tree란?

B+ Tree

• B-Tree는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있습니다.
• 이러한 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있습니다.

• Index node들과 Data node로 구성
• Index node : 리프노드를 제외한 나머지 노드
  • Index set : index node 들의 모임 → 데이터의 빠른 접근을 위한 인덱스 역할
• Data node : 리프노드
  • sequence set : 리프노드의 모임 → 오름차순으로 정렬( 실제 데이터)

 

4️⃣ B+ Tree 특징

• Data node는 연결리스트로 형성되어 있다.
• B트리의 순차접근에 대한 문제의 해결책으로 제시되었다.
• B트리와 다르게 삽입, 삭제연산이 리프노드에서만 이루어진다.
• 데이터의 빠른 접근을 위한 인덱스 역할만 하는 노드가 추가로 있다.
• 모든 key, data가 리프노드에 모여있다.

 

5️⃣ B-Tree vs B+ Tree

 

6️⃣ B-Tree 이용 사례

• DBMS나 파일시스템의 인덱스 자료구조로 활용 (B+tree, B*tree로 발전)
• 검색엔진, 패턴 매칭 등 성능이 일정하면서 빠른 탐색이 요구되는 분야에 활용

---

🌐 참고 링크

[자료구조] B 트리

균등한 응답속도를 위한 탐색 트리, B-Tree

[Data Structure] B Tree(Balanced Tree) | B Tree 규칙 | B+ Tree | B Tree와 B+ Tree 차이

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

[Computer Science] B-트리(B-Tree)

B-tree 와 B+ tree