B 트리, B+ 트리 비교

1. B 트리, B+ 트리 개념 비교

B 트리	B+ 트리
균형잡힌 m-차 트리로, 모든 노드에 키와 데이터를 저장하는 트리 구조	B트리 확장 구조로, 리프 노드에만 실제 데이터 저장,  내부 노드는 인덱스 역할하는 구조

 

 

2. B 트리, B+ 트리 상세 비교

항목	B 트리	B+ 트리
데이터 저장	모든 노드	리프 노드
내부 노드 역할	데이터 저장, 인덱스	인덱스 역할
리프 노드 연결	없음	linked list 연결
검색 경로	루트 -> 내부 노드	루트 -> 리프
범위 검색	느림 (리프 간 연결 없음)	빠름 (리프 간 연결)
공간 효율	적은 노드에 분산 저장	인덱스는 작지만 리프는 큼
장점	- 삽입/삭제 처리 단순 - 노드 수 작음	- 검색/범위 검색 빠름 - 정렬된 순서 유지 쉬움
단점	- 범위 탐색 비효율적 - 내부 노드 변경 많음	- 리프 노드가 커서 디스크 접근 많음