[자료구조] - B-Tree

 

 

 

 

 

Multiway Search Tree (다원 탐색 트리) / m-way Search Tree (m 분기 탐색 트리)

한 노드가 가질 수 있는 key의 값이 최대 m-1개이고
가질 수 있는 Child의 수가 m개인 트리를 Mulituway Search Tree라 합니다.

 

이진 트리 : 2-way search tree
AVL 트리 : 2-way search tree
2-3 트리 : 3-way search tree

 

 

 

정의는 다음과 같습니다.

m-way Search Tree는 다음을 만족하는 검색 트리입니다.

1. Leaf Node를 제외한 모든 노드는 m개 이하의 서브 트리를 가집니다.

2. k개의 자식 노드를 갖는 노드는, k-1개의 요소(key)를 가집니다.

3. 각 노드의 key는 오름차순으로 정렬되어 있습니다.

4. 노드의 i번째 Key 값을 $Key_i$,  i번째 서브트리가 가진 모든 Key들을 $SKeys_{i}$ 라고 할 때, 다음을 만족합니다.
$$SKeys_i  < Key_i < SKeys_{i+1}<  Key_{i+1}$$

5. 중복된 데이터는 허용하지 않습니다.

 

 

 

 

 

 

 

 

 

 

 

B-Tree

m-way Search Tree의 한 종류로써, 다음을 만족하는 트리입니다.

Order가 m인 B-Tree는 m-way search tree이며 다음을 만족합니다.

1. 루트 노드는 최소 2개 이상의 자식을 갖습니다.(리프 노드인 경우 제외) 

2. 루트를 제외한 모든 노드는 최소 $ \left \lceil  \frac{m}{2} \right \rceil$ (m의 절반 이상)개의 자식을 가집니다.

3. 모든 Failure Node는 동일 level에 존재해야 합니다.

Failure Node는 Leaf Node 아래에 존재하는 가상의 Node입니다.

앞으로 언급하는 Leaf Node는 Failure Node가 아닌 Failure Node의 부모 노드를 의미합니다.

order가 2인 B-Tree는 full binary tree입니다.

2-3 Tree는 order가 3인 B트리 입니다.

 

 

 

 

 

 

 

 

 

 

 

B-Tree 사용 이유

B-Tree는 한번의 접근 시 많은 자원을 소모하는 데이터(Disk 등에 존재)를 효율적으로 조회하기 위해 사용합니다.

 

일반적인 BST의 경우, 한번의 접근에 오직 2개의 데이터만 가지고 오기 때문에 10번의 Disk Access를 하더라도 $2^{10}$ 개 만큼의 데이터만 가져올 수 있습니다.

 

그러나 order가 200인 B-Tree를 생각하면 2번의 접근만으로도 $200^2$개의 데이터를 가지고 올 수 있으므로 효율적입니다.

 

그렇다면 모든 데이터를 한번에 들고오는게 가장 좋지 않을까요?

 

Disk등의 공간에는 엄청난 수의 데이터가 들어있어서 이를 memory에 모두 가져오는 것은 불가능하기에, 어쩔 수 없이 여러번 디스크에 접근해야 합니다.

 

즉 m의 크기를 잘 조정하여 메모리에 무리가 가지 않으면서 Disk의 접근 횟수를 최대한 줄이는 것이 중요합니다.

 

 

 

 

 

 

 

 

 

 

 

 

B-Tree 에서의 삽입

반드시 Leaf Node에 데이터를 삽입합니다.

1. 값이 추가될 위치를 찾습니다. 

2. 추가될 Leaf Node가 용량을 초과하지 않았다면 오름차순으로 데이터를 삽입합니다.
만약 용량을 초과하였다면 Split(분할)을 수행하여야 합니다.

 

 

예시로 사용되는 B-Tree는 Order가 5인 B-Tree입니다.

Order가 5인 B-Tree

 

 

 

 

Split(분할)

Split은 다음과 같은 과정입니다.

추가될 데이터를 포함하여 중앙값을 결정합니다.

중앙값을 부모 노드에 추가시키며 중앙값보다 작은 값들은 왼쪽 서브트리, 중앙값보다 큰 값들은 오른쪽 서브트리가 됩니다.

부모 노드가 없다면 새로 생성하며,
부모 노드에서도 용량이 가득찼다면 똑같이 Split 하는 과정을 반복합니다.

 

 

 

 

 

 

 

 

 

 

 

 

