[DATABASE] B-Tree 인덱스란?

데이터베이스에서 사용되는 균형 트리 구조 중 B-Tree 인덱스에 대해서 알아보자.

 

---

1. B-tree 인덱스

 

1-1. B‑Tree 인덱스란?

B-Tree(Balanced Tree)는 모든 노드(내부 노드, 리프 노드)에 실제 데이터를 저장하는 균형 트리 구조이다.

 

B-Tree 인덱스 (모든 노드에 데이터를 저장)

---

2. B-tree 인덱스의 구조

• 노드 구성
  • 각 노드는 키-데이터 쌍들과 자식 포인터들로 구성된다.
  • 차수가 m인 B-Tree에서 각 노드는 최대 m-1개의 키-데이터 쌍을 가질 수 있다.
• 분할과 병합 
  • 노드가 가득 차면 중간 키를 부모로 올리고 노드를 분할한다.
  • 반대로 노드가 너무 비면 형제 노드와 병합한다.
• 데이터 접근 방식 
  • 내부 노드에서도 데이터를 직접 찾을 수 있어, 검색 시 리프 노드까지 내려가지 않아도 되는 경우가 있다.
  • 위 그림과 같이 값 70을 찾는 경우 루트 노드에서 바로 찾을 수 있다.

 

---

3. 특징

• 데이터 분산 저장: 내부 노드와 리프 노드 모두에 실제 데이터(또는 데이터 포인터)가 저장된다. 
• 가변 검색 경로: 찾는 데이터가 내부 노드에 있으면 리프까지 내려가지 않고 바로 반환할 수 있어 검색 경로가 다양하다.
• 균형성: 모든 리프 노드가 동일한 레벨에 위치하여 최악의 경우에도 O(log n) 성능을 보장한다.
• 다중 분기: 각 노드가 여러 개의 키와 자식을 가질 수 있어 트리의 높이를 낮게 유지한다.