[Data Structure] B-Tree란?

 

안녕하세요 Foma 💻 입니다!

 

오늘은 트리 자료구조 중 균형 끝판왕 (이름 자체가 Balanced - Tree)인 B-Tree에 대해 알아보겠습니다.

 

바로 시작할게요~

---

B-Tree의 배경

 

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. - 위키 백과 -

 

즉, 이진 트리를 조금 더 효율적으로 확장한 자료구조에요!

 

이진 탐색 트리는 최악의 경우 O(n)의 시간 복잡도를 갖기 때문에 그것을 조금 더 효율적으로 만든 것이

 

O(logn)의 시간 복잡도를 갖는 AVL 트리였습니다.

 

하지만 만약 2천만개의 데이터가 있다면 log20,000,000 = 24 즉, 최대 24번 탐색하게 됩니다.

 

여기서 24번보다 더 적게 탐색할 순 없을까? 를 생각하게 되는데 그게 바로 "브랜치(자식)를 확장시키자"였습니다.

 

쉽게 설명하면 이진트리는 자식(브랜치)이 무조건 2개잖아요? 

 

대신 "자식을 여러 개 가지면서 높이를 줄이자!" 해서 나온 게 바로 B - Tree입니다.

 

노드가 가질 수 있는 최대 자식의 수를 M이라고 한다면 M차 B-Tree로 불리게 됩니다.

---

B-Tree 규칙

 

B-Tree 자료구조를 구성하기 위해선 몇 가지 규칙이 성립해야 합니다.

 

1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다.

 

어긋나는 예 ❌

만족하는 예 👍🏻

 

 

2. 노드 안에 데이터는 정렬되어 있어야 한다.

 

어긋나는 예 ❌

 

만족하는 예 👍🏻

 

3. 자식 노드의 데이터는 부모의 데이터 값에 따라 배치된다.

 

자식 노드들은 부모 노드의 데이터 n번째보다 작은 값이 배치되고 나머지 한 개의 자식 노드에 마지막 노드보다 더 큰 값이 배치됩니다.

 

어긋나는 예 ❌

 

0번째 자식 노드는 부모의 0번째 데이터인 4보다 작아야 하고,1번째 자식 노드는 부모의 1번째 데이터인 10보다 작아야 합니다.

 

2번째 자식 노드는 마지막 데이터 보다 더 큰 값들이 배치됩니다.

 

만족하는 예 👍🏻

 

 

 

4. 루트 노드가 리프 노드가 아닌 경우 항상 2개 이상의 자식을 갖는다.

 

나쁜 예 ❌

만족하는 예 👍🏻

 

 

5. M차 B-Tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가지고 있어야 한다.

 

만약 4차 B-Tree라면 최대 4개의 데이터를 가질 수 있고 2(4/2)개 이상의 데이터를 가져야 합니다.

 

어긋나는 예 ❌

 

 

만족하는 예 👍🏻

 

6. 모든 리프 노드의 높이는 같아야 합니다.

 

어긋나는 예 ❌

 

 

만족하는 예 👍🏻

 

 

7. 리프 노드의 데이터 수는 M-1 이하여야 한다.

 

3차 B-Tree라면 마지막 리프 노드 수는 2개 이하여야 한다.

 

어긋나는 예 ❌

만족하는 예 👍🏻

 

 

---

Search

 

B-Tree를 탐색하는 방법은 간단합니다.

 

찾고자 하는 값보다 더 큰 값이 있는 위치의 인덱스를 가진 자식 노드(없다면 데이터 수만큼)로 이동해줍니다.

 

만약 여기서 5를 찾기 위해선 어떻게 해야 할까요?

 

 

루트 노드부터 탐색해줍니다.

 

루트 노드의 6(0번째)이 5보다 더 크죠? 0번째 자식 노드로 이동합니다.

 

 

0번째 자식 노드 2와 4 중에서 더 큰 값이 없으므로 2번째(데이터 수) 자식 노드로 이동해줍니다.

 

 

---

Insert

 

삽입하기 위해선 2가지 경우가 있습니다.

 

1. 리프 노드가 M-2개 이하인 경우

 

이 경우엔 그냥 삽입하면 됩니다.

 

3차 B-Tree에 10을 삽입하는 경우

 

10이 들어갈 공간이 [9] 1개 밖에 없으므로 그냥 삽입해 줍니다.

 

 

