B-Tree 인덱스

B-Tree 인덱스

균형 잡힌(Balanced) 다진(Multi-way) 트리 구조로, 검색·삽입·삭제 시 O(log n)의 시간 복잡도를 보장하는 자기 균형 탐색 트리 인덱스

특징

• •모든 리프 노드가 같은 깊이 (균형 트리)
• •하나의 노드에 여러 키 저장 (다진 트리)
• •동등 검색과 범위 검색 모두 지원
• •키가 정렬된 상태로 유지

구조

• •루트 노드(Root): 트리의 시작점
• •브랜치 노드(Branch/Internal): 중간 노드, 키와 포인터
• •리프 노드(Leaf): 최하위 노드, 실제 데이터 또는 ROWID

특성 (차수 m인 B-Tree)

• •루트: 최소 2개 자식
• •내부 노드: 최소 ⌈m/2⌉개 자식
• •모든 리프: 같은 레벨
• •키는 정렬된 상태 유지

검색 시간복잡도: O(log n)

적용사례: OLTP 시스템, 범위 쿼리, 정렬이 필요한 쿼리

비교: B-Tree(균형/다진) vs 이진트리(불균형 가능/2진)

연관: B+Tree, 인덱스, 균형 트리