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"이므로, K = "Califieri"이고, P -> ("Califieri"로 시작하는 노드)인 항목의 쌍을 부모 노드에 삽입해야 한다. Figure 3는 삽입 후의 B⁺트리를 보여준다. 이 경우 부모 노드에는 새 항목을 저장할 공간이 있었으므로, 추가적인 분할없이 가능했다. 만약 공간이 없었다면 부모 노드도 분할해야 하며, 이 경우, 부모의 부모에도 항목을 삽입해야 한다. 최악의 경우에는 root까지의 모든 노드가 분할되어야 할 수 있으며, root 노드가 분할되어야 할 수 있으며, 루트가 분할되면 전체 트리의 높이(height)는 1 증가한다.

non-leaf 노드의 분할은 leaf 노드의 분할과는 약간 다르다. Figure 4는 figure 3에 "Lamport" 키 값을 가진 레코드를 삽입한 결과를 보여준다. "Lamport"가 삽입될 리프 노드는 이미 "Gold", "Katz", "Kim" 항목을 포함하고 있어 분할이 필요하다. 분할 결과 생성된 오른쪽 노드에는 "Kim"과 "Lamport"가 들어간다. 이 경우 (Kim, n1) 항목이 부모 노드에 추가되어야 하며, 여기서 n1은 새 노드를 가리키는 포인터이다. 그러나 부모 노드에 공간이 없기 때문에, 부모 노드도 분할해야 한다. 이때 부모 노드는 임시로 확장되어 항목을 추가한 후, 과도한 항목 수를 분할하여 처리한다.
non-leaf 노드를 분할할 때는, 자식 노드를 지시하는 포인터들을 기존의 노드와 새로 생성된 노드 사이에 나누어 배치한다. Figure 4에서는 기존의 노드가 첫 세개의 포인터를 유지하고, 새 노드는 나머지 두 개의 포인터를 가진다. 하지만 기존 노드에서의 검색키값은 이와 조금 다르게 처리된다. 새 노드로 이동된 포인터들 사이에 있는 검색 키 값들("Kim")은 해당 포인터들과 함께 이동한다. 반면, 기존 노드에 그대로 남아 있는 포인터들 사이에 있는 키 값들("Califieri", "Einstein")은 그대로 남는다. 이때, 기존 노드에 남는 포인터들과 새 노드로 이동하는 포인터들 사이에 위치한 검색 키 값("Gold")은 별도로 처리된다. 이는 어느 노드에도 삽입되지 않고, (Gold, n2) 항목으로 상위 부모 노드에 삽입되며, 여기서 n2는 새로 생성된 노드를 가리키는 포인터이다. 이 예제에서 부모 노드는 루트이고, 새 항목을 위한 공간이 충분했다. 아래는 B⁺트리에 대한 일반적인 삽입 기법이다.

1. 삽입이 이루어져야 할 리프 노드 l을 결정한다.
2. 분할이 발생하면, 새로 생성된 노드를 l의 부모에 삽입한다.
3. 이 삽입으로 인해 또다시 분할이 발생하면, 이를 트리 위로 재귀적으로 반복하며 처리한다.
4. 삽입이 더 이상 분할을 유발하지 않거나, 새로운 root 노드가 생성될 때까지 이 과정을 반복한다.

아래는 이 알고리즘을 의사 코드로 나타낸 것이다:

procedure insert(value K, pointer P)
    if (tree is empty) create an empty leaf node L, which is also the root
    else Find the leaf node L that should contain key value K

    if (L has less than n − 1 key values)
        then insert_in_leaf(L, K, P)
    else begin /* L has n − 1 key values already, split it */
        Create node L'
        Copy L.P₁ … L.Kₙ₋₁ to a block of memory T that can hold n (pointer, key-value) pairs
        insert_in_leaf(T, K, P)
        Set L'.Pₙ = L.Pₙ ; Set L.Pₙ = L'
        Erase L.P₁ through L.Kₙ₋₁ from L
        Copy T.P₁ through T.K[⌈n/2⌉] from T into L starting at L.P₁
        Copy T.P[⌈n/2⌉+1] through T.Kₙ from T into L' starting at L'.P₁
        Let K' be the smallest key-value in L'
        insert_in_parent(L, K', L')
    end

위 의사 코드에서 L, N, P, T는 노드를 가리키는 포인터이며, L은 leaf 노드를 나타낸다. L.Ki와 L.Pi는 각각 노드 L의 i번째 키 값과 포인터를 의미하며, T.Ki 및 T.Pi도 마찬가지이다. 의사코드는 또한 노드 N의 부모를 찾기 위한 함수 parent(N)을 사용한다. 또한 insert in parent 절차는 인자로 N, K′, N′을 받으며, 여기서 노드 N이 N과 N′으로 분할되었고, K′는 N′에서의 최소 키 값이다. 이 절차는 노드 N의 부모를 갱신하여 분할을 기록한다. insert into index와 insert in parent 절차는 노드 분할 시 내용을 임시 메모리 영역 T에 저장하여 처리한다. 절차는 수정하여 분할된 노드에서 새 노드로 데이터를 직접 복사하도록 최적화할 수 있지만, 임시 공간 T를 사용하면 절차를 단순화할 수 있다.