1월 8일 부터 1월 13일까지, B - Tree와 B+ - Tree를 구현하는 프로젝트를 진행하고 있다.
오늘(1월 11일)을 시작으로 한 주 동안 B - Tree의 원리, 삽입 그리고 삭제가 어떻게 이루어지는지에 대해 알아볼 것이다.
B - Tree 관련 포스팅들은 [Introductions to Algorithms (Third Edition), Tomas H. Corman]의 내용을 토대로 부족한 설명들과 예시를 덧 붙일 예정이다.
B - Tree를 공부하며, 인터넷의 여러 강의들 그리고 블로그들을 참고했다. 그런데, B - Tree를 구현하는 방법이 조금씩 달라서 이해하는데 혼란스러웠던 점이 있다. 특히, 대부분의 자료들에서 삽입에 대한 설명보다 삭제에 대한 설명이 부족하다고 느꼈다. 그래서 B - Tree 포스팅에서는 삭제를 조금더 꼼꼼히, 자세하게 다루어 볼 예정이다.
아래는 내가 공부를 하며 책 외에 참고한 자료들이다.
책의 내용이 너무 이해하기 힘들어 다른 인터넷 자료들을 찾아 다녔었다. 하지만, 책 만큼 정확하게 모든 경우들을 다루는 자료는 찾지 못했다. 인터넷의 자료들이 중구남방이라는 느낌을 받았다. 반면, 책은 논리적이고 일관적이라는 것을 깨닫고 책의 로직을 이해하는데 온 힘을 쏟았다.
- Abdul Bari 교수님의 10.2 B Trees and B+ Trees. How they are useful in Databases click
- 책의 방식과 다른 방법을 소개해 준다. 특히, B-Tree를 사용하는 이유, 어떤 장점이 있는지에 대해 깨달을 수 있었다. 삭제에 관한 영상이 없어 굉장히 아쉬웠다. 삭제에 대해서도 설명해 주셨다면, 이 방식으로 구현해 보았을 것 같다.
- Deletion from a B-tree click
- 책에는 시각적인 자료가 조금 부족한 편인데, B-Tree 삭제 입문을 하는데 큰 도움을 받았다. 하지만, 위의 강의와 마찬가지로 책과 약간 다른 방식을 소개해주며, 이 페이지만 봐서는 코드로 구현하기가 참 힘들다.
- B-Tree display click
- B-Tree를 시각적으로 구성해주는 사이트이다. B-Tree를 공부하는 초기에 내가 공부한 내용이 맞는지 확인하는 용도로 사용했다.
B-Tree는 디스크나 다른 직접 접근 보조 기억 장치에서 잘 동작하도록 설계된 균형 잡힌 검색 트리이다. Balanced Tree의 종류들 중 하나이다. 이진 트리에서는 노드의 왼쪽과 오른쪽의 균형을 맞추어 주는 매커니즘이 존재하지 않기 때문에, 최악의 경우 모든 노드가 오른쪽으로 쏠리게 된다. 이때 최악의 시간 복잡도는 O(N)이 되게 된다.
하지만, B-Tree와 같은 Balanced Tree에서는 위의 그림과 같이 노드가 한 쪽으로 쏠리지 않도록, 삽입/삭제시에 재 정렬된다. 이렇게 한쪽 자식에게 값이 몰리지 않도록 재정렬 함으로, 최악의 경우에도 시간 복잡도는 O(log N)이다.
늘 그렇듯 TradeOff는 존재한다. Balanced Tree에서 삽입/삭제 시 재정렬하는 추가적인 작업을 수행하기 때문에, 삽입/삭제 시에는 이진트리와 같은 일반적인 트리보다 느리다. 삽입/삭제의 성능과 탐색의 성능을 Trade한 것이다.
Balanced Tree의 종류에 B-Tree외에도 Red-Black-Tree가 존재한다. 하지만, B-Tree는 한 개의 노드에 여러개의 key들을 담을 수 있고, Red-Black-Tree에는 한 개의 노드에 한 개의 key만 담을 수 있다. 이러한 이유로 B-Tree의 깊이가 Red-Black_Tree의 깊이보다 적고, 이는 값을 탐색할 때 이점으로 작용한다.
이러한 이유로 많은 데이터베이스 시스템에서 정보를 저장하는데 B-Tree 혹은 B-Tree 변형을 사용한다.
키와 관련된 부수적인 정보는 키와 같은 노드에 있다고 가정한다.
Abdul Bari 교수님의 10.2 B Trees and B+ Trees. How they are useful in Databasesclick
위의 강의에서 설명하는 방식과 다른 방식의 삽입을 설명합니다.
해당 포스팅에서 설명하는 방식은 루트 노드에서 리프 노드까지 Top-Down으로 내려가며 재귀적으로 탐색하는 방식입니다.
1. 모든 노드 x는 아래와 같은 속성이 있다.
a. x.n은 노드 x에 현재 저장되어 있는 키의 개수다.
b. x의 key들은 x.key(1) <= x.key(2) <= ... <= x.key(x.n) 이 되도록 단조증가하는 순서로 정렬되어 있다.
c. x가 리프 노드일 때는 x.leaf가 1이며, x가 내부 노드일 때는 x.leaf가 0이다.
2. 각 내부 노드 x는 리프 노드가 아닐 때 자식 노드를 가리키는 x.n+1개의 포인터 x.c(1), x.c(2), ... x.c(x.n+1)를 가진다. 자식 노드의 개수는 항상 키의 개수 + 1이다.
3. x.key(i)는 각 서브 트리에 저장되는 키들의 범위를 분할한다. x.key(i)는 x.c(i)의 key들보다 항상 크고, x.c(i+1)의 key들보다 항상 작다.
4. 모든 리프 노드는 트리 높이 h와 같은 깊이를 가진다.
5. 노드는 그들이 포함할 수 있는 키의 개수에 대해 상한과 하한을 가진다. 이런 한계를 B-Tree의 최소 차수라고 하는 일정한 정수 T>=2를 이용해 포현한다.
a. 루트를 제외한 모든 노드는 t-1개 이상의 키를 가진다. 따라서, 루트 노드를 제외한 모든 내부 노드는 자식 노드를 적어도 t개 가진다. 트리가 비지 않았다면, 루트는 키를 적어도 하나 가진다.
b. 모든 노드는 2t-1개 이하의 키를 가진다. 따라서, 하나의 내부 노드에는 자식 노드를 최대 2t개 가진다. 키를 정확히 2t-1개 가지는 경우 해당 노드를 가득 차 있다고 한다.
1~5번 규칙들은 책에 있는 내용을 그대로 옮겨온 것이다. 이 문장들을 조금 더 자세히 살펴보자.
리프노드는 트리의 가장 아래 위치하는 노드이다. 따라서, 리프 노드에는 자식 노드(x.child)가 존재하지 않는다.
위의 그림에서 각 노드는 5개의 key를 가지기 때문에 x.n = 5이다.
내부 노드의 경우 5개의 key를 가지고, key의 개수보다 1이 많은 6개의 자식을 '반드시' 가진다.
B Tree에서는 노드 내에 들어갈 수 있는 key 개수의 범위가 제한되어 있다. 만약 차수(t)가 3이라면, 노드에 들어갈 수 있는 키 개수의 최대값은 5개(2t-1)이고, 최소값은 2개(t-1)이다.
차수가 3인 경우 노드의 키 개수가 5이면, 노드의 키 개수가 최대이고, 노드의 키 개수가 2이면, 노드의 키 개수가 최소이다. 노드에 들어갈 수 있는 키 개수의 범위가 제한되어 있다는 사실은 굉장히 중요하다.
삽입을 할 때, 노드의 키 개수가 이미 최대라면 더 이상 삽입할 수 없음으로, 해당 노드를 분할한 후에 삽입해야 한다.
이렇게 노드를 분할할지 말지에 대한 기준이 되는 숫자가 2t-1이다. 분할된 노드의 키의 개수는는 각각 t-1개 t-1개이며, 중간값을 가지는 키 1개가 부모노드로 올가가게 된다.
* t-1은 삭제시 노드를 병합해야할지 말지에 대한 기준이 되는 숫자이고 뒤에서 다음 포스팅에서 다시 다룰 예정이다. 우선은 삭제 과정에 집중하자.
B Tree에서는 단순히 키가 삽입될 리프 위치를 찾아 삽입할 수 없다. 왜냐하면 삽입 후의 결과가 조건에 모두 부합하는 올바른 B Tree가 되지 않을 가능성이 있기 때문이다. (삽입 되어야 할 위치에 이미 2t-1개의 노드가 존재한다면, 1개의 키가 추가되는 순간 조건에 위배된다.)
따라서, 루트 노드에서 리프 노드 방향으로 키가 삽입될 위치를 찾아가면서, 경로에 존재하는 키의 개수가 (2t-1)개인 가득 찬 노드들을 미리 분할한다. 이 과정을 통해 리프 노드에 도달하게 되면 가득 찬 노드를 분할하고자 할 때마다 그 부모가 가득 차 있지 않음이 보장된다. 또한, 리프 노드에 도달했을 때, 리프노드 또한 가득 차 있지 않음이 보장된다.
위의 그림과 같이 자식 노드가 분할되어 중간값 6이 부모 노드로 올라온다.
이때, 부모 노드에 6이 추가되기 전에 존재하던 키의 개수가 2t-1개였다면, 6이 들어옴으로써 키의 개수가 2t개가 되고 이는 범위를 초과하기 때문에 다시 부모노드를 분할해 주어야 한다. 이 과정이 연쇄적으로 발생할 수 있기 때문에, 이를 미연에 방지하고자 우리가 이동하는 경로에서 만나는 노드의 키의 개수가 2t-1개라면, 미리 모두 분할해 주었다.
우리가 이동할 노드의 키가 2t-1개일 때, 해당 노드를 분할하며 내려갈 것이다.
위의 방식으로 리프 노드에 도달하게 되면 가득 찬 노드를 분할하고자 할 때마다 그 부모가 가득 차 있지 않음이 보장된다.
- 분할 과정
node x 가 존재하고, 키가 내려갈 node는 y라고 하자. y에 존재하는 키의 개수가 2t-1개라면, y를 분할한 후에 k를 y로 내려보내야 한다. y를 분할하는 과정이 어떻게 이루어지는지 조금 더 자세히 알아보자.
분할하기 위해 분할된 값들이 들어갈 node를 추가로 생성하고, 이 노드를 z라고 하자.
y를 분할하면, 키 1개가 x로 올라가게 된다. 이 키가 들어갈 자리를 확보하기 위해 x의 키를 오른쪽으로 한 칸씩 오른쪽으로 밀어준다. 그림에서는 나타내지 않았지만, x에는 자식들을 가리키는 포인터들도 존재한다. x에서 z를 가리킬 포인터를 y 오른쪽에 삽입해 주어야 함으로, 이 공간을 확보하기 위해 x의 자식들도 한 칸씩 오른쪽으로 밀어준다.
공간이 확보되었음으로, y의 키들을 노드 x와 z에 각각 분할해주자.
이제 k를 자식 노드로 내려보내야 한다. 그런데, y.key2가 y로부터 x로 올라왔음으로, k가 y.key2보다 큰지 작은지 한번 더 확인해주어야 한다. k가 y.key2보다 크다면, i+1번째 자식으로, 그렇지 않다면 그대로 i번째 자식으로 내려보내면 된다.
B Tree에서 키는 리프 노드에서만 삽입된다.
리프 노드를 제외한 모든 노드에 n개의 키가 존재할 때, 자식은 n+1개 존재해야 한다. 리프 노드에는 자식이 존재하지 않기 때문에, 키를 한 개 더 추가하더라도 규칙에 위배되지 않는다. 하지만, 자식을 가지고 있는 내부 노드에 키를 추가하게 되면, 자식의 수와 키의 개수가 동일해지고, 트리의 규칙에 위배된다. 따라서, 키는 리프 노드에서만 삽입될 수 있다.
x가 루트 노드인 경우, 1번과 같이 분할할 수 없다.
x가 루트 노드라면, x의 부모 노드는 존재하지 않는다는 뜻이다. 이때, 분할한 값을 담을 노드 z를 생성하고, 1번과 같이 분할 과정을 진행하게 되면, x.key2가 갈 곳이 없다는 문제가 생긴다.
따라서, x가 루트 노드인 경우에는 x의 중간값이 올라갈 새로운 루트 노드를 하나 생성한 후에, 1번과 같은 과정을 진행해 주어야 한다.
위의 경우를 예외적으로 처리하기 위해서, B_Tree_Insert함수와, B_Tree_Insert_main함수로 나누어 작성해 주었다.
B_Tree_Insert함수는 루트 노드를 확인한 후에 위의 경우와 같이 가득 차있으면, split되었을 때, 중간값이 올라갈 수 있는 빈 노드를 형성시키고, B_Tree_Split_child 함수를 실행하게 된다. 이후 노드 부터는 B_Tree_Split_child와 B_Tree_Insert_Nonfull함수가 재귀적으로 처리하며 내려가게 된다.
위의 조건들을 생각하며, B Tree에 원소k 가 삽입되는 경우에 대해 생각해보자.
1. node x가 리프 노드이면, x에 원소k를 삽입한다.
2. node x가 리프 노드가 아닌 경우 원소k를 자식 노드로 내려준다. 이때, 원소k가 내려가게 될 자식 노드(y)를 사전에 체크해 주어야 한다.
-
2 - 1. y가 가진 키의 개수가 2t-1개 보다 적다면, 키가 추가로 삽입될 공간이 존재함으로 재귀 함수를 호출해 y로 k를 보내준다.
-
2 - 2. y가 가진 키의 개수가 2t-1개 라면, 키가 추가로 삽입될 공간이 없음으로, y를 먼저 분할한다. 이때, y가 분할되며, 키 1개가 x로 올라오게 되는데, x는 이미 2t-1개 미만의 키를 가지는 것이 보장되어 있음으로, y로부터 1개의 키가 x로 올라오더라도 x의 키의 개수는 2t-1개를 초과하지 않는다.
y가 분할되고, y의 중간값이 x로 올라온다. 이때, x는 2t-1개보다 적은 수의 키를 가지고 있음으로, 키가 추가로 삽입될 수 있음이 보장된다.
k가 y.key2보다 큰지 작은지에 따라서, 2번 child로 내려갈지, 3번 child로 내려갈지가 결정된다. k와 y.key2를 비교해 재귀함수를 실행시키자.
B Tree 삽입에서 가득 찬 노드들을 미리 분할했던 것 처럼, 삭제시에도 최소 키의 개수를 가지는 노드들이 키를 더 많이 가질 수 있도록 미리 처리한다. k를 찾아 재귀적으로 내려가는 과정에서 방문하는 경로에 존재하는 키의 개수가 (t-1)인 경우 형제 노드에서 키를 가져오거나, 형제노드와 병합하는 과정을 거친다.
삭제 과정에서 발생할 수 있는 모든 경우의 수에 대해 알아보자.
1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다.
2. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재한다.
3. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재하지 않는다.
리프 노드 x 내에 k가 존재한다면, k를 삭제한다.
x를 방문했다는 것은 이미 x에 존재하는 키의 개수가 t-1개보다 크다는 의미이기 때문에, 키 한 개를 삭제하더라도, 트리의 규칙에 어긋나지 않는다.
2 - 1. k가 i번째 키일 때, i번째 자식의 키의 개수가 t개 이상인 경우
k가 i번재 키일 때, i번째 자식의 키의 개수가 t개 이상인 경우(t-1개가 아닌 경우) x.child[i]를 루트로 하는 서브트리에서 가장 큰 수인 k`을 찾는다.
k`은 서브트리의 리프 노드들 중 가장 오른쪽에 위치한다. k`은 k 왼쪽에 위치한 수들 중 가장 큰 수이기 때문에 k대신 i번째 자식과 i+1번째 자식을 나누는 기준이 될 자격을 갖춘 수이다.
k`을 k자리에 대체한 후, x.child[i]로 내려가 k`을 재귀적으로 삭제한다.
재귀함수를 호출시켜 k를 삭제한다. Delete(x.child[i], k)를 실행하자.
2-2. k가 i번째 키일 때, i번째 자식의 키의 개수가 t-1개 이고, i+1번째 자식의 키의 개수는 t개 이상인 경우
k가 i번재 키일 때, i+1번째 자식의 키의 개수가 t개 이상인 경우(t-1개가 아닌 경우) x.child[i+1]를 루트로 하는 서브트리에서 가장 작은 수인 k`을 찾는다.
k`은 서브트리의 리프 노드들 중 가장 왼쪽에 위치한다. k`은 k 오른쪽에 위치한 수들 중 가장 작은 수이기 때문에 k대신 i번째 자식과 i+1번째 자식을 나누는 기준이 될 자격을 가지고 있다.
k`을 k자리에 대체한 후, x.child[i+1]로 k`을 삭제하러 재귀적으로 내려가자.
재귀함수를 호출시켜 k를 삭제한다. Delete(x.child[i+1], k)를 실행하자.
2-3. k가 i번째 키이고, i번째 자식과 i+1번째 자식의 키의 개수가 모두 t-1개인 경우
i번째 자식과 k 그리고 i+1번째 자식을 합쳐, 2t-1개의 키를 가지는 새로운 노드를 만든다.
t-1개의 키를 가지는 두개의 노드와 k를 합쳤기 때문에 이 경우 병합된 노드에 존재하는 키의 개수는 항상 2t-1개이다.
이렇게 노드에 존재하는 키의 개수를 보충해 주고, 자식 노드로 k를 지우러 가는 재귀함수를 실행시키자.
k가 x내에 존재하지 않는다면, k가 위치해야 하는 자식 노드의 위치를 먼저 찾는다. 이때, 자식 노드(i번째 자식)와 형제 노드들의 키의 개수에 따라 경우가 나뉜다.
3 - 1. i번째 자식 노드에 존재하는 키의 개수가 t개 이상인 경우
i번째 자식 노드로 k를 삭제하러 가기 위한 재귀함수를 실행시킨다.
3 - 2. i번째 자식 노드에 존재하는 키의 개수가 t-1개인 경우
3-2-1. i-1번째 자식 노드에 존재하는 키의 개수가 t개 이상인 경우 i-1번째 자식 노드로부터 키 한 개를 빌려오자.
3-2-2. i+1번째 자식 노드에 존재하는 키의 개수가 t개 이상인 경우 i+1번째 자식 노드로부터 키 한 개를 빌려오자.
3-2-3. 양 옆의 형제노드 모두 키의 개수가 t-1개인 경우 왼쪽 혹은 오른쪽 형제노드와 병합한다. child[i]와 child[i+1]을 병합하는 경우 i 번째 key도 함께 병합한다. 2-3의 경우와 같이 t-1개의 노드 두개와 키 한개를 병합하기 때문에, 2t-1개의 키를 가지게 된다.