B-Tree (2)

앞선 포스트에서 설명한 B-Tree에 이어 서술합니다.

 

B-Tree의 자손노드는 B-Tree의 가장 하단의 노드 레벨로, B-Tree의 단말 레벨의 +1값과 동치입니다.

자손노드의 특징으로는, Root 노드와 단말 노드 이외의 모든 노드들은 ceil(m/2) 개의 자손 노드를 가진다는 특징이 있습니다.

 

B-Tree에서 중복을 없애기 위해 B-Tree 각 노드에 키와 데이터 레코드에 대한 주소를 포함합니다. 이 방법을 사용하여 중복을 방지하고 공간을 절약하며, 검색시간을 단축하지만 내부 노드의 크기가 증가하는 단점을 포함합니다.

 

B-Tree의 특성을 정리하자면 다음과 같습니다.

• 모든 노드는 최대 m개의 자손 노드를 가집니다.
• 루트와 단말 노드 이외의 모든 노드는 최소 ceil(m/2)개 이상의 자손노드를 가집니다.
• 루트 노드는 최소 2개의 자손노드를 가질 수 있습니다.
• 모든 단말 노드들은 같은 레벨을 유지합니다.
• 단말 레벨의 노드들은 데이터 파일에 대한 완전한 정렬된 형태를 표현합니다.

N개의 키를 가지는 B-Tree의 최악의 검색 깊이는 다음으로 정의 됩니다.

 

N >= 2 * ceil(m/2)^(d-1)

 

삭제 연산은 삽입과 반대로 진행하며, Underflow가 발생했을 때, 합병(Merging) 혹은 재분배(Redistribution) 중 선택하여 진행합니다. 합병은 이웃노드와 진행하고, 재분배는 합병이 안되는 경우 선택합니다. 삭제에도 삽입처럼 Special Case가 존재하는데, 루트가 Underflow가 발생할 경우 합병 혹은 재분배를 통해 Level Down이 발생합니다.

 

재분배 우선으로 삽입할 경우, 노드의 분리를 피하거나 지연시켜서 Overflow 시 초과된 키를 이웃 노드로 이동시켜 노드의 공간 활용도가 올라가는 효과를 볼 수 있습니다. 실제로 1 - 2 Node Split의 경우 50%의 공간 활용도, 평균적으로 67%를 보여주지만, 재분배 우선으로 삽입할 경우 평균적으로 86%의 공간활용도를 보여줍니다.