B-트리(tree)에서의 삽입과 삭제는 모두 리프(leaf)에서의 변경이 위로 전파(propagate)된다는 것이 중요하다. 만약, 루트에서 키를 하나만 가지고 있고, 이 키 값에 대한 삭제가 일어난다면 단지 하나만 제거하고, 그것으로 그만이다.
B-트리의 구현은 여러가지가 있으며, 여기서의 삭제 연산도 그런 구현 중 하나이다. 구체적으로, 여기서의 삭제 연산은 키의 중복을 허용하는 버전의 경우이며, 노드에서의 차수(order)는 하나의 노드가 가질 수 있는 자손(decendant)의 최대 개수를 의미한다. 이 버전에서 노드 n에서 키 k를 삭제하는 규칙은 다음과 같다.
1. 만약 n이 키의 최소 개수 이상이고, 키가 n에서 가장 크지 않다면, 간단히 n에서 k를 삭제한다.
2. 만약 n이 키의 최소 개수 이상이고 k가 n에서 가장 크다면, k를 삭제하고, n의 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨 인덱스(level index)를 변경한다.
3. 만약 n이 정확히 키의 최소 개수를 가지고, n의 형제(sibling) 중의 하나가 충분히 작은 키를 가진다면, 그것의 형제와 n을 합병하고 부모 노드로부터 키를 삭제한다.
4. 만약 n이 정확히 키의 최소 개수를 가지고, 형제 중의 하나가 여분의 키를 가진다면, 형제로부터 n까지 몇 개의 키를 옮김으로써 재분배한다. 그리고 영향받은 노드에 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨의 인덱스를 변경한다.
Reference
Micheal J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addision Wesley
B-트리의 구현은 여러가지가 있으며, 여기서의 삭제 연산도 그런 구현 중 하나이다. 구체적으로, 여기서의 삭제 연산은 키의 중복을 허용하는 버전의 경우이며, 노드에서의 차수(order)는 하나의 노드가 가질 수 있는 자손(decendant)의 최대 개수를 의미한다. 이 버전에서 노드 n에서 키 k를 삭제하는 규칙은 다음과 같다.
1. 만약 n이 키의 최소 개수 이상이고, 키가 n에서 가장 크지 않다면, 간단히 n에서 k를 삭제한다.
2. 만약 n이 키의 최소 개수 이상이고 k가 n에서 가장 크다면, k를 삭제하고, n의 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨 인덱스(level index)를 변경한다.
3. 만약 n이 정확히 키의 최소 개수를 가지고, n의 형제(sibling) 중의 하나가 충분히 작은 키를 가진다면, 그것의 형제와 n을 합병하고 부모 노드로부터 키를 삭제한다.
4. 만약 n이 정확히 키의 최소 개수를 가지고, 형제 중의 하나가 여분의 키를 가진다면, 형제로부터 n까지 몇 개의 키를 옮김으로써 재분배한다. 그리고 영향받은 노드에 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨의 인덱스를 변경한다.
Reference
Micheal J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addision Wesley