B+ 트리(B+ Tree)는 B-트리를 확장한 자료구조로, 삽입·삭제·탐색 연산에서 B-트리보다 더 나은 성능을 제공합니다. 주로 데이터베이스 인덱스나 파일 시스템처럼 대용량 데이터를 디스크에서 효율적으로 관리해야 하는 환경에서 널리 활용됩니다.
B-트리와 B+ 트리의 차이
일반적인 B-트리에서는 키(key)와 레코드 값이 내부 노드와 리프 노드 양쪽 모두에 저장됩니다. 반면 B+ 트리에서는 실제 데이터(레코드)가 오직 리프 노드에만 저장되고, 내부 노드에는 탐색을 위한 키 값만 저장됩니다.
또한 B+ 트리의 리프 노드들은 연결 리스트(linked list)처럼 서로 연결되어 있어, 특정 지점부터 데이터를 순차적으로 읽어 들일 수 있다는 점이 큰 특징입니다.
B+ 트리 예시
B+ 트리의 기본 연산
B+ 트리는 탐색(search), 삽입(insertion), 삭제(deletion)와 같은 기본 연산을 지원합니다. 각 노드 내부의 항목은 항상 정렬된 상태로 유지되며, i번째 위치의 요소는 그 앞과 뒤에 자식 노드를 가집니다. 따라서 왼쪽에 있는 자식들은 해당 키보다 작은 값을, 오른쪽에 있는 자식들은 더 큰 값을 담게 됩니다. 이러한 정렬 구조 덕분에 이진 탐색과 유사한 방식으로 빠르게 원하는 키를 찾아갈 수 있습니다.
B-트리 대비 B+ 트리의 장점
- 균일한 디스크 접근: 어떤 레코드든 동일한 횟수의 디스크 접근만으로 조회할 수 있습니다.
- 낮고 균형 잡힌 트리 높이: 트리의 높이가 항상 균형을 이루며, B-트리에 비해 더 낮게 유지됩니다.
- 순차 검색 가능: 리프 노드가 연결 리스트처럼 연결되어 있어 범위 질의(range query)나 순차 검색에 유리합니다.
- 효율적인 인덱싱: 내부 노드의 키가 인덱스 역할을 하여 탐색 경로를 안내합니다.
- 빠른 탐색 속도: 실제 데이터가 리프 레벨에만 존재하므로 탐색 과정이 단순하고 빠릅니다.
이처럼 B+ 트리는 안정적인 성능과 효율적인 디스크 I/O를 동시에 만족하기 때문에, MySQL의 InnoDB를 비롯한 다양한 데이터베이스 시스템의 기본 인덱스 구조로 채택되고 있습니다.