차수 3 예시
리프 overflow는 두 리프로 나누고, 오른쪽 첫 키를 부모에 복사해 탐색 기준을 갱신한다.
리프 분할의 핵심은 데이터를 부모로 옮기는 것이 아니라, 리프에는 값을 남겨두고 부모에는 경계 키만
Copy-up
하는 점이다.
1. 삽입
overflow 발생
35가 오른쪽 리프에 들어간다
기존 리프 `[30, 40]`에 35를 넣으면 리프 최대 2개 키를 넘어서 초과 상태가 된다.
30
10
20
30
35
40
왜 분할하나?
리프가 수용 가능한 키 수를 초과했기 때문이다.
2. 리프 분할
값은 리프에 유지
초과 리프를 두 개로 나눈다
`[30, 35, 40]`을 `[30]`과 `[35, 40]`으로 분할한다. 두 값 묶음 모두 리프에 그대로 남는다.
30
→
35
40
리프 연결 리스트 유지
중요
리프 분할은 데이터를 위로 밀어 올리지 않는다. 검색용 경계만 따로 부모에 알려 준다.
3. Copy-up
부모의 경계 갱신
오른쪽 첫 키 35를 부모에 복사한다
부모는 `[30, 35]`가 되고, 이제 35 이상 값은 새 오른쪽 리프로 내려가도록 탐색 경계가 정리된다.
30
35
10
20
30
35
40
결과
부모에는 분기 기준만 추가되고, 실제 데이터는 계속 리프 계층에 남아 있다.