TIL 010 B+트리

https://www.programiz.com/dsa/b-plus-tree

B+트리를 c로 구현한 코드다.
github

📕 B+트리

B+트리는 B트리의 개선 구조로 leaf에 모든 값들을 담고 있다. 이는 멀티레벨 인덱싱을 가능하게 하여 더 빠르고 간단하게 데이터에 접근할 수 있게 한다. 데이터 베이스에서 사용되기 적절하다.

👉 B+트리 특징

• 모든 leaf 노드는 같은 레벨에 있다.
• root는 최소 두 개의 자녀를 갖는다.
• root를 뺀 모든 노드는 최대 n개, 최소 n/2 개의 자녀를 갖는다.
• 모든 노드는 최대 n-1개, 최소 n/2 -1 개의 키를 갖는다텍스트.

👉 B+트리 기능

1. 탐색
n 차 B+트리에서 k값을 탐색하고자 한다.

• root에서 시작해 키 값들을 n-1까지 순차적으로 찾을 것이다.
• 만약 k가 key1보다 작으면, 루트의 왼쪽 자식으로 간다.
• 만약 k가 key1와 같으면, key2와 비교한다. 만약 key2보다 작으면, k는 key1과 key2 사이에 있는 것이다. 그러므로, key2의 왼쪽 자식으로 간다.
• 만약 k가 key2보다 크다면, key3,key4,...,key(n-1)까지 반복한다.
• 이를 leaf 노드에 닿을 때까지 반복한다.
• leaf에 k가 있다면 true를 없다면 false를 반환한다.
  (이진탐색을 사용하면 더 빠른 시간복잡도로 해결할 수 있다.)

2. 삽입
B+트리에서 모든 값은 leaf에 삽입되어야하므로, 일단은 적절한 leaf까지 찾아 들어간다. 삽입은 두 가지 단계를 거친다.
1) 적절한 leaf를 찾고 삽입
2) 필요하다면 정리와 분할

Case#1: leaf가 가득차지 않았을 때

• 키 값을 leaf에 오름차순으로 삽입

Case#2: leaf가 가득찼을 때

• 키 값을 leaf에 오름차순으로 삽입, 다음과 같이 정리해준다.
• n/2 지점(중앙값,median)을 기준으로 나눈다.
• n/2 키 값을 부모 노드에 보내준다.
• 나눈 leaf 노드를 링크 시켜준다.
• 만약, 부모 노드도 가득 찾다면, 부모도 정리 과정을 거친다.

3. 삭제
B+트리에서는 내부의 노드가 중복되어 있음으로(내부에 한 개, leaf에 한 개) 신경써야 한다. 삭제는 다음 3단계를 거친다.
1) 삭제될 키의 위치를 탐색 후 삭제
2) 필요하다면 정리
3) 필요하다면 노드가 최소의 키 갯수를 가지지 못하는 underflow에 대한 처리

Case#1: leaf에서만 삭제 될 때

• 만약 충분한 키 갯수가 있다면, 그냥 삭제한다.
• 만약 삭제 후 키 갯수가 부족하다면, 형제 노드에서 빌려온다.

Case#2: 내부와 leaf 삭제 될 때

inorder predecessor = 내 노드의 왼쪽 자식 노드 중 가장 큰 키
inorder successor = 내 노드의 오른쪽 자식 노드 중 가장 작은 키

B+트리의 핵심은 leaf에서 일어나는 삭제와 내부에서 일어나는 삭제를 구분하는 것이다. leaf에 일어나는 삭제는 부모 노드와 자녀가 같은 경우도 있고, 리프 노드의 연결성도 신경써한다. 내부에서 일어나는 삭제는 inorder successor로 대체된다.

또한, leaf에서 일어나는 삭제와 내부에서 밸런싱과 밸런싱과 병합(merge)을 구분해야 한다. leaf에서 일어나는 삭제는 부모 노드 리프노드가 같은 경우와 리프 노드를 고려해야한다. 내부에서 일어나는 밸런싱과 병합은 비트리와 같다.

• 만약 leaf 노드에 충분한 키 갯수가 있다면, 내부와 leaf의 키 값을 삭제한다. leaf는 다음 키와 연결 시켜준다. (내부 노드의 빈 공간은 inorder successor로 대체한다.)

• 만약 leaf 노드에 충분한 키 갯수가 부족하다면, 삭제 후 형제 노드에서 빌려온다. 빌려온 빈 공간은 빌려온 값으로 대체한다. (내부 노드의 빈 공간은 inorder successor로 대체한다.)

• 만약 leaf 노드에 충분한 키 갯수가 부족하고, 형제 노드에서 빌려올 수 없다면, 형제 노드와 병합이 일어난다. 자식은 합쳐주고 부모는 삭제된다. (내부 노드의 빈 공간은 inorder successor로 대체한다.)

• 만약 내부의 빈 공간이, leaf의 할아버지(부모의 부모)노드 일 때, leaf 노드는 형제 노드와 합친다. 빈 공간은 inorder successor로 대체한다. -> 이런 케이스를 따로 고려할 수도 있지만 재귀를 사용하여 다시 한번 밸런싱이 이루어진후 다시 한번 삭제할 값이 있는 지 검토하는 방법도 있다.

Case#3: 트리의 높이(height)가 축소 될 때

• leaf에서 삭제가 일어나 키 수가 부족하지만 형제에서 빌려올 수 없어 병합이 일어난 뒤 부모 노드에서도 키 수가 부족하지만 빌려올 곳이 없는 경우 또 병합이 일어나면서 축소가 일어난다.