[DB] B-트리(B-tree)

---

B-트리 (B-Tree)

 

B-트리는 이진탐색트리처럼 탐색을 위한 자료구조 중 하나로 탐색 성능을 유지하기 위해 균형 트리를 유지하는 것이 특징이다. 다음과 같은 조건을 만족하면 B-트리라 하고, 다르게는 다음 조건을 통해 성능을 유지한다.

• 모든 리프노드(leaf node)는 동일한 레벨(level)에 위치한다.
• 루트르 제외한 모든 비리프노드(non-leaf node)는 최소 $ \lceil m / 2 \rceil $ 개 이상, 최대 $ m $ 개의 자식을 가진다.
• 비리프노드의 데이터 개수는 자식 수보다 하나 작으며 리프노드는 최소 $ \lceil m / 2 \rceil - 1 $ 개에서 최대 $ m - 1 $ 개의 데이터를 가진다.
• 루트노드는 트리 전체에 루트 하나로만 구성되지 않는 한 최소 2개의 자식을 가져야 한다.
• 데이터는 오름차순으로 정렬되어 저장되며 자식 포인터는 데이터의 범위를 기준으로 연결된다.

다르게 보면 노드의 데이터 수가 $ n $ 개라면 자식 노드의 개수는 $ n + 1 $ 개라는 것과 노드 데이터를 기준으로 왼쪽은 데이터보다 작은 값을 가진 서브트리, 오른쪽은 데이터보다 큰 값을 가진 서브트리라는 것을 알 수 있다.

 

---

삽입

 

삽입은 항상 리프노드에 한다. 노드가 넘칠 때 중앙 키를 기준으로 좌우 키들을 분할하고 중앙 키가 부모 노드로 올라간다. 만약 부모 노드에서도 넘친다면 다시 분할하는 것을 반복한다.

노드가 넘친다는 것은 위 조건으로 제시된 것 이상의 키 값을 노드가 가지는 경우이다. 즉 $ m - 1 $ 개 이상의 키 값을 하나의 노드가 가진다면 넘친다고 한다.

먼저 분할이 필요없는 경우 노드 삽입은 탐색 후 해당 자리에 값을 삽입하는 것으로 끝난다.

출처: https://code-lab1.tistory.com/

만약 분할이 필요하다면 아래와 같이 분할이 일어난다.

출처: https://code-lab1.tistory.com/

즉 노드가 넘치면 분할이 일어나고 중앙에 위치한 키값이 부모노드로 이동하고, 부모노드가 넘치면 다시 분할이 일어나고를 반복하여 트리를 구성한다.

 

---

삭제

 

삽입보다 다양하게 경우의 수가 나뉜다. 먼저 리프노드에서 값을 삭제하는 경우이다.

그 중에서도 삭제하더라도 문제가 생기지 않는 경우에는 그냥 삭제해주면 된다.

출처: https://code-lab1.tistory.com/

만약 삭제했을 때 문제가 발생, 즉 부모노드가 자식노드를 기준 미만으로 가지게 된다면 이때도 경우의 수가 나뉜다. 처음으로 형제노드에서 값을 빌릴 수 있다면 다음과 같이 삭제가 가능하다.

출처: https://code-lab1.tistory.com/

그런데 형제노드에서 빌려오지 못할 수 있다. 그런데 부모노드를 분할하여 맞출 수 있다면 아래와 같이 처리할 수 있다.

출처: https://code-lab1.tistory.com/

만약 리프노드에서 값을 삭제하는데 형제노드에서도, 부모노드에서도 빌려올 수 없다면 조금 복잡해진다. 아래 부분을 참고해야 한다.

리프노드가 아닌 내부노드에서 삭제가 일어난다고 해보자.

먼저 내부노드에서 삭제할 때 자식노드가 충분한 경우라면 오른쪽 서브트리의 최소 노드, 혹은 왼쪽 서브트리의 최대 노드와 삭제하려는 노드를 교환한 후 삭제한다. 그렇다면 그 이후는 리프노드를 삭제하는 것과 같다.

출처: https://code-lab1.tistory.com/

그러나 만약 내부노드에서 값을 삭제하는데 현재노드와 자식노드 모두 키 개수가 최소라면 조금 복잡해진다. 이 경우는 앞서 말한 리프노드에서 값을 삭제하는데 형제노드에서도, 부모노드에서도 빌려올 수 없을 때도 사용된다.

내부 노드의 값을 삭제하려고 할 때, 해당 노드와 그 자식 노드 모두 키의 개수가 최소 개수인 경우에는 단순히 값을 제거하는 것만으로는 트리의 균형 조건을 유지할 수 없다. 이때는 트리의 재구조화 과정이 필요한데 먼저 삭제하려는 값을 제거한 후, 해당 값의 양쪽 자식 노드를 하나의 노드로 병합한다.

병합된 자식 노드는 삭제된 키의 부모 노드에서 제거된 키의 자리에 있던 형제 노드와 병합되며, 이로 인해 형제 노드의 자식으로 다시 연결된다. 만약 병합된 노드의 키 개수가 트리에서 허용하는 최대 키 수를 초과한다면, 삽입할 때처럼 다시 노드를 분할하여 트리를 균형 있게 유지한다. 반대로 병합된 결과가 여전히 최소 키 수를 만족하지 못한다면, 이번에는 부모 노드의 키를 형제 노드와 병합하는 과정을 반복하게 된다. 이러한 병합 과정은 필요할 경우 루트 노드까지 전파되어 트리의 구조를 바꾸며, 경우에 따라 트리의 높이가 줄어들 수도 있다.

출처: https://code-lab1.tistory.com/