B트리 삽입, 삭제 도식화와 좀 특이한 방식 분석

BTree.mht

위 파일은 인터넷서 얻은 도식화 파일이다. 그림으로 설명이 참 깔끔하게 잘 된듯 하다.
참조... http://swblog.net/entry/B-Tree
B트리의 처리 방식은 제각각인 듯 하다. B트리의 원칙만 잘 지키면 되는 듯 하다.

삽입의 경우 좀 특이하게 처리했던 경우는(이재규 알고리즘 강좌)
일단 위에서부터 아예 포화상태에 놓인 경우(5차원시 노드에 5개 요소가 있는경우)
먼저 분할시키면서 아래로 내려와서 마침내 들어갈 자리를 찾으면 해당 노드에 요소를 삽입하는 방식이다.
이때문에 해당 노드에서 분할시에 부모가 오버플로우될 상황은 없다.(부모노드 요소의 갯수는 모두 4개 이하이므로)

다른 방식은 위 도식화에서 표현하듯이 저질러놓고 수습하는 방식인 데 이게 일반적인 경우인 듯 하다.
일단 해당 값이 들어갈 노드를 찾고 값을 삽입 후 그 노드가 오버플로우 상황이 되면 분할하는 방식이다.
분할하면 부모노드에 한개의 요소가 추가되므로 다시 부모노드를 검사해
부모노드가 오버플로우인지 확인하는 작업이 계속 진행되어야 할 것이다. 오버플로우이면 다시 분할하고
이 경우 부모의 부모노드 역시 요소 한개가 추가되므로 그 노드 계속 검사해야 할 필요가 있을 것이다.
이처럼 상향식으로도 처리가능하다.

위 두 방식을 비교하자면
최종 삽입할 노드에 여분의 들어갈 공간이 있는 경우에는 분할은 일어나지 않으므로
전자처럼 윗 노드들에 예비작업을 해 놓는 방식은 불필요한 작업이 될 수도 있다.
다만 분할이 일어나게 되는 상황이면 전자의 방법이 약간 시간상 이득이 될 것이다.
(후자의 방법은 다시 거슬러 올라가면서 조사해야 하므로 좀 더 오버헤드가 있을 것이다.)


삭제의 경우도 기본적인 원칙은 정해져 있지만 구현하는 방법은 다양한 듯 하다.
기본적인 원칙은 borrow(redistribute), bind(merge), swap이다.

주의해야 될 점은  borrow시는 부모노드의 요소의 갯수에는 변화가 없지만
bind시는 자식노드에 녹아들어 1개가 줄어든다.
이 경우 반드시 부모노드의 언더플로우를 체크해야 할 것이다.
부모노드에서도 bind 상황이 발생시 부모노드의 부모도 언더플로우가 발생할 수 있으므로
다시 위와 같은 체크를 해야 할 것이다.(위에서 삽입의 경우 자식에서 거슬러 올라가는 체크와 비슷하다.)

swap의 경우는 tree구조의 대원칙인 우측 서브트리에서 가장 작은 값을 찾아 대체하거나
좌측 서브트리에서 가장 큰 값을 대체하는 식이 있을 것이다. 보통 전자의 방식을 많이 사용하는 듯 하다.
역시 이 경우 대체되는 노드에서는 요소가 한 개 줄어드므로 대체되는 노드에서 언더플로우 체크가 필요하다.

다시 한 번 강조하지만 바인드(bind)상황의 경우 부모노드의 요소는 필수적으로 한 개가 줄어드므로
부모노드의 언더플로우 체크 및 이에 대한 처리(borrow나 bind)를 해야한다. 부모노드에 바인드 상황이
발생하면 부모노드의 부모노드 역시 언더플로우 체크 및 이에 대한 처리를 해야 한다.
최악의 경우 root까지 거슬러 올라갈 수 있을 것이다. 위 도식화된 과정이 이를 잘 보여주고 있다.

참고로 전술한 삽입의 특수한 경우처럼 부모노드들에 대해 미리 예비작업을 해 놓는 방식이 있다.
이 경우는 아예 삭제 키를 찾으러 내려오는 과정에서 갯수가 m/2개 이하(미만이 아니라 이하임의 주의) 노드들은
borrow나 bind 작업을 통해 적어도 m/2+1개로 만들어 버린다.(이재규 알고리즘 강좌)
부모노드의 요소 갯수가 m/2+1개 이상이면 하위 자식노드에서 bind 상황이 발생해도 적어도 m/2개는 유지하므로
언더플로우는 절대 발생하지 않을 것이다.
마침내 해당 키값이 있거나 스왑키가(내부노드의 키 삭제시 말단으로 스왑되었을 겅시다.) 착출되었던
말단 노드 레벨에 도달하면 키를 삭제하면 된다. 해당 말단 레벨에서 언더플로우이면 borrow나 bind해주면 된다.
bind 과정이 일어나더라도 부모노드에 이미 선수작업을 해놨으므로 언더플로우는 발생하지 않는다.

이러한 방식은 선처리 삽입의 경우에서와  유사하게
말단 노드에서 bind 작업이 일어나는 경우 다시 거슬러 탐색하는 시간만큼의  이득을 볼 수 있으나
삭제될 키가 발견되지 않거나 bind가 발생하지 않는 상황에서도 무조건 위의 선처리 작업을 하면서 내려오므로,,,
;;;; 약간 오바스럽기도 하다.