B+Tree

B+ 트리

키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종입니다.

특징

• 동적임
• 각각의 인덱스 세그먼트(블록, 노드) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스로 구성됨
• B트리와 대조적으로 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있음 즉, 오직 키들만이 내부 블록에 저장됨
• 블록-지향적인 storage context(ex : filesystem)에서 검색을 효율적으로 할 수 있음

B-Tree vs B+Tree

1. 모든 key, data가 리프노드에 모여있음
2. 모든 리프노드가 연결리스트 형태를 띄고 있음
3. 리프노드의 부모 key는 리프노드의 첫 번째 key보다 작거나 같음
   
   M차 B+Tree의 특징

• 노드는 최대 M개부터 M/2개까지의 자식을 가질 수 있음
• 노드에는 최대 M-1개부터 [M/2]-1개의 키가 포함될 수 있음
• 노드의 키가 x개라면 자식의 수는 x+1개
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족함

장점

• 블럭 사이즈를 더 많이 이용할 수 있음
• leaf 노드끼리 연결 리스트로 연결되어 있어 탐색에 유리함

단점

• B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

---

B+Tree 검색

B-Tree와 동일하나 B-Tree는 Best Case의 경우 루트 노드에서 끝날 수 있지만

B+Tree는 모든 경우에 대해 리프 노드로 가서 순차 탐색함으로써 데이터를 찾아야 합니다

B+Tree 삽입

통상적인 검색으로 삽입하고자 하는 노드가 어느 리프 노드에 해당하는지 체크합니다.

1. 리프 노드가 full 상태가 아니라면 오름차순 정렬에 맞게 삽입한다.

2. 리프 노드가 full 상태라면 노드를 분할해야 한다.

   a) 새로운 리프 노드를 구성하고 기존 리프 노드 데이터의 절반을 옮긴다.

   • 새로운 리프 노드의 최소 키(기존 리프 노드의 중간값)를 부모 노드에 삽입하여 기준 포인터로 삼는다.
   • 부모 노드 역시 리프 노드의 key를 받았으므로 full 상태인지 체크해야 한다.
     • 부모 노드가 쪼개지지 않는 시점이 올 때까지 상향식으로 반복한다.

3. 루트가 쪼개지면 새로운 루트 노드를 생성하되 1개의 키와 2개의 양쪽 포인터로 구성되어야 하며 기존 루트 노드의 중간 key는 새로운 루트 노드에 저장한 뒤 제거한다.

B+Tree 삭제

루트에서 출발하여 key가 속한 leaf 노드를 찾아 리프 노드의 key를 삭제합니다.

삭제한 뒤 리프 노드가 최소 key 이상인지 체크해야 합니다.

1. 삭제할 key가 index set에 존재하지 않을 경우

   a) 리프 노드의 key 개수가 t−1t−1보다 클 때

   • 리프 노드의 key만 삭제하고 종료

   b) 리프 노드의 key 개수가 t−1t−1일 때

   • 형제 노드 중 하나라도 key의 개수가 t−1t−1보다 큰 경우
     • 왼쪽 노드가 크다면 왼쪽 노드의 가장 큰 값을 받고 현재 노드의 첫 번째 값이 바뀌므로 부모 노드의 key도 바뀐 값으로 변경
     • 오른쪽 노드가 크다면 현재 노드는 변화가 없으나 우측 노드의 최솟값이 현재 노드로 옮겨감에 따라 우측 노드의 부모 key를 다음 값으로 바꿔준다.
   • 형제 노드가 모두 t−1t−1인 경우
     • 어떤 경우라도 최소 차수를 만족할 수 없으므로 형제 노드들 중 하나와 병합해야 한다. 왼쪽 혹은 오른쪽 노드와 병합하되 왼쪽은 현재 노드의 부모 key, 오른쪽에 합치면 우측 노드의 부모 key가 삭제된다.
     • 부모 노드의 key 개수가 1 감소한 경우 부모 노드의 key 개수가 t−1미만이면 다시 reconstruct를 해야한다.

2. 삭제할 key가 index set에 존재할 경우

a) 리프 노드의 key 개수가 t−1t−1보다 클 때

• 리프 노드를 삭제하고 기존 key가 있던 index set 자리에 inorder successor 값으로 바꾼다.

b) 리프 노드의 key 개수가 t−1t−1일 때

• 형제 노드 중 하나라도 key의 개수가 t−1t−1보다 큰 경우
  • 왼쪽에서 가져오면 현재 노드의 첫 번째 값이 바뀌므로 index set의 key 값도 가져온 값으로 교체
  • 오른쪽에서 가져오면 우측 노드의 첫 번째 값이 바뀌므로 index set의 기존 우측 노드의 첫 번째 값을 다음 값으로 교체
• 형제 노드가 모두 t−1t−1인 경우
  • 한쪽 형제와 현재 노드를 병합한다. 왼쪽과 병합한 경우 현재 노드의 부모 key를 삭제, 오른쪽과 병합한 경우 오른쪽 노드의 부모 key를 삭제한다.
  • 부모 key가 삭제되었으므로 부모 노드의 key 개수가 t−1미만이면 다시 reconstruct를 수행한다.

참고

https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Plus-Tree

https://ko.wikipedia.org/wiki/B%2B_트리

https://8iggy.tistory.com/191