B-트리에서의 삭제는 삽입과 유사하나 이보다 조금 더 복잡하다. 이는 리프(leaf) 노드만이 아닌, 임의의 노드에서 키가 삭제될 수 있으며, 내부 노드에서의 삭제는 자식 노드들에 대한 재배열을 요구하게 되기 때문이다. 삽입에서의 삭제 시에도 B-트리의 특성에 위반되는 구조를 갖는 트리가 만들어지는 것을 방지할 수 있어야 한다. 삽입 때문에 한 노드가 너무 커지지 않도록 보장하는 것처럼, 삭제로 인해 한 노드가 너무 작아지지 않는 것을 보장할 수 있어야 한다(루트 노드가 최대 2t - 1개를 초과하는 키들을 갖는 것이 허용되지 않더라도 루트 노드는 최소 t - 1개 미만의 키를 갖는 것이 혀용되는 것만 제외하면). 간단한 삽입 알고리즘에서 키가 삽입될 경로 내의 노드가 이미 가득 찬 경우 되돌아 가야 할 수도 있는 것처럼, 간단한 삭제 방법도 삭제되어야 할 경로상의 노드가(루트 노드가 아닌) 키들의 개수가 최소일 경우 다시 되돌아 가야 할 지도 모른다.
B-Tree-Delete 프로시저가 키 k를 x가 루트인 서브 트리로부터 삭제한다고 가정한다. 이 프로시저는 언제나 B-Tree-Delete가 노드 x에 대해 재귀적으로 호출될 때마다 x에 있는 키들의 수가 적어도 최소 t가 됨을 보장하도록 설계되었다. 이 조건은 일반적인 B-트리 조건에서 요구되는 최소의 키보다 한 개 더 많은 키를 요구하는 것임을 주의하라. 따라서 가끔은 자식 노드에 대해 재귀적인 호출을 하기 전에 키가 자식 노드로 옮겨져야만 하는 상황이 발생하기도 한다. 이러한 강화된 조건은 우리가 "되돌아 갈" 필요 없이(나중에 이야기하겠지만 한가지 예외가 있다) 한번의 하향식 패스 시에 트리에서 하나의 키를 삭제할 수 있도록 해 준다. 아래의 B-트리에서의 삭제에 대한 명세는 다음의 이해를 기반하여 해석되어야 한다. 만약, 루트 노드 x가 하니도 없는 내부 노드가 되는 경우가 발생할 때(이 상황은 아래의 2c와 3b 경우에 발생할 수 있다) x는 삭제되고 x의 유일한 자식 노드 c(1)[x]는 트리의 새로운 루트 노드가 되어, 트리의 높이가 하나 낮아지게 되면서, 트리가 비어 있지 않은 한 루트 노드가 최소 한 개의 키를 가져야 한다는 특성을 유지시켜 준다.
의사코드를 제공하는 대신에 삭제 작업이 어떻게 이루어지는지 간략히 설명해 보자. 그림 18.8은 B-트리에서의 키를 삭제하는 다양한 경우를 설명하고 있다.
1. 만약 키 k가 노드 x에 있고 x가 리프 노드라면, 키 k를 x에서 삭제한다.
2. 만약, 키 k가 노드 x에 있고 x가 내부 노드라면, 다음과 같이 처리한다.
a. 만약, x 노드의 키 k의 바로 직전에 오는 자식 노드 y가 최소 t개의 키를 가진다면, k의 선행 키인 k'을 y를 루트로 하는 서브 트리에서 찾아 낸다. 재귀적으로 k'을 삭제하고, x의 k'으로 치환한다(k'을 찾는 것과 이를 삭제하는 것은 한 번의 하향식 패스만에 이루어 질 수 있다).
b. 대칭적으로 만약, 노드 x의 키 k의 바로 직후에 오는 자식 노드 z가 최소 t개의 키를 가진다면, k의 후행 키인 k'을 z를 루트로 하는 서브 트리에서 찾아 낸다. 재귀적으로 k'을 삭제하고, x의 k를 k'으로 치환한다(k'을 찾는 것과 이를 삭제하는 것은 한번의 하향식 패스만에 이루어 질 수 있다).
c. 이외의 경우에서는, 즉 만약 y와 z가 모두 단지 t - 1개의 키를 갖는다면, k와 z의 모든 키들을 y로 병합한다. 따라서 x는 k와 z에 대한 포인터 두가지를 잃게 되고, y는 이제 2t - 1개의 키를 갖게 된다. 이제 z를 제거하고, 재귀적으로 y에서 k를 삭제한다.
3. 만약, 키 k가 내부 노드 x에 있지 않다면, k가 트리에 존재할 경우 k를 반드시 포함하게 되는 서브 트리의 루트 c(i)[x]를 결정한다. 만약, c(i)[x]가 단지 t - 1개의 키를 가졌다면, 최소 t개의 키를 가지는 노드에게 재귀적 호출을 할 수 있음을 보장할 수 있도록 하기 위해 필요한 단계 3a 또는 3b를 실행한다. 그 후, x의 해당 자식 노드에서 재귀적으로 호출 함으로써 작업을 마치게 된다.
a. 만약, c(i)[x]가 단지 t - 1개의 키를 가졌으나 최소 t개의 키를 가진 인접한(immediate) 형제 노드가 있다면, 다음과 같이 c(i)[x]에게 하나의 키를 더해준다. x의 키(c(i)[x]와 해당 형제 노드에 연관된)를 c(i)[x]로 내려 주고, c(i)[x]의 인접한 해당 왼쪽 도는 오른쪽 형제 노드의 키를 x로 올려 준다. 이때 올려주는 키에 연관된 자식 노드에 대한 포인터ㄹ는 그 인접한 형제로부터 c(i)[x]로 옮겨 준다.
b. 만약, c(i)[x]와 c(i)[x]의 양쪽 인접한 형제 노드가 모두 t - 1개의 키를 가지고 있다면, c(i)[x]에, x로부터 c(i)[x]로 키 한 개를 움직이고 c(i)[x]의 바로 왼쪽 또는 오른쪽 형제에서 키 한 개를 x로 올려주고 해당되는 자식 포인터를 그 형제에서 c(i)[x]로 옮겨줌으로써, 한개의 키를 더해준다.
B-트리의 대부분의 키들은 리프 노드에 있기 때문에, 실제적으로 삭제 연산은 리프 노드에서 가장 빈번하게 발생할 것이라고 기대할 수 있다. 이때 B-Tree-Delete 프로시저는 다시 위로 올라가는 일 없이 트리에서 한 번의 하향식 패스만에 수행될 수 있다. 그러나 내부 노드에서 키를 삭제할 경우에는 그 프로시저가 한번의 하향식 패스 외에 삭제되는 키를 그것의 선행키 또는 후행키로 치환하기 위해(2a와 2b의 경우에서처럼) 다시 해당 노드로 되돌아 와야 하는 경우가 발생할 수 있다.
삭제 연산이 복잡해 보이기는 하나, 삭제 연산은 h의 높이를 가지는 B-트리에 대해 단지 O(h)번의 디스크 연산만을 사용하게 된다. 이는 그 프로시저의 재귀적 호출들 간에, O(1)회만의 Disk-Read와 Disk-Write 함수가 호출되기 때문이다. 요구되는 CPU 시간은 O(th) = O(log(base t)(n))이 된다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein, Introduction to Algorithms Second Edition, The MIT Press
B-Tree-Delete 프로시저가 키 k를 x가 루트인 서브 트리로부터 삭제한다고 가정한다. 이 프로시저는 언제나 B-Tree-Delete가 노드 x에 대해 재귀적으로 호출될 때마다 x에 있는 키들의 수가 적어도 최소 t가 됨을 보장하도록 설계되었다. 이 조건은 일반적인 B-트리 조건에서 요구되는 최소의 키보다 한 개 더 많은 키를 요구하는 것임을 주의하라. 따라서 가끔은 자식 노드에 대해 재귀적인 호출을 하기 전에 키가 자식 노드로 옮겨져야만 하는 상황이 발생하기도 한다. 이러한 강화된 조건은 우리가 "되돌아 갈" 필요 없이(나중에 이야기하겠지만 한가지 예외가 있다) 한번의 하향식 패스 시에 트리에서 하나의 키를 삭제할 수 있도록 해 준다. 아래의 B-트리에서의 삭제에 대한 명세는 다음의 이해를 기반하여 해석되어야 한다. 만약, 루트 노드 x가 하니도 없는 내부 노드가 되는 경우가 발생할 때(이 상황은 아래의 2c와 3b 경우에 발생할 수 있다) x는 삭제되고 x의 유일한 자식 노드 c(1)[x]는 트리의 새로운 루트 노드가 되어, 트리의 높이가 하나 낮아지게 되면서, 트리가 비어 있지 않은 한 루트 노드가 최소 한 개의 키를 가져야 한다는 특성을 유지시켜 준다.
의사코드를 제공하는 대신에 삭제 작업이 어떻게 이루어지는지 간략히 설명해 보자. 그림 18.8은 B-트리에서의 키를 삭제하는 다양한 경우를 설명하고 있다.
1. 만약 키 k가 노드 x에 있고 x가 리프 노드라면, 키 k를 x에서 삭제한다.
2. 만약, 키 k가 노드 x에 있고 x가 내부 노드라면, 다음과 같이 처리한다.
a. 만약, x 노드의 키 k의 바로 직전에 오는 자식 노드 y가 최소 t개의 키를 가진다면, k의 선행 키인 k'을 y를 루트로 하는 서브 트리에서 찾아 낸다. 재귀적으로 k'을 삭제하고, x의 k'으로 치환한다(k'을 찾는 것과 이를 삭제하는 것은 한 번의 하향식 패스만에 이루어 질 수 있다).
b. 대칭적으로 만약, 노드 x의 키 k의 바로 직후에 오는 자식 노드 z가 최소 t개의 키를 가진다면, k의 후행 키인 k'을 z를 루트로 하는 서브 트리에서 찾아 낸다. 재귀적으로 k'을 삭제하고, x의 k를 k'으로 치환한다(k'을 찾는 것과 이를 삭제하는 것은 한번의 하향식 패스만에 이루어 질 수 있다).
c. 이외의 경우에서는, 즉 만약 y와 z가 모두 단지 t - 1개의 키를 갖는다면, k와 z의 모든 키들을 y로 병합한다. 따라서 x는 k와 z에 대한 포인터 두가지를 잃게 되고, y는 이제 2t - 1개의 키를 갖게 된다. 이제 z를 제거하고, 재귀적으로 y에서 k를 삭제한다.
3. 만약, 키 k가 내부 노드 x에 있지 않다면, k가 트리에 존재할 경우 k를 반드시 포함하게 되는 서브 트리의 루트 c(i)[x]를 결정한다. 만약, c(i)[x]가 단지 t - 1개의 키를 가졌다면, 최소 t개의 키를 가지는 노드에게 재귀적 호출을 할 수 있음을 보장할 수 있도록 하기 위해 필요한 단계 3a 또는 3b를 실행한다. 그 후, x의 해당 자식 노드에서 재귀적으로 호출 함으로써 작업을 마치게 된다.
a. 만약, c(i)[x]가 단지 t - 1개의 키를 가졌으나 최소 t개의 키를 가진 인접한(immediate) 형제 노드가 있다면, 다음과 같이 c(i)[x]에게 하나의 키를 더해준다. x의 키(c(i)[x]와 해당 형제 노드에 연관된)를 c(i)[x]로 내려 주고, c(i)[x]의 인접한 해당 왼쪽 도는 오른쪽 형제 노드의 키를 x로 올려 준다. 이때 올려주는 키에 연관된 자식 노드에 대한 포인터ㄹ는 그 인접한 형제로부터 c(i)[x]로 옮겨 준다.
b. 만약, c(i)[x]와 c(i)[x]의 양쪽 인접한 형제 노드가 모두 t - 1개의 키를 가지고 있다면, c(i)[x]에, x로부터 c(i)[x]로 키 한 개를 움직이고 c(i)[x]의 바로 왼쪽 또는 오른쪽 형제에서 키 한 개를 x로 올려주고 해당되는 자식 포인터를 그 형제에서 c(i)[x]로 옮겨줌으로써, 한개의 키를 더해준다.
B-트리의 대부분의 키들은 리프 노드에 있기 때문에, 실제적으로 삭제 연산은 리프 노드에서 가장 빈번하게 발생할 것이라고 기대할 수 있다. 이때 B-Tree-Delete 프로시저는 다시 위로 올라가는 일 없이 트리에서 한 번의 하향식 패스만에 수행될 수 있다. 그러나 내부 노드에서 키를 삭제할 경우에는 그 프로시저가 한번의 하향식 패스 외에 삭제되는 키를 그것의 선행키 또는 후행키로 치환하기 위해(2a와 2b의 경우에서처럼) 다시 해당 노드로 되돌아 와야 하는 경우가 발생할 수 있다.
삭제 연산이 복잡해 보이기는 하나, 삭제 연산은 h의 높이를 가지는 B-트리에 대해 단지 O(h)번의 디스크 연산만을 사용하게 된다. 이는 그 프로시저의 재귀적 호출들 간에, O(1)회만의 Disk-Read와 Disk-Write 함수가 호출되기 때문이다. 요구되는 CPU 시간은 O(th) = O(log(base t)(n))이 된다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein, Introduction to Algorithms Second Edition, The MIT Press