[자료구조] B-Tree, B*Tree, B+Tree

B-Tree

데이터베이스와 파일 시스템에서 사용되는 트리 자료구조의 일종으로, 이진 트리가 자식 노드를 최대 2개만 가질 수 있지만 B-tree는 자식 노드의 개수가 2개 이상인 트리입니다. 또한 노드 내의 데이터가 1개 이상일 수 있습니다. 

노드 내 최대 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree 라고 합니다. 

하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가질 수 있게 되면서 "차수"라는 개념이 등장합니다.

최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부릅니다.

출처 : 위키백과

이렇게 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 효율적으로 저장소에 담을 수 있게 되었습니다.

 

하드디스크,  SSD와 같은 외부 기억장치(비휘발성 메모리)는 블럭 단위로 파일을 입출력합니다. 이 때 발생하는 입출력의 비용은 파일의 크기와 상관 없이 동일합니다. 1KB 크기 블럭에 1byte크기 알파벳 하나가 저장되어 있어도 1KB크기가 가득차있는 블럭과 차이가 없다는 뜻입니다.

이 때 하나의 블럭에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 효율적으로 사용할 수 있습니다.

 

B-Tree는 균현이진트리의 연속

아무리 최악의 경우라도 O(logN)의 시간 복잡도를 가집니다.

 

Preorder traversal (전위 순회) 방식으로 접근합니다.

 

특징(조건)

- 각 노드의 데이터는 정렬되어 있습니다.

- 자료는 중복되지 않습니다.

- 모든 leaf node는 같은 레벨에 있습니다.

- 노드의 데이터 수가 n개라면 자식 노드의 개수는 n+1개입니다.

- root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식을 가집니다.

- root node와 leaf node를 제외한 노드들은 최대 M개 부터 최소 [M/2] 개 까지의 자식을 가질 수 있습니다.

- 노드의 키는 최대 M-1개부터 최소 [M/2]-1개의 키가 포함될 수 있습니다.

- 자식 수의 하한값을 t 라고 하면, M=2t - 1을 만족합니다.
  ( 최소 차수 = 자식 수의 하한값,
    최소 차수 t = 2 라면 3차 B-Tree, key의 하한은 1개 입니다)

 

Key 검색 (하향식)

다음은 차수가 3인 B-Tree입니다.

- 파란색 : 노드

- 초록색 : 노드안에 데이터 (key)

- 노란색 : 자식 노드들을 가르키는 포인터

 

각 노드의 Key들은 노드 안에서 항상 정렬된 값을 가지며, 이진 검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가집니다.

루트 노드에서 시작하여 하향식으로 검색을 수행합니다. 검색하고자 하는 key는 k입니다.

1. 루트 노드에서 시작하여 key들을 순회하면서 검사합니다.
  1-1. 만일 k와 같은 key를 찾았다면 검색 종료
  1-2. 검색하는 값과 key들의 대소관계를 비교
       어떠한 key들 사이에 k가 들어간다면 해당 key들 사이의 자식노드로 내려갑니다.
2. 해당 과정을 Left node에 도달할 때까지 반복합니다. 
    만일 Leaf Node에도 k와 같은 key가 없다면 검색 실패

 

K = 29 일때

1. 29검색 시작, 루트 노드의 key를 순회하면서 검색 시작
2. 29는 20보다 크기 때문에 다음 key를 검사
3. 29은 20보다 크고, 35보다 작기 때문에 20과 35 사이의 자식 노드로 이동
4. 자식 노드에서 다시 검색 시작, 29는 23보다 크기 때문에 다음 key를 검사
5. 29는 노드의 가장 마지막 key인 27보다 크기 때문에 노드의 마지막 자식 노드로 이동
6. 29  검색 완료

 

Key 삽입 (상향식)

B-Tree에 데이터를 삽입하는 과정은 leaf node에서 시작하여 상향식으로 진행합니다.

