[탐색 트리] 한 살도 이해하는 B-트리

B-트리란?

B-트리(B-tree)는 데이터베이스와 파일 시스템에 널리 사용되는 트리 자료구조의 일종으로,

이진 트리를 확장해 하나의 노드에 여러 개의 데이터를 저장한다.

 

---

차수가 p인 B-트리의 특성

 

1)적어도 노드의 반은 채워야 한다.

즉, root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 =  최소 ⌈p / 2⌉개, 최대 p 개

 

2) root는 pointer를 2개 이상 가져야 한다. 

즉, root의 서브트리의  수   >=  2

 

3) 모든 leaf는 같은 level  (즉, 균형 트리이다)

 

4) 노드의 key 개수

   leaf가 아닌 노드: pointer 수  - 1 개 = 서브트리 수 - 1개

   (아래 B-트리 기본 구조 그림을 보면, key의 개수는 (pointer 개수 - 1)일 수 밖에 없다. pointer 사이사이에 key가 들어가므로!)

   leaf노드 : 최소 ⌈p / 2⌉ - 1개, 최대 p -1 개  (최소 조건은 노드의 삽입과 삭제에 있어 중요한 부분이다)

 

5) 한 노드 내의 키 값은 오름차순으로 정렬 (즉, p-원 탐색트리이다)

 

---

B-트리 기본 구조

B-트리 기본 구조: 노드, Key, Pointer

 

 

노드 구조

Key값과 Pointer를 가진다.

Pointer는 서브 트리를 가리킨다.

P : tree pointer, Pr: data pointer

 

B-트리 노드 구조

 

 

---

B-트리의 검색

내가 찾고자 하는 Key 값을 검색하는 방법을 알아보자.

예를들어, key 값이 42인 key를 찾는다고 하면, pointer를 따라 조건에 맞게 이동하며 검색을 한다.

해당하는 블록 내에서는 오름차순으로 정렬되어 있으므로 순차 탐색을 한다.

B-트리 검색

---

B-트리의 삽입

- 새로운 Key는 leaf 노드에 삽입한다

- 노드에 새로운 key가 들어갈 빈 공간이 있는 경우 단순히 leaf 노드에 삽입한다.

- 빈 공간이 없는 경우, 즉 overflow가 발생한 경우에는 분할(split)한 후 삽입한다.

 

분할(split)

삽입할 key 값을 노드에 넣었을 때, 총 key의 개수를 M이라고 하자.(아래 그림에서 10, 20, 30이므로 총 개수 M = 3)

1. ⌈M / 2⌉ 번째의 key 값을 부모 노드로 이동한다. (만약, 부모 노드가 존재하지 않는다면 부모 노드를 새로 만들어 준다.)

(아래 그림에서 20을 부모 노드로 올려준다!)

2. 나머지 key 값들은 절반씩 나누어 왼쪽, 오른쪽 서브트리가 된다.

 

 

B-트리 삽입 시 분할(split)

역시 백문이 불여일run

직접 삽입을 해보자!

 

주어진 트리는 다음과 같다.

차수가 3인 3원 B-트리이므로, 앞서 봤던 B-트리의 특성을 복습할 겸 그림과 같이 보자.

p=3 이므로, 

B-트리 예시

---

차수가 3인 B-트리의 특성

1)적어도 노드의 반은 채워야 한다.

즉, root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 =  최소 2개 (⌈3 / 2⌉)개, 최대 3 개.

 

2) root는 pointer를 2개 이상 가져야 한다. 

즉, root의 서브트리의  수   >=  2

 

3) 모든 leaf는 같은 level  (즉, 균형 트리이다)

 

4) 노드의 key 개수

   leaf가 아닌 노드: pointer 수  - 1 개 = 서브트리 수 - 1개

   (아래 B-트리 기본 구조 그림을 보면, key의 개수는 (pointer 개수 - 1)일 수 밖에 없다. pointer 사이사이에 key가 들어가므로!)

   leaf노드 : 최소 1개 (⌈3 / 2⌉-1)개, 최대 2(3 -1) 개(최소 조건은 노드의 삽입과 삭제에 있어 중요한 부분이다)

 

 

