B+트리 (B+ Tree)

B+트리 (B+ Tree)

내부 노드는 키만 저장하고 모든 데이터는 리프 노드에만 저장하며 리프 노드가 연결 리스트로 연결된 B-트리 변형으로, 범위 쿼리와 순차 접근에 최적화

목적: 범위 쿼리 최적화, 순차 접근, 디스크 I/O 최소화, 데이터베이스 인덱싱

특징: 리프에만 데이터, 리프 연결, 내부 노드는 인덱스만, 더 많은 키

구조

• •내부 노드: 키만 저장(인덱스 역할), 더 많은 키 가능(차수 증가)
• •리프 노드: 키+데이터 저장, 연결 리스트(순차 접근)
• •모든 데이터는 리프에만 존재

연산

• •검색: 내부 노드 탐색 → 리프 도달, O(log n)
• •범위 쿼리: 시작 리프 찾기 → 연결 리스트 순회, O(log n + k)
• •삽입·삭제: B-트리와 유사, 리프에서만 데이터 변경, O(log n)

시간 복잡도: 검색 O(log n), 범위 쿼리 O(log n + k)

장점: 범위 쿼리 최적, 순차 접근 빠름, 더 많은 키(높은 차수), 디스크 I/O 최소화

단점: 복잡한 구현, 중복 키(내부+리프)

적용사례: 데이터베이스 인덱스(MySQL InnoDB 기본), PostgreSQL, Oracle, 파일 시스템

비교: B+트리(리프만 데이터/범위쿼리) vs B-트리(모든 노드 데이터/단일쿼리)

연관: B-트리, 데이터베이스 인덱스, 범위 쿼리, 디스크 I/O