트리 인덱스, B- B+

인덱싱 :데이터를 빠르게 찾고 정렬하기 위한 기술

 

트리 인덱스란?

데이터를 트리 구조로 구성한 인덱스, 데이터가 정렬된 상태로 유지되며, 탐색(Search), 삽입(Insert), 삭제(Delete) 같은 연산을 빠르게 수행

대부분의 관계형 데이터베이스(RDBMS)에서 사용되며, 데이터의 범위 검색, 정렬된 출력, 빠른 키 기반 검색에 유리

 

B-Tree 인덱스 구조

균형 이진 트리를 확장한 구조로, 하나의 노드에 여러 개의 키와 자식 노드를 포함

 

• 트리의 모든 리프 노드는 같은 깊이
• 노드는 key 값과 함께 자식 노드를 가리키는 포인터를 가지고 있음
• 삽입과 삭제 시 트리가 자동으로 균형을 맞춤
• 검색할 때 범위를 반씩 줄여가며 O(log n) 시간

 

B+Tree 인덱스 구조

B-Tree를 개선한 구조로, 실제 데이터를 리프 노드에만 저장하는 것이 가장 큰 특징

 

• 중간 노드는 오직 키와 포인터만 보관 (데이터 없음)
• 모든 데이터는 리프 노드에만 존재
• 리프 노드가 순차 연결(Linked List) 되어 있어 범위 검색이 빠름

 

항목	B-Tree	B+Tree
데이터 저장 위치	모든 노드	리프 노드에만
중간 노드 역할	키 + 데이터	키만 (인덱스 전용)
순차 접근	비효율적	효율적 (리프 연결)
범위 쿼리 성능	낮음	높음
사용 예시	드뭄	대부분의 DB (MySQL, Oracle 등)

 

 

* 대부분의 DBMS (MySQL InnoDB, Oracle, PostgreSQL 등)는 B+Tree 인덱스를 기본 인덱스로 사용