인덱스 구조

B+Tree 인덱스는 리프에 검색 키와 행 위치를 함께 둔다

루트와 중간 노드는 어느 리프로 내려갈지 좁히고, 리프는 정렬된 검색 키와 해당 행을 찾기 위한 위치 정보를 보관한다.

Root 분기 키로 큰 범위를 고른다.

Branch 조건에 맞는 하위 범위를 좁힌다.

Leaf 정렬된 엔트리에서 키를 확인한다.

Row locator로 원본 행을 읽는다.

위에서 범위를 좁히고 리프에서 위치를 얻는다

예: email = lee@shop.com 조건이 어떤 경로로 행 위치를 찾는지 본다.

루트 노드 분기 키

h r

a - h 왼쪽

a d h

i - r 선택

i l r

s - z 오른쪽

s w z

kim@shop.com 이전 리프

검색 키 ROWID 42:8

lee@shop.com 일치

검색 키 PK 1024

park@shop.com 다음 리프

검색 키 페이지 51:2

조건이 좁을수록 테이블 전체를 읽기 전에 후보 행을 빠르게 줄인다.

루트에서 방향 결정

분기 키를 보고 lee@shop.com이 i-r 범위에 있음을 판단한다.

리프에서 키 확인

정렬된 리프 엔트리에서 일치 키를 찾는다.

행 위치로 이동

PK 1024, ROWID, 페이지 포인터 같은 locator로 실제 행을 읽는다.

검색 키

WHERE, JOIN, ORDER BY에서 비교하는 컬럼 값이다.

행 위치

DBMS와 저장 엔진에 따라 ROWID, 기본 키 값, 페이지 포인터가 된다.

원본 행

필요 컬럼이 인덱스에 없으면 locator로 테이블 행을 추가로 읽는다.

트리 탐색 키 비교만으로 읽을 페이지 수를 줄인다.

범위 탐색 리프 시작점을 찾은 뒤 옆 리프를 순서대로 읽는다.

정렬 회피 이미 정렬된 키 순서를 활용해 별도 정렬 비용을 줄인다.