1. Tree가 비어있다면, root node를 할당하고 K를 삽입합니다.
2. Tree가 비어있지 않다면, 데이터를 넣을 적절한 leaf node를 탐색한다.
3. leaf node에 데이터를 넣고 leaf node가 적절한 상태에 있다면 종료한다.
4. leaf node가 부적절한 상태에 있다면 분리한다.

두 가지 사항을 고려하면 됩니다.

1. 분리가 일어나지 않는 경우

2. 분리가 일어나는 경우

 

case 1. 분리가 일어나지 않는 경우

insert(30)

1. 30를 넣을 노드 탐색, 마지막 depth의 node부터 탐색 시작

2. 30는 40보다 작고 29보다 크므로, 29 key가 있는 노드에 삽입

 

차수가 3인 B-Tree는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 B-tree 조건에 부합합니다.

 

case 2. 분리가 일어나는 경우

insert(31)

1. 31을 넣을 노드 탐색, 마지막 depth의 node부터 탐색 시작
2. 31는 30보다 크고 40보다 작으므로, 30 key가 있는 노드에 삽입

Depth 3에서 한 노드에 담을 수 있는 데이터 수를 초과하였습니다.

차수가 3인 B-Tree는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 B-tree 조건에 부합하지 않습니다.

 

3. 분리를 진행합니다.
3-1. 30 key가 부모 노드로 올라가고, 29key와 31key는 30key의 왼쪽, 오른쪽 자식노드로 연결합니다.

Depth 2에서 한 노드에 담을 수 있는 데이터 수를 초과하였습니다.

차수가 3인 B-Tree는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 B-tree 조건에 부합하지 않습니다.

 

4. 분리를 진행합니다.
4-1. 27key가 부모 노드로 올라가고, 23key와 30key는 27key의 왼쪽, 오른쪽 자식노드로 연결합니다.

Depth 1(=root node)에서 한 노드에 담을 수 있는 데이터 수를 초과하였습니다.

차수가 3인 B-Tree는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 B-tree 조건에 부합하지 않습니다.

 

 

5. 분리를 진행합니다.
5-1. 27key가 root node로 지정하고, 20key와 35key는 27key의 왼쪽, 오른쪽 자식노드로 연결합니다.

6. 이제 모든 노드가 B-tree 조건에 만족하여 분리를 종료합니다.

 

Key 삭제

key를 삭제하는 과정에서  B-Tree 조건에 부합하지 않는다면 트리 재구조화를 진행해야합니다.

key를 삭제하더라도 최소 유지 개수 조건을 만족한다면 트리 재구조화가 필요 없습니다.

case 1. leaf node에서 삭제

delete(43)

43을 삭제하게 되면 [42,45] 노드의 자식 노드 개수가 3개여야 하는 조건을 위반하게 됩니다.

1. 부모 노드에서 Left Min(왼쪽에서 제일 작은 수) key를 
    Left Min Key 오른쪽 key의 자식으로 이동합니다.
2. 왼쪽 자식 노드에 추가됩니다.

 

최소 유지 조건에 부합하는 완성된 tree입니다.

 

case 2-1. leaf node가 아닌 중간 노드에서 삭제

delete(42)

42를 삭제하게 되면 45key의 자식 노드 개수는 2개여야 하는데 3개로 초과하게 됩니다.

이러한 경우는 최대 유지 개수를 부합하지 않으므로 트리 재구조화를 진행해야 합니다.

1. 43key의 Left 자식 노드가 부모 노드로 이동합니다.

[40,45] 노드의 자식 노드의 개수가 3개여야 하는데 2개로 B-Tree 조건에 부합하지 않습니다.

2. 부모 노드 [40,45] 에서 40key가 왼쪽 자식 노드로 이동합니다.

최소 유지, 최대 유지 조건에 부합하는 tree구조로 완성되었습니다.

 

 

