B+Tree

B+Tree는 경계 키로 길을 찾고 리프에서 행 위치를 만난다

내부 키는 리프의 실제 키 범위를 가르는 separator이고, 리프에는 정렬된 키와 row locator가 모인다.

라우팅 키
리프
row locator
30 | 60separator keys
10 | 20leaf: key + locator
30 | 40 | 50leaf: key + locator
60 | 70 | 80leaf: key + locator
separator는 리프 경계값을 길 안내용으로 중복 저장할 수 있다. RID, TID, PK 값, 전체 행 데이터 등 리프 내용은 DBMS와 인덱스 종류에 따라 달라진다.