---

(1) 22를 삽입 (파란색 선을 따라가보자)

22가 들어갈 자리가 비어있으므로 단순하게 삽입한다.

[20,    ]  ->  [20,  22] 

 

22가 삽입될 leaf 노드에는 빈 공간이 존재하므로 단순 삽입한다. 41도 직접해보자!(연두색 선)

(2) 59를 삽입

59를 삽입하려고 했더니, 59가 들어갈 leaf 노드에는 이미 50,58로 꽉 차있다.

그렇다면 분할(split)을 해줄 때!
[50, 58, 59]

1) 현재 총 key 값이 3개이므로, ⌈M / 2⌉ 번째 = ⌈3 / 2⌉ = 2 번째 값, 즉 58을 부모 노드로 올려준다.

=> 부모 노드는 [60,   ] 에서  [58, 60] 이 되겠죠?

 

2) 50과 59는 각각  [58 ,60] 중 58의 왼쪽과 오른쪽의 서브트리가 된다.

 

57도 직접 넣어보자! 단순 삽입

3) 54를 삽입

조금 더 어렵다. 분할이 두 번 이상 나오는 유형! 이것까지 이해하면 삽입은 거의 다 이해했다고 봐도되므로 도전해보자.

자, 우선 54를 넣을 leaf 노드를 찾아가 봤더니 [50, 57]로 꽉 차있다.

그렇기에 분할을 해준다.

[50, 54, 57]

1) 현재 총 key 값이 3개이므로, ⌈M / 2⌉ 번째 = ⌈3 / 2⌉ = 2 번째 값, 즉 54를 부모 노드로 올려준다.

2) 부모 노드가 [58, 60]으로 꽉 차 있으므로 역시 분할을 시작한다.

 

 

[54, 58, 60]

2-1) 현재 총 key 값이 3개이므로, ⌈M / 2⌉ 번째 = ⌈3 / 2⌉ = 2 번째 값, 즉 58를 부모 노드로 올려준다.

2-2) 부모 노드가 [19, 43]으로 꽉 차 있으므로 여기서도 분할을 해줘야 한다!

 

[19, 43, 58]

3-1) 현재 총 key 값이 3개이므로, ⌈M / 2⌉ 번째 = ⌈3 / 2⌉ = 2 번째 값, 즉 43을 부모 노드로 올려준다.

3-2) 부모 노드인 [69,  ]에 빈 자리가 있으므로 단순 삽입해준다. 

[69,  ]   =>  [43, 69] 

3-3) 19와 58는 각각  [43 ,69] 중 43의 왼쪽과 오른쪽의 서브트리가 된다. [19,  ] 와  [58,  ] 이 되겠죠? 

3-4) 54와 60은 [58,   ]의 각각 왼쪽, 오른쪽 서브트리가 된다.  [54,   ]와  [60,  ] 이 된다.

3-5) 50과 57은 [54,  ]의 각각 왼쪽, 오른쪽 서브 트리가 된다.  [50,   ]와  [57,  ] 이 된다.

 

각 노드의 pointer가 가리키고 있던 곳은 그래도 가리키도록 유지해준다.

 

결국 overflow가 발생하면 분할하는 과정의 반복이다. 직접 그려보면서 하다 보면 어렵지 않다.

 

54 삽입 최종 결과

---

B - 트리의 삭제

 

1) 삭제할 키가 leaf 노드가 아닌 경우

후행 키 값과 자리 교환 후 leaf 노드에서 삭제

(선행 키랑 교환할지 또는 후행키랑 교환할지는 정하는 사람 마음이다. 우린 후행키와 교환으로 정하자!

선행 키는 해당 key보다 트리에서 왼쪽에 있는 key 값중 가장 큰 값,  즉, 나보다 작은 값 중에 최대값

후행 키는 해당 key보다 트리에서 오른쪽에 있는 key 값중 가장 작은 값, 즉 나보다 큰 값 중에 최소값 을 말한다.)

 

