-
KDB 트리 삽입과 삭제)
KDB 트리의 삽입 처리는 B 트리와 유사하게 처리가 진행된다. 먼저, 적절한 리프 노드를 찾고 해당 노드에 공간이 있으면 (키, 페이지 번호) 쌍을 삽입하고 종료한다.
해당 노드에 공간이 없는 경우 형제 노드를 확인하여 재분배하고 종료한다.
만약 재분배가 불가능한 경우리프 노드를 분할하고 분할된 말단 노드를 가리킬 새로운 노드를 부모 노드에 삽입한다.
이 때 부모 노드에 공간이 있으면 그대로 종료하고 아니면 부모 노드를 기준으로 새롭게 처리를 진행한다.
특정 노드가 분할되어 부모 노드에 할당됐을 때 공간을 수용할 수 없는 경우 분할된 기준을 부모 노드에 적용하여 두 노드로 분할한다.
쉽게 배우는 알고리즘 KDB 트리 그림 5-28 삭제의 경우도 기본적으로 B 트리의 처리와 비슷하게 진행되며 병합의 처리가 부모 노드에서도 언더 플로우 발생으로 이어지는 경우 무모 노드를 기준으로 언더 플로우 처리를 진행한다.