KDB-Tree (\(k\)-Dimensional B-Tree)
KDB-트리 (\(k\)-차원 B-Tree)
* 검색 트리의 종류 (URL)
Mechanism (원리)
- KDB-Tree에서는 B-Tree와 같이, 한 노드의 크기가 디스크의 한 Page를 담을 수 있을 만큼으로 구성된다.
- 기본적으로, KDB-Tree 또한 B-Tree이기 때문에, 모든 Leaf Node들의 Level은 같다.
Node Structure (노드 구조)
1) 영역 노드 (Region Page)
- 복수 개의 (영역, 페이지 번호) Pair로 구성된다.
(영역 값은 서로 겹치치 않는다.)
- 영역 노드에서의 페이지 번호란, 자식 노드가 위치한 페이지 번호를 의미한다.
- KDB-Tree의 모든 Internal Node는 영역 노드이다.
2) 키 노드 (Point Page)
- 복수 개의 (키, 페이지 번호) Pair로 구성된다.
- 키 노드에서의 페이지 번호란, 실질적인 레코드(정보)가 위치한 페이지 번호를 의미한다.
- KDB-Tree의 모든 Leaf Node는 키 노드이다.
Example. \(k\)-Dimensional KDB-Tree에서의 영역들
\((<min_0, max_0>, <min_1, max_1>, \cdots , <min_{k-1}, max_{k-1}>)\)
- 즉, 각 차원에는 영역이 부여되며, 해당 차원에 위치한 Key들은 해당 영역에 부합되는 값을 가졌음을 의미한다.
Query Operation (검색 연산)
- KDB-Tree에서 임의의 \(\mathrm{Key} \; x\)에 대한 검색 연산은
Root 노드에서 시작하여 \(x\)가 포함되는 영역(Region)을 따라 Leaf Node까지 내려가면 된다.
- 영역값들은 겹치는 부분 없이, 완전 독립적이므로 임의의 \(\mathrm{Key} \; x\)로 도달하는 Leaf는 유일함이 보장된다.
- 도달한 Leaf Node에 \(\mathrm{Key} \; x\)가 있으면, \(x\)에 Mapping된 레코드의 페이지 번호로 Disk에 접근하고,
Leaf Node에 \(\mathrm{Key} \; x\)가 없으면, 검색에 실패한 것이다.
* Region Search (영역 검색)
- 검색하고자 하는 영역에 해당되는 Key에 Mapping된 레코드의 페이지 번호를 모두 찾아내는 연산이다.
Insertion Operation (삽입 연산)
※ KDB-Tree에서의 삽입 연산은 B-Tree에서의 삽입 연산과 같은 원리로 작동된다.
- B-Tree (URL)
- 삽입할 Key가 속할 Leaf Node를 찾은 후, 해당 Leaf Node가 삽입한 Key를 수용할 수 있으면, 삽입한다.
- 해당 Leaf Node가 삽입할 Key를 수용할 수 없다면, 인접한 Sibling Node와 Redistribution한 후 삽입한다.
- 인접한 Sibling Node와 Redistribution조차 불가능하다면, Leaf Node를 두 개로 분할한 후, 한 쪽에 삽입한다.
(하나였던 Leaf Node를 두 개로 분할했으므로, 이 들의 부모 노드의 영역도 둘로 분리되어야 한다.)
(이 때, 부모 노드도 꽉 차 있어 분할할 수 없으면, 그 들의 부모 노드를 분할한다. 즉, 재귀적으로 처리한다.)
Deletion Operation (삭제 연산)
※ KDB-Tree에서의 삭제 연산은 B-Tree에서의 삭제 연산과 같은 원리로 작동된다.
- B-Tree (URL)
- 삭제하고자 하는 Key를 삭제한 후, Underflow가 발생되지 않으면, 그걸로 삭제를 완료한다.
- 삭제 이후, Underflow가 발생했을 경우, 인접한 Sibling Node와 Redistribution을 시도하고,
Redistribution이 불가능한 경우, 두 노드를 Merge한다.
(이 때, Merge 과정에서는 두 노드의 부모 노드에서 영역 통합이 일어나야 한다.)
- 영역 통합을 한 이후, 부모 노드에서 Underflow가 발생하면, 이에 대한 처리를 재귀적으로 처리한다.
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
Reference: K-D-B-tree
(Wikipedia, 2020, URL)
