루트 / 브랜치 페이지
경계 키
30
60
B+Tree
B+Tree는 리프에 실제 인덱스 항목을 모은다
내부 노드는 길 안내용 경계 키를 들고, 리프 노드는 정렬된 키와 행 위치 정보를 보관한다. 범위 검색은 리프 연결을 따라 옆 페이지로 이어진다.
Leaf A
< 30
10
20
10, 20
행 위치
Leaf B
30-59
30
40
50
30, 40, 50
행 위치
Leaf C
≥ 60
60
70
80
60, 70, 80
행 위치
key BETWEEN 40 AND 70 조건은 Leaf B에서 시작해 Leaf C로 이어진다. 그래서 B+Tree는 단건 탐색뿐 아니라 범위 검색에도 강하다.
리프에 무엇이 들어가는가
Oracle
인덱스 키와 ROWID를 리프 엔트리에 둔다.
PostgreSQL
키와 heap tuple 위치인 TID를 둔다.
InnoDB 보조
보조 인덱스 리프에 기본 키 값을 함께 둔다.
InnoDB 클러스터드
기본 키 순서의 리프가 실제 행 데이터에 가깝다.
탐색이 읽는 페이지 순서
01
루트
경계 키 30, 60을 보고 어느 범위인지 고른다.
02
리프
정렬된 키와 locator를 찾고 필요한 행으로 이동한다.
03
옆 리프
범위 검색이면 다음 리프 페이지로 순서대로 넘어간다.