B트리(B-Tree) 와 B+트리(B+Tree)

B-트리 (Balanced Tree)

개념

• 이진 탐색 트리(Binary Search Tree) 를 일반화한 형태.
• 하나의 노드가 여러 개의 키(key) 와 자식 포인터(pointer) 를 가질 수 있음.
• 항상 균형(Balanced) 을 유지하여, 검색, 삽입, 삭제 시 효율적.

구조

• 하나의 노드는 여러 개의 키(Key) 와 자식 노드 포인터를 가짐.
• 각 노드 내의 키는 정렬된 상태로 저장됨.
• 루트에서 리프까지의 높이가 일정(균형 트리).

특징

항목	설명
균형 유지	루트~리프 깊이가 항상 같음
모든 노드에 데이터 저장	내부 노드(비단말 노드)와 리프 노드 모두 실제 데이터(레코드) 보관 가능
검색	루트에서 리프까지 키 비교로 탐색
삽입/삭제 시 재구조화	필요 시 노드 분할(split) 또는 병합(merge) 수행
활용 예시	파일 시스템, 데이터베이스 인덱스의 기본 구조

예시

      [30]
     /    \
 [10,20]  [40,50,60]

• 루트(30)를 기준으로 왼쪽엔 10,20 / 오른쪽엔 40,50,60 저장
• 모든 노드에 실제 데이터 존재 가능

---

B+트리 (B-트리의 확장형)

개념

• B트리의 변형 버전으로, 인덱스 검색 효율을 높이기 위해 고안된 구조
• 데이터는 리프 노드에만 저장, 내부 노드는 인덱스 역할만 수행

구조

• 리프 노드(leaf node): 모든 실제 데이터 저장
• 비단말 노드(internal node): 검색용 키만 저장
• 리프 노드끼리 연결된 연결 리스트(linked list) 구조로 되어 있음 → 순차 접근 빠름

특징

항목	설명
데이터 저장 위치	모든 데이터는 리프 노드에만 저장
내부 노드 역할	검색용 인덱스 키만 저장
리프 노드 연결	리프 노드끼리 포인터로 연결되어 있어 순차 탐색이 빠름
검색 효율	항상 리프 노드에서 검색 종료 → 탐색 경로 일정
활용 예시	데이터베이스 인덱스 (특히 클러스터형 / 보조 인덱스)

예시

          [30 | 60]
         /     |     \
     [10,20] [30,40,50] [60,70,80]
             ↘   ↘   ↘
         (리프노드 연결)

• 내부 노드: 인덱스 키만 보유
• 리프 노드: 실제 데이터 저장 및 연결되어 있어 정렬 순회가 빠름

  

 

---

B트리 vs B+트리 비교표

구분	B-트리	B+트리
데이터 저장 위치	내부 노드와 리프 노드 모두	리프 노드에만 저장
내부 노드 역할	데이터 + 인덱스	인덱스 전용
리프 노드 연결	연결 안 됨	연결 리스트로 연결됨
검색 효율	데이터가 중간 노드에 있을 수도 있어 비일관적	항상 리프에서 끝나므로 일관된 검색 경로
범위 검색(range query)	느림	빠름 (리프 간 연결)
공간 효율성	상대적으로 낮음	더 높음
활용 분야	파일 시스템 인덱스	DB 인덱스 표준 구조 (MySQL, Oracle 등)