240122_B-Tree

참조: https://www.youtube.com/watch?v=H_u28u0usjA&t=167
참조: https://rebro.kr/169
B-Tree 시뮬레이션: https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree란

• Balanced Tree라고도 하며, 이진 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 갯수를 늘리기 위한 트리 자료구조.
• 주로 DB 또는 파일 시스템에 사용된다.
• 일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도로 O(logN)을 갖지만, 트리가 편향된 경우 최악의 시간 복잡도로 O(N)을 갖게 된다. 하지만 B-Tree는 편향되지 않도록 항상 밸런스를 유지하므로 최악의 경우에도 O(logN)의 시간이 보장된다.

B-Tree 특징

위 트리는 3차 B-Tree의 예시이고, 주황색 부분은 자식 node를 가리키는 포인터이며, 살구색 부분은 각 node의 key이다.

• 자녀 노드의 최대 갯수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.
• 노드의 key들은 반드시 오름차순으로 정렬한다.
• 정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다.
• 최대 M개의 자녀를 가질 수 있는 B-Tree를 M차 B-Tree라 부른다.
• root node는 항상 2개 이상의 자식 node를 갖는다.(root node가 leaf node인 경우를 제외)
• 모든 leaf node들은 같은 level에 있어야 한다.

주요 4가지 파라미터
1. M: 각 노드의 최대 자녀 노드 수
2. M-1: 각 노드의 최대 key 수
3. ceil(M/2): 각 노드의 최소 자녀 노드 수
4. ceil(M/2)-1: 각 노드의 최소 key 수

B-Tree의 key 검색

• 과정

1. root node부터 탐색을 시작한다.
2. node의 key를 순서대로 확인하며 탐색하는 값이 존재하면 탐색을 종료한다.
3. 만약 존재하지 않는다면, 포인터를 통해 자식 node로 내려간다.
4. leaf node까지 2~3 과정을 반복한다.

B-Tree의 key 삽입

• 과정

1. 빈 트리인 경우 root node를 만들어 새로운 값을 삽입한다. root node가 가득 찬 경우 node를 분할하여 leaf node를 생성한다.
2. 빈 트리가 아니라면, 새로운 값이 들어갈 leaf node를 검색 과정과 동일하게 탐색한다.
3. 해당 leaf node에 자리가 남아있다면 정렬을 유지하도록 알맞은 위치에 삽입하고, leaf node가 가득 찼다면, 새로운 값을 삽입한 후 해당 node를 분할한다.
4. node가 분할되는 경우 node의 중앙값을 기준으로 분할한다. 중앙값은 부모 node로 합쳐지거나 새로운 node로 생성되고, 중앙값을 기준으로 왼쪽의 key는 왼쪽 자식, 오른쪽의 key는 오른쪽 자식으로 생성된다.

해당 트리에 13이라는 key를 삽입하는 예시이다.

B-Tree의 key 삭제

B-Tree의 삭제의 경우 다음과 같이 나눠진다.

1. 삭제할 key가 leaf node에 있는 경우
   1-1) 현재 node의 key 수가 최소보다 큰 경우
1-2) 현재 node의 key 수가 최소이고, 왼쪽 또는 오른쪽 형제 node의 key수가 최소보다 큰 경우
1-3) 현재 node와 왼쪽, 오른쪽 형제 node의 key 수가 최소이고, 부모 node의 key 수가 최소보다 큰 경우
1-4) 현재 node와 왼쪽, 오른쪽 형제 node, 부모 node 모두 key수가 최소인 경우
2. 삭제할 key가 leaf node를 제외한 node에 있는 경우
   2-1) 현재 node 또는 자식 node의 key 수가 최소보다 큰 경우
2-2) 현재 node와 자식 node 모두 key 수가 최소인 경우

1. 삭제할 key가 leaf node에 있는 경우

1-1) 현재 node의 key 수가 최소보다 큰 경우

• 단순히 삭제해도 무방하다.

1-2) 현재 node의 key 수가 최소이고, 왼쪽 또는 오른쪽 형제 node의 key수가 최소보다 큰 경우

1-3) 현재 node와 왼쪽, 오른쪽 형제 node의 key 수가 최소이고, 부모 node의 key 수가 최소보다 큰 경우



1-4) 현재 node와 왼쪽, 오른쪽 형제 node, 부모 node 모두 key수가 최소인 경우

• 트리의 재구조화가 필요하다.
• 이 경우는 2-2)와 동일하므로 뒤에서 함께 설명하겠다.

2. 삭제할 key가 leaf node를 제외한 node에 있는 경우

2-1) 현재 node 또는 자식 node의 key 수가 최소보다 큰 경우


이 후 과정은 case1과 동일하다

2-2) 현재 node와 자식 node 모두 key 수가 최소인 경우

과정

1. k를 삭제하고 k의 양쪽 자식을 하나로 합친다. 합쳐진 node를 n1이라고 하자.
2. k의 부모 노드 key를 형제 node에 합쳐준다. 합쳐진 node를 n2라 하자.
3. n1를 n2의 자식이 되도록 연결한다.
4-1. 만약 n2의 key 수가 최대보다 크다면 key 삽입 과정과 동일하게 분할한다.
4-2. 만약 n2의 key 수가 최소보다 작다면, 2. 로 돌오가서 동일한 과정을 반복한다.