2) 삭제할 키가 leaf 노드인 경우

단순 삭제

또는

leaf 노드에서 underflow 발생할 경우에 (leaf 노드의 key 개수가 최소 ⌈p / 2⌉ - 1개보다 작을 경우)

재분배(redistrubution) 또는 합병(merge) 필요

 

재분배 - 형제 노드가 최소 key 개수 보다 많은  key를 가진 경우

형제 노드의 key -> 부모 노드->  부모 노드에 있던 키 값을 underflow 발생한 노드로 이동, 부모 노드에 형제 노드의 key가 위치함.

 

합병 - 재분배가 불가능할 경우 (형제 노드도 최소 key 개수를 갖는 데 있어서 사정이 마땅치 않을 경우)

형제 노드 + 부모 노드의 key + underflow 노드를 합쳐 하나의 노드로 합병

 

역시 백문이 불여일run!

직접 삭제를 해보자.

16 삭제

1) 16 삭제

16은 leaf 노드의 key값이 아닌 중간 노드에 있으므로, 후행 키인 18과 교환 후에 삭제한다.

16과 18을 자리 교환 후 삭제

앗 그런데 후행 키와 교환한 후 leaf 노드에서 16을 삭제했더니 underflow가 발생한다.

(16이 있던 노드에 key의 개수가 0이 되버리기 때문)

 

그렇다면 재분배를 시도해본다. 형제 노드한테 가서 형편이 된다면 꿔온다고 생각하면 된다! 마치 흥부와 놀부처럼..

그런데.. 형제 노드인 j가 15를 빌려주면 j도 underflow가 발생하므로 재분배가 불가능하다.

(놀부 형님 j 도 형편이 좋지 않았다)

 

그렇다면 마지막으로 합병을 시도한다.

 

부모, 형제, underflow 노드의 합병

부모 노드의 key 값인 18과 형제 노드, underflow가 발생한 노드를 합병했다.

그런데 부모 노드의 18이 합병되면서 원래 부모 노드 d에서 underflow가 발생했다. (18이 있던 부모 노드의 key 개수가 0)

이 역시 재분배를 시도해보고, 안되면 합병을 진행한다.

 

역시 재분배가 불가능하므로 합병!

d의 형제 노드 e가 26을 주게되면 역시 최소 key 개수를 갖지 못하므로, 합병을 진행했다.

우리는 삭제를 위한 모든 과정을 이해했다.

 

B-트리의 삽입과 삭제를 진행하다보면 다음과 같은 특징을 발견할 수 있다.

- B-트리는 leaf leveld은 계속 유지되면서,

- 노드가 늘어나면 root 방향 쪽으로 늘어나고

- 줄어들면 root 부터 줄어든다.

---

시간 복잡도

Red-Black 트리와 마찬가지로 항상 좌, 우 자식 노드 개수의 밸런스를 유지하므로 항상 시간 복잡도 O(logN)을 보장한다.

배열, 이진 탐색 트리, Red-Black 트리, B-트리의 시간 복잡도를 비교해보면,

배열은 최악의 경우 O(n)

이진 탐색 트리는 평균적으로 O(log n), 최악의 경우 O(n) 한 줄로 쭉 나가는 경우..

Red-Black 트리와 B-Tree는 최악의 경우에도 O(log n )

 

B-Tree와 Red-Black Tree의 차이 (정보 출처: https://steady-coding.tistory.com/558)

우선, B-Tree는 트리의 높이가 상대적으로 작을 수 밖에 없다. 한 노드에 여러 개의 key값이 존재하기 때문!

B-Tree의 각 노드는 배열로서 실제 메모리 상에 차례대로 저장이 되어 있다고 한다.

같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다.

즉, 같은 노드 상 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스에 접근을 하는 것이다.

반면 RedBlack-Tree는 각 노드마다 무조건 하나의 데이터만 가지게 되므로 모든 데이터를 접근할 때 무조건 참조 포인터로 접근한다.