case 2-2. 부모 노드와 자식 노드 모두 key개수가 최소인 경우

K : 삭제하고자 하는 key 값

1. K를 삭제하고 K의 자식 노드들을 하나의 노드로 합칩니다.
   합쳐진 노드를 N1이라고 하겠습니다.
2. K의 Parent를 K의 형제 노드에 합칩니다.
   합쳐진 노드를 N2라고 하겠습니다.
3. N1을 N2의 자식 노드로 연결합니다.
4-1. 만약 N2의 Key수가 최대보다 크다면 key삽입 과정과 동일하게 분할합니다.
4-2. 만약 N2의 Key수가 최소보다 작다면 2번 과정으로 돌아가서 동일한 과정을 반복합니다.
5. tree의 left, right depth가 다르다면 depth를 맞추는 작업을 진행합니다.

delete(15)

 

1. 15를 삭제하고 15의 자식 노드들을 하나의 노드로 합칩니다.

2. 15의 부모 노드(20)를 15의 형제 노드(23)에 합칩니다.

3. N1을 N2의 자식 노드로 연결합니다.

 

최소 유지 개수, 최대 유지 개수는 만족하지만 tree의 depth가 다릅니다.

 

5. depth를 같게 해주는 작업을 진행합니다.

B-tree조건에 부합하는 최종 트리가 완성되었습니다.

 

 

B-Tree를 만들어 볼 수 있는 사이트입니다. 만들어 보면서 B-Tree에 대해 알아보니 이해가 더 빠르네요~

 

B*Tree

B-Tree의 단점 중 하나는 구조를 유지하기 위해 추가적인 연산이 수행되거나 새로운 노드가 생성된다는 것입니다. →Balancing

노드의 추가적인 생성과 추가적인 연산의 최소화를 위해 B-Tree에서 규칙이 추가된 B*Tree가 등장했습니다.

 

B-Tree와 B*Tree의 차이점

자식 노드 수의 최소 제약 조건 : 2M / 3 개로 증가하였습니다. (B-Tree에서는 M/2개)

노드가 가득 차면 분열 대신 이웃한 형제 노드로 재배치합니다. (더 이상 재배치 할 수 없는 시점에만 분열)

 

B*Tree특징

- 각 노드의 자료는 정렬되어 있습니다.

- 자료는 중복되지 않습니다.

- 모든 leaf node는 같은 레벨에 있습니다.

- root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식 노드를 가집니다.

- root node가 아닌 노드들은 적어도 2[(M-2)/3]+1 개의 자식 노드를 가지고 있습니다.
  (최대 M개)

 

B+Tree

B-Tree는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있습니다.

이러한 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키 값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있습니다. (같은 레벨의 Sibiling node는 모두 연결되어 있어서 키 값이 중복되지 않습니다.)

 

만약 특정 값을 찾아야하는 상황이라면 leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 이어져 있으므로 탐색에 있어 매우 유리한 구조입니다.

leaf node가 아닌 자료는 인덱스 노드, leaf node자료는 데이터 노드라고 부릅니다.

- 인덱스 노드는 value값에 다음 노드를 가리킬 수 있는 포인터 주소가 존재합니다.

- 데이터 노드는 value값에 데이터가 존재합니다.

 

따라서 키 값은 중복 될 수 있고(인덱스 노드와 데이터 노드에서 동시에 등장 가능),

데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다는 특징을 가지고 있습니다.

 

대부분의 DB시스템은 B+Tree구조를 채택하고 있습니다.

 

B+Tree 특징

- 데이터 노드의 자료는 정렬되어 있습니다.

- 데이터 노드에서는 데이터가 중복되지 않습니다.

- 모든 leaf node는 같은 레벨에 있습니다.

- leaf node가 아닌 node의 키 값의 수는 (그 노드의 서브 트리수 -1) 입니다.

- 모든 leaf node는 연결리스트로 이어져 있습니다.