Rotation과 Merge

삭제의 경우 Rotation(회전)과 Merge(병합)을 사용합니다.

 

 

Rotation (회전)

원소가 삭제되는 노드를 기준으로,
삭제되는 노드의 형제노드의 원소 하나를 부모 노드로,
부모 노드의 원소 하나를 자신의 노드로 가져와 회전시키는 것을 의미합니다.

 

 

 

 

Rotation이 가능한 조건

order가 5인 B-Tree를 예시로 설명하겠습니다.

 

모든 노드들은 $\left \lceil \frac{5}{2} \right \rceil = 3$개 이상의 자식을 가져야 합니다.

삭제되는 노드의 형제 노드가 $\left \lceil \frac{m}{2} \right \rceil  + 1$개 이상의 Key를 가지고 있을 경우,
하나를 제거해도 B-Tree의 조건을 만족시키므로 Rotation이 가능합니다.

 

 

 

 

 

 

 

 

Merge (병합)

원소가 삭제되는 노드를 기준으로,
삭제되는 노드의 직후 형제노드(혹은 직전 형제노드)와 자신 사이에 포함되는 모든 부모 원소를 합치는 것을 의미합니다.

 

 

 

 

 

 

 

 

 

이후 설명할 모든 삭제의 상황에서, 다음과 같은 알고리즘을 사용한다고 하겠습니다.

Non Leaf Node의 삭제 시, 삭제되는 Key의 Left Subtree의 최댓값으로 비어있는 부분을 채워주도록 하겠습니다.

RightSubtree의 최솟값을 가져오는 경우 이후 존재하는 값들을 왼쪽으로 한칸씩 당겨주어야 하지만, 
LeftSubtree의 최댓값을 가져오는 경우 바로 가져올 수 있기 때문에 효율적입니다.

 

Rotation은 최좌측 서브트리를 제외하고는 반드시 왼쪽 형제노드를 확인하여 가능할 때만 발생한다고 하겠습니다.

최좌측 서브트리는 항상 왼쪽 형제노드가 없으므로 이 경우에만 특별하게 오른쪽 형제노드를 확인합니다.

이 또한 마찬가지로 오른쪽 형제노드에서 Rotation을 하는 경우 값들을 한칸씩 당겨주어야 하기 때문에 비효율적이므로 위와같은 방법을 사용합니다.

 

Rotation은 최좌측 서브트리를 제외하고는 반드시 왼쪽 형제노드를 우선적으로 확인도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

B-Tree 에서의 삭제

• Leaf Node의 삭제
• Non Leaf Node의 삭제

 

트리에서의 Non Leaf Node의 삭제는 모두 Leaf Node의 삭제 형태로 바꿔주어 생각할 수 있습니다.

 

 

 

 

 

 

 

 

Leaf Node의 삭제

• 삭제 시 노드의 자식노드의 수가 $\left \lceil \frac{m}{2} \right \rceil$(m의 절반 이상)개보다 큰 경우
• 삭제 시 노드의 자식노드의 수가 $\left \lceil \frac{m}{2} \right \rceil$(m의 절반 이상)개보다 작아진 경우

 

첫번째 경우, 삭제 이후 추가적인 작업이 필요하지 않습니다.

 

두번째 경우에서는 삭제 이후 Rotation(회전) 혹은 Merge(병합) 작업을 행해주어야 합니다.

 

Rotaion이 가능하다면 Rotation을,
Rotation이 불가능하다면 Merge를 수행합니다.

 

 

 

 

 

 

 

삭제 시 노드의 자식노드의 수가 $\left \lceil \frac{m}{2} \right \rceil$(m의 절반 이상)개보다 큰 경우

바로 삭제가 가능합니다.

 

 

 

 

 

 

삭제 시 노드의 자식노드의 수가 $\left \lceil \frac{m}{2} \right \rceil$(m의 절반 이상)개보다 작은 경우

삭제 이후 Rotation 혹은 Merge를 수행합니다.

 

 

 

 

 

 

 

 

 

Non Leaf Node의 삭제

Leaf Node의 삭제 형태로 바꿔줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference

https://yoongrammer.tistory.com/73

[자료구조] 다원 탐색 트리 (Multiway Search Tree)