B+Tree 인덱스

B+Tree 인덱스

B-Tree의 변형으로 모든 데이터를 리프 노드에만 저장하고 리프 노드들이 연결 리스트로 연결된 구조로, 대부분의 RDBMS에서 기본 인덱스로 사용

B-Tree와 차이점

• •내부 노드: 키만 저장 (데이터 없음, 인덱싱 역할만)
• •리프 노드: 모든 키와 데이터 저장
• •리프 노드 연결: 리프 노드들이 Linked List로 연결

구조

• •내부 노드(Internal): 키와 자식 포인터만 저장
• •리프 노드(Leaf): 키 + 데이터(또는 ROWID) 저장
• •Leaf Link: 리프 노드 간 양방향 연결

장점

• •범위 검색 효율: 리프 노드 순차 스캔
• •내부 노드 Fan-out 증가: 더 많은 키 저장 가능
• •일관된 검색 성능: 항상 리프까지 탐색

적용사례: Oracle, MySQL InnoDB, PostgreSQL 기본 인덱스

비교: B+Tree(리프에 데이터/리프연결) vs B-Tree(모든노드 데이터)

연관: 인덱스, B-Tree, 범위 검색, 클러스터드 인덱스