2. 리프 노드가 M-1개인 경우

 

삽입한 뒤에 중앙값을 기준으로 분할하고 중앙값은 부모노드로 합쳐지거나 새로운 노드로 생성되고 

 

해당 중앙값에 따라서 자식 노드가 배치됩니다.

 

아래 3차 B-Tree에 17이 삽입될 경우

 

[14,15,16]로 7번째 규칙인 "리프 노드는 M-1이여야 한다."에 어긋나게 됩니다.

 

고로 14,15,16의 중앙값인 15을 부모 노드로 합칩니다.

 

여기선  3번째 규칙인 "자식 노드의 데이터는 부모의 데이터 값에 따라 배치된다."에 어긋납니다.

 

 

고로 데이터의 값에 맞게 배치해주면 아래와 같이 B-Tree가 완성됩니다.

 

---

Remove

 

삭제를 할 경우 2가지 경우가 존재합니다.

 

1. 리프 노드인 경우

 

1-1) 삭제하려는 데이터가 있는 노드의 수가 최소보다 큰 경우

 

그냥 삭제해주고 자식 노드를 데이터에 맞게 재배치 합니다.

 

아래 3차 B-Tree에서 17을 삭제할 경우

 

[17,24]이 1(최소 M/2)보다 크기 때문에 17을 삭제하고 자식 노드들을 재배치 합니다.

 

 

1-2) 삭제하려는 데이터가 있는 노드의 수가 최소이고 형제 노드의 수가 최소보다 많을 때

 

삭제하려는 데이터를 삭제하고 삭제하려는 노드의 인덱스를 가진 부모 노드의 데이터로 바꿔줍니다.

 

그리고 형제 노드 중 최소보다 많은 노드가 왼쪽 노드의 데이터라면 가장 큰 값을 오른쪽 노드의 데이터라면 

 

가장 작은 값을 바꿔준 부모 노드 자리에 채워주고 데이터에 맞게 재배치 해줍니다.

 

3차 B-Tree에서 27을 삭제할 경우

 

먼저 19가 0번째 노드에 있으므로 부모 노드의 0번째 데이터인 24과 바꿔주고 27을 삭제합니다.

 

 

왼쪽 형제 노드의 가장 큰 값을 부모로 대체해 줍니다.

 

 

1-3) 삭제하려는 노드와 형제 노드의 수가 모두 최소이고, 부모의 노드가 최소보다 큰 경우

 

삭제하려는 노드 인덱스 위치를 가진 부모의 데이터를 대체해주고 재배치합니다.

 

3차 B-Tree 3을 삭제할 경우

 

 

 

3을 삭제해주고 그 자리에 3이 1번째 노드에 있으므로 [2,4]의 1번째인 4를 대체해 줍니다.

 

 

1-4) 삭제하려는 노드,형제,부모 노드 모두 최소인 경우

 

3차 B-Tree에서 16을 삭제할 경우

 

 

 

데이터를 삭제해주고 부모 노드와 자식 노드를 합쳐줍니다.

 

 

형제 노드의 자식들로 합쳐줍니다.

 

현재 노드 번째의 부모 노드 인덱스를 내려줍니다.

 

 

데이터를 올바르게 배치해줍니다.

 

 

 

2. 리프 노드가 아닌 경우

 

2-1) 삭제하려는 노드 또는 자식 노드의 수가 최소보다 큰 경우

 

삭제한 뒤 자식의 왼쪽 노드에서 가장 큰 값 또는 오른쪽 노드에서 가장 작은 값으로 대체해 줍니다.

 

3차 B-Tree에서 2를 삭제할 경우

 

 

 

2를 삭제한 뒤 오른쪽 자식 노드에서 가장 작은 값인 4와 대체해 줍니다.

 

 

2-2) 삭제하려는 노드와 자식 노드가 모두 최소일 경우

 

삭제하려는 노드를 삭제하고 자식들을 하나로 합쳐줍니다.

 

3차 B-Tree에서 4를 삭제하는 경우

 

삭제해주려는 데이터를 삭제하고 자식들을 합쳐줍니다.

 

 

 

삭제해준 노드 번째 인덱스를 가진 부모 노드의 데이터를 형제 노드와 합쳐준 뒤 합쳐준 자식 노드들을 그 아래로 붙여줍니다.