B+Tree의 핵심 분리 위쪽은 탐색 경로, 아래쪽은 실제 데이터 위치

내부 노드는 키만 들고 내려갈 방향을 정하고, 리프 노드만 ROWID를 보관합니다.

키만 저장 ROWID = 실제 행 위치
내부 노드 데이터는 없고, 어느 리프로 갈지 안내
[30]
[10 | 20]
[30 | 40 | 50]
↓ 검색 키를 비교해 적절한 리프 구간으로 내려갑니다.
30보다 작은 구간 30 이상인 구간
리프 노드 키와 ROWID가 정렬된 상태로 저장
[10, ROWID]
[20, ROWID]
[30, ROWID]
[40, ROWID]
[50, ROWID]
↔ 리프끼리 양방향으로 이어져 있어 한 번 도착하면 좌우로 연속 읽기가 가능합니다.

왜 DB 인덱스의 표준이 되었나

구조를 둘로 나누면 같은 블록에 더 많은 안내 키를 담을 수 있고, 실제 행 탐색은 정렬된 리프 층에서 처리됩니다.

1. 내부 노드는 가벼워진다

키만 저장하므로 한 노드에 더 많은 분기 키를 넣을 수 있어 팬아웃이 커집니다.

2. 실제 데이터 위치는 리프에 모인다

리프의 ROWID가 실제 데이터 행을 가리켜, 탐색 경로와 데이터 저장 위치가 분리됩니다.

3. 범위 검색이 자연스럽다

시작 리프를 찾은 뒤 연결 리스트를 따라 읽으면 되므로 정렬 조회와 범위 스캔에 유리합니다.

요점: B+Tree는 내부 노드 = 라우팅, 리프 노드 = 키 + ROWID + 순차 연결로 역할을 분리해 디스크 I/O와 범위 검색 비용을 줄입니다.