[인덱스] MySQL B+Tree 인덱스 구조와 데이터 검색 원리

 

B+Tree 인덱스란

개념

검색값을 빠르게 찾을 수 있도록 데이터를 정렬하고, 여러 단계의 페이지로 나누어 관리하는 트리 구조 

검색값과 기준값 비교

→ 검색값이 포함된 하위 범위로 이동

→ 범위를 반복해서 축소

→ 마지막 페이지에서 값 확인 

 

구조

구성 요소	역할
루트 노드	검색을 시작하는 최상위 페이지 → 검색값이 어느 하위 범위에 들어가는지 판단
브랜치 노드	- 검색 범위를 더 작게 나누고, 이동해야 할 다음 페이지를 안내한다. - 실제 데이터가 많아지면, 여러 개의 브랜치 노드가 추가될 수 있음.
리프 노드	실제 인덱스 항목이 저장되는 마지막 페이지

 

정렬된 값: 10, 20, 30, 40, 50, 60, 70, 80

루트 노드

30  |  60

↙        ↓        ↘

10 | 20	30 | 40 | 50	60 | 70 | 80
30 미만	30 이상 60 미만	60 이상

50을 찾는 과정
① 루트 노드에서 30 이상 60 미만 범위 선택
② 가운데 리프 노드로 이동
③ 30 | 40 | 50에서 50 확인

 

사용하는 이유

검색 범위를 빠르게 줄일 수 있음

각 단계에서 검색값이 존재할 수 없는 범위를 제외하면서 읽어야 하는 데이터의 범위를 줄임

 

트리의 높이를 낮게 유지할 수 있음

한 노드에는 하나의 기준값만 저장되는 것이 아니라 여러 개의 키와 하위 페이지 정보가 저장될 수 있음

→ 한 단계에서 여러 범위 구분

→ 트리 높이를 낮게 유지

→ 리프 노드까지 거쳐야 하는 페이지 수 감소

 

ex) 

[ 30 | 60 ]

위 노드 하나만 확인해도 전체 데이터를 세 범위로 나눌 수 있음

- 30 미만

- 30 이상 60 미만

- 60 이상 

 

 

범위 검색에 유리함

리프 노드는 인덱스 값의 정렬 순서대로 연결되어 있음.

 

---

 

리프 노드에 저장되는 정보

 

실제 인덱스 항목이 저장되지만, 저장되는 내용은 인덱스 종류에 따라 다름

 

인덱스 종류	리프 노드에 저장되는 정보
클러스터드 인덱스	기본 키와 실제 행 데이터 기본 키로 리프 노드 탐색 → 리프 노드에서 실제 행 데이터 확인
보조 인덱스	보조 인덱스 컬럼값과 해당 행의 기본 키 보조 인덱스에서 검색값 탐색 → 리프 노드에서 기본 키 확인 → 해당 기본키로 실제 행을 다시 조회

 

---

 

B+Tree와 페이지의 관계

 

실제 데이터베이스는 각각 인덱스 페이지 단위로 관리됨.

 

일반적인 인덱스 탐색 과정

1. 루트 인덱스 페이지 읽기
2. 검색값이 포함된 하위 범위 확인
3. 필요한 브랜치 페이지 읽기
4. 리프 페이지의 인덱스 항목 확인

=> 전체 인덱스 페이지를 모두 읽는 것이 아니라, 검색값이 있는 위치로 이어지는 경로의 페이지를 중심으로 탐색함.