B-TreeB-트리

B-트리(B-Tree)는 디스크 기반 스토리지 시스템을 위해 설계된 자기 균형 트리 자료구조다. 각 노드가 여러 키와 자식을 가질 수 있어 트리 높이를 최소화하며, 데이터베이스 인덱스와 파일 시스템의 표준 자료구조다.

특징

• •모든 리프 노드가 동일한 깊이
• •각 노드는 최소 ⌈m/2⌉, 최대 m개의 자식 (m: 차수)
• •O(log n) 검색·삽입·삭제

구조 (차수 3, 최대 2개 키)

           [30 | 70]
          /    |    \
   [10|20]  [40|60]  [80|90]

B-트리 vs B+-트리

데이터베이스에서의 활용

-- MySQL, PostgreSQL의 기본 인덱스 구조
CREATE INDEX idx_email ON users(email);
-- 내부적으로 B+-트리로 구현
-- 검색: O(log n), 범위 검색: O(log n + k)

관련 개념

• •이진 트리 — B-트리의 기반 개념
• •데이터베이스 인덱스 — B+-트리 기반 인덱스
• •이진 탐색 — B-트리 내 키 탐색

참고문헌

• •Cormen et al. Introduction to Algorithms — Chapter 18
• •Bayer, R. & McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes