Update of B+-Trees

개요

레코드(Record)가 릴레이션(relation)에 삽입/삭제(insert/delete)될 때, 해당 릴레이션에 대한 인덱스들도 이에 맞게 갱신되어야 한다. 이때 레코드에 대한 갱신(upadate) 작업은 기존 레코드를 삭제한 후, 그 위치에 갱신된 레코드를 삽입하는 것으로 수행될 수 있다. 따라서 삽입/삭제 작업만을 고려하면 된다. 이때 삽입과 삭제 작업은 조회(lookup)보다 더 복잡한데, 삽입 결과로 노드가 너무 커질 경우, 분할(split)이 필요하고, 삭제 결과로 노드가 너무 적어질 경우(⌈n/2⌉ 포인터보다 적은 경우)에는 노드 사이의 결합이 필요할 수 있기 때문이다. 이때 노드를 분할하거나 병합할 때는 트리의 균형(balance)이 유지되도록 해야 한다.

B⁺-트리에서의 삽입과 삭제 개념을 소개하기 위해, 먼저 노드가 너무 커지거나 작아지지 않는다고 잠정적으로 가정해보자. 이 가정 하에서는 삽입과 삭제가 다음과 같이 수행된다:

• 삽입: find() 함수에서 사용한 것과 동일한 기법을 이용하여, 삽입하려는 검색키 값을 포함할 leaf 노드를 찾는다. 그런 다음, 해당 leaf 노드에 (검색키 값, 레코드 포인터) 형태의 항목을 삽입하며, 검색키 값들이 정렬 순서를 유지하도록 위치를 조정한다.
• 삭제: find()와 동일한 방식으로 삭제할 항목이 포함된 리프 노드를 찾는다. 검색 키 값이 동일한 여러 항목이 있는 경우, 삭제할 레코드를 가리키는 항목을 찾을 때까지 이들을 탐색한다. 그런 다음 해당 항목을 리프 노드에서 제거한다. 삭제된 항목 오른쪽에 있는 모든 항목은 한 칸씩 왼쪽으로 이동하여 빈 공간이 없도록 한다.

이제 노드 분할과 병합을 포함한 일반적인 삽입과 삭제 경우를 알아보아야 한다.

Insertion

노드를 분할해야 하는 삽입 예제를 고려하기 위해, name 속성의 값이 "Adams"인 레코드를 instructor 릴레이션에 삽입한다고 하자. 그러기 위해서는 Figure 1의 B⁺트리에 "Adams" 항목을 삽입해야 한다. 이때 find() 함수에서의 알고리즘에서의 동일한 방식을 사용하면 Adams"는 "Brandt", "Califieri", "Crick"을 포함하는 leaf 노드에 들어가야 한다. 하지만 이 leaf 노드에는 "Adams"를 삽입할 공간이 없으므로, 해당 leaf 노드는 두개의 노드로 분할되어야 한다. Figure 2는 "Adams" 삽입으로 인해 leaf 노드가 분할된 모습을 보여준다. "Adams"와 "Brandt"는 하나의 리프에, "Califieri"와 "Crick"은 다른 리프에 위치한다.

일반적으로는 n개의 검색키 값(리프 노드의 n−1개 키 값 + 삽입하려는 값)에서, 처음 ⌈n/2⌉ 개를 기존 노드에 유지하고 나머지를 새로 생성된 노드에 넣는다. 이때 leaf 노드를 분할한 이후에는 새 leaf 노드를 B⁺-트리 구조에 삽입해야 한다. 이 예제에서는 새 노드의 최소 검색키 값이 "Califieri"이므로, 이 값을 키로 하고 새 노드에 대한 포인터를 값으로 하는 항목을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B⁺트리를 보여준다.