B-Tree
검색트리가 방대하면 모두 메모리에 올려놓고 사용할 수 없다. 따라서 디스크에 넣어둔 상태로 작업해야 한다. 이는, 외부 검색트리에 해당한다. 외부검색트리일 땐 CPU보다는 디스크 접근 횟수가 효율을 좌우한다. 그리고 트리의 높이를 최소화하는 것이 유리하다.
이는 분기수를 늘리면 다진 검색트리가 되고 높이도 줄어든다. 10억 개의 키값을 가진 이진검색트리는 높이가 30이다. 256개의 분기를 가진 트리는 5의 높이를 갖는다. 이러한 분기는 블럭의 크기를 고려하여 결정한다.
B-Tree는 결국 트리 균형을 유지하여 최악의 경우 디스크 접근 횟수를 줄인다. 또한, 다진검색트리로써 다음과 같은 특성을 갖는다.
- 루트노드를 제외한 모든 노드에서 [k/2]~k개의 키를 갖는다.
- 모든 리프 노드는 똑같은 높낮이 레벨을 갖는다.
삽입, 삭제, 검색 연산에서 O(log n)이지만 균형 잡힌 이진검색트리에 비해 상수인자가 작다.
B-Tree의 노드 구조
자식 노드는 하나의 노드 페이지를 갖는다. 여기서 k의 값은 디스크 블록이 수용할 수 있는 최댓값이 돼야 한다.
key i번째에서 페이지 p i에 접근할 수 있다.
B-Tree 삽입
이번에 B-Tree에서 원소를 삽입하는 과정을 알아보자.
k=5인 B-Tree가 있다. 이는 하나의 노드에 2~5개의 키가 저장됨을 의미한다. 다시 말해, 노드에는 1개이거나 6개 이상의 키가 저장될 수 없다.
9, 31을 삽입했을 때 숫자를 비교하면 적재적소에 배치하였다. 허나 이번에 5를 삽입한다고 해보자.
오버플로우가 발생하여 맨 왼쪽 노드는 k값을 넘었다. 즉시 7을 2번째 노드에 배치하고 오버플로우가 발생한 원소 6은 루트 노드로 옮겨졌다.
다시 39를 삽입해보자.
맨 오른쪽 노드가 k값을 넘어버렸다. 이번엔 바로 원소만 옮기지는 않고 오버플로우가 발생한 노드에서 분할을 한다. 중간값(3번째 값이나 4번째 값이나 상관없다. 중간이기만 하면 된다.)을 루트노드로 보내고 분기를 하나 더 늘린다.
32가 삽입되어 다시 오버플로우가 발생해, 분할하고 원소를 옮겼지만 루트 노드에서 다시 오버플로우가 발생했다. 이때는 루트노드 단위에서 분할하여 중간값 단독으로 루트노드를 만들어준다.
BTreeInsert(t, x) //x는 삽입하고자 하는 키다. t는 트리의 루트 노드이다.
{
x를 삽입할 리프 노드 r을 찾는다.;
x를 r에 삽입;
if (r에 오버플로우 발생) then clearOverflow(r);
}
clearOverflow(r)
{
if (r의 형제 노드 중 여유있는 노드가 있음) then
r의 남는 키를 형제 노드에게 넘김;
else {
r을 둘로 분할하고 가운데 키를 부모 노드 p로 넘김;
if (부모 노드 p에 오버플로우 발생) then clearOverflow(p);
}
}
B-Tree 삭제
아무 문제 없이 단순 원소를 삭제한다고 했을 때는 삭제만 하면 된다.
다만 언더플로우가 될 예정이라면 바로 다음 키값과 교환하고 삭제된다. 이후 언더플로우가 발생하면 형제노드에서 키를 재분배받는다.
언더플로우가 다시 발생해 알맞게 재분배해 병합되더라도 부모노드에서 언더플로우가 발생할 수도 있다. 이때는 부모 노드의 형제 노드, 즉 바로 옆에 있는 노드와 그 부모노드(루트노드)와 함께 병합하면 된다.
BTreeDelete(t, x, v)
{ //t= 루트 노드, x= 삭제하고자 하는 키, v= x를 갖고 있는 노드
if (v!=리프노드) then {
x의 직후 원소 y를 가진 리프 노드를 찾는다;
x<->y;
}
리프 노드에서 x를 제거, 이 리프 노드를 r이라 함;
if (r에서 언더플로우 발생) then clearUnderflow(r); //재귀처리
}
clearUnderflow(r)
{
if (r의 형제 노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있으면)
then
r이 형제 노드의 키를 넘겨받음;
else {
r의 형제 노드와 r을 병합하고 부모 노드에서 키를 하나 받음;
if (부모 노드 p에 언더플로우 발생) then clearUnderflow(p);
}
}
다차원 검색트리 - KD-Tree
검색키에 여러 필드를 사용하려면 다차원 검색트리를 이용해야 한다. 이는 복수 갱의 필드를 그대로 검색에 사용할 수 있다.
KD-Tree
이진검색트리의 확장으로, k개의 필드로 이뤄진 검색키를 사용한다. k보다 크거나 같아야 한다.
또한, 트리의 한 레벨에서 하나의 필드만 사용할 수 있다. 레벨 i에서 필드 i mod k를 사용할 수 있다. 즉, 어떤 필드를 검색에 사용했으면, k개의 레벨을 내려간 다음 그 필드를 검색에 사용할 수 있다.
레벨 0에서는 처음 필드만을 비교할 수 있다. 레벨 1에서는 다음 필드만 비교할 수 있다.
예를 들어보자. 위 KD-Tree는 k=2이다. 35, 95값을 가진 노드를 삽입한다고 해보자.
처음 35는 A노드의 붉은색 50과 비교한다. 35는 50보다 작다. 따라서 왼쪽 노드로 이동한다. B의 파란색 70과 두 번째 삽입원소 95를 비교한다. 이는 70보다 크다. 따라서 오른쪽 노드로 이동한다. 마지막으로 E의 붉은색 40과 35를 비교한다. 35는 40보다 작으니 왼쪽 노드로 이동하고 리프노드가 된다.
'공부한 기록 > 알고리즘' 카테고리의 다른 글
| 알고리즘(12) - 집합의 처리 (4) | 2023.05.08 |
|---|---|
| 알고리즘(11) - 해시테이블 Hash table (0) | 2023.04.18 |
| 알고리즘(9) - 검색트리 - 레드블랙트리 red-black tree (0) | 2023.04.04 |
| 알고리즘(8) - 검색트리 ( search tree ) (0) | 2023.04.03 |
| 알고리즘(7) - 선택 알고리즘 Selection algorithm (0) | 2023.03.29 |