B Tree
- 일반화된 Balanced Search Tree
- 모든 리프들은 같은 depth를 갖는다 (비트리의 height)
- 루트를 제외한 모든 노드는 최소한 t-1개의 키를 갖는다 (t >= 2)
- 루트를 제외한 모든 인터널 노드는 최소한 t개의 자손을 갖는다
- 모든 노드는 최대 2t-1개의 키를 갖는다
- 따라서 모든 인터널 노드는 최대 2t개의 자손을 갖는다(리프 노드는 자손 없다)
- 리프 노드를 제외하고, 모든 노드는 n개의 키를 가지면 자손의 개수는 n+1개이어야 한다
x.n : 노드 x에 저장되어 있는 키의 수
x.leaf : 불리언 값으로 x가 리프노드면 TRUE, x가 인터널 노드면 FALSE 값이 저장된다
x.key[1], x.key[2] ... x.key[x.n] : 오름차순으로 정렬되어 저장된다
x.c[1], x.c[2] ... x.c[x.n+1] : 자식노드를 가리키는 포인터들
높이의 최대값 (Upper Bound of Height) : Worst-case Height
위의 식을 통해서 O(h) = O(log t N) 임을 알 수 있다
검색(Search)
- 입력값
x : 루트 노드를 가리키는 포인터 (서브 트리의 루트인 경우도)
k : 해당 서브 트리에서 찾고자 하는 키값
- 출력값
k 값이 트리에 존재하는 경우 : (y, i) 노드 포인터 y와 index i (y의 키들 중 i번째에 key가 존재)
k 값이 트리에 존재하지 않는 경우 : NIL
BTreeSearch(x, k):
i = 1
while i <= x.n and k > key :
i += 1
if i <= x.n and k == key :
return (x, i)
else if x.leaf :
return NIL
else :
return BTreeSearch(x.ci, k)
시간복잡도
각 노드에서 키를 선형탐색으로 찾는 경우
O(h) * O(t) = O(t * log t N)
각 노드에서 키를 이진탐색으로 찾는 경우
O(log t N) * O(log 2 t) = O(log 2 N)
삽입(Insert)
- 이미 존재하는 리프 노드에 새로운 키를 삽입한다
- 리프 노드가 가득 차게 되면 중간값을 기준으로 리프 노드를 분리하고
- 중간 값은 분리된 두 노드들의 dividing point를 나타내기 위해서 부모 노드로 승진한다(올라간다)
- 입력값
x : 가득 차지 않은 인터널 노드
i : x.c[i]가 x의 가득 찬 자녀인 i
- 출력값
없음
x, y, z를 업데이트한다
B-TREE-SPLIT-CHILD(x, i):
y =x.c[i]
// 새 노드 할당, 설정(leaf, n)
z = ALLOCATE-NODE()
z.leaf y.leaf
z.n = t - 1
// key : y의 t+1~2t-1부분을 z의 1~t-1 부분으로 붙여넣기
// c : y의 t+1~2t 부분을 z의 1~t부분으로 붙여넣기
for j = 1 to t - 1:
z. key[j] =y.key[j+t]
if not y. leaf:
for j = 1 to t:
z.c[j] =y.c j + t
// y의 n 줄이기
y.n = t - 1
// y의 t번째가 들어가기 위한 x의 i번째 자리 만들기
for j=x.n + 1 downto i + 1:
x.c[j + 1] =x.c[j]
x.c[i+1] = z
for j =x.n downto i:
x.key[j+1]=x.key[j]
// 키를 옮기고 x의 n을 바꾸기
x. key[i] =y.key[t]
x.n = x.n + 1
Case 1 : B트리의 루트가 가득 찬 경우
- 새로운 노드 s를 만들고, 루트를 분할하여 s를 새로운 루트로 만든다
- 키 k를 s를 루트로 하는 B트리에 삽입한다
Case 2 : B트리의 루트가 가득 차지 않은 경우
- 키 k를 루트가 가득 차지 않은 B트리에 삽입한다
BTreeInsert(T, k):
r = T.root
if r.n == 2t-1:
s = ALLOCATE-NODE()
T.root = s
s.leaf = FALSE
s.n = 0
s.c[1] = r
BTreeSplitChild(s, 1)
BTreeInsertNonFull(s, k)
else:
BTreeInsertNonFull(r, k)
루트를 분할하는 것이 B트리의 높이를 증가시키는 유일한 방법이다
BTreeInsertNonFull(x, k):
if x.leaf:
while i >= 1 and k < x.key[i]:
x.key[i+1] = x.key[i]
i = i-1
x.key[i+1] = k
x.n = x.n+1
else:
while i >= 1 and k < x.key[i]:
i = i-1
i = i+1
// x.c[i]가 가득찬 경우
if x.c[i].n == 2t-1:
BTreeSplitChild(x,i)
// x.c[i]가 두개로 분할 되었을 때 어느 쪽으로 내려가야 하는지 결정하는 부분
if k > x.key[i]:
i = i+1
// 리프 노드가 발견 될 때까지 재귀적으로 반복될 것이다
BTreeInsertNonFull(x.c[i], k)
시간 복잡도 : O(t*log t N)
삭제(Delete)
Case 1: 삭제될 키가 리프노드에 있는 경우
Case 1-(1) : 삭제될 키가 있는 노드의 x.n >= t인 경우
- just delete the key
Case 1-(2) : 삭제된 키가 있는 노드의 x.n == t-1 (minimum number of keys)인 경우
- 노드의 키를 삭제하는 것은 B-tree 속성 위배로 이어지게 된다
- Case 1-2-a : sibling 노드가 t개 이상의 키를 가지는 경우, sibling node로 부터 키를 빌려온다.
- Case 1-2-b : sibliing 노드가 모두 키의 최소수를 가지는 경우, 부모 노드로 부터 키를 빌려와서
sibling 노드와 병합한다. 이 과정을 거치면 부모 노드의 키가 1개 줄어드므로
이 과정 이후의 부모 노드의 키의 수를 확인해야 한다.
* Case 1-2b로 키를 삭제한 이후 부모 노드의 키가 줄어드는데, 부모가 루트이고 자식 노드가 없다면
B 트리의 높이가 줄어든다.
Case 2 : 삭제될 키가 인터널노드에 있는 경우
- 이 케이스를 케이스 1으로 바꾼다
- 삭제될 키가 속한 노드의 predecessor 혹은 successor을 찾는다
- 삭제될 키를 predecessor로 대체한다
- 이제 리프 노드에 있는 키를 삭제한다(case 1)