B+트리, B*트리(B+Tree, B*Tree)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

B+Tree란?

B-Tree의 변형된 형태로 트리 탐색하지 않고 데이터를 linear하게 탐색해야 할 경우 순차 접근을 해야 하는데 그러면 중위 탐색을 수행하게 되고 트리 전체를 탐색하게 되어 성능 저하가 발생한다. B+Tree는 B-Tree의데이터의 순차 접근 문제를 개선하기 위해 제시되었다. B-Tree에서는 중복값 없이 한 개의 노드에만 key가 유일하게 존재했으나 B+Tree는 leaf 노드와 그 외 노드에 공존할 수 있다.

B+Tree의 리프 노드는 연결리스트로 구성되어 있으며 순차 집합(Sequence Set)이라고도 한다. 여기에 데이터가 담긴다. 리프 노드가 아닌 비단말 노드는 인덱스 집합(Index Set)이라고 부르며 데이터로의 빠른 접근을 위한 인덱스 역할만 하기 때문에 키와 포인터로만 구성된다. 따라서 기존 B-Tree의 데이터를 모두 리프 노드로 내려서 리프 노드를 B-Tree의 구조 + 연결리스트로 구현된 색인 구조로 구성하여 순차적인 탐색에 유리하다.

B+Tree의 성질

1. 모든 데이터는 리프 노드에만 존재한다.
2. 모든 리프 노드는 연결리스트로 구성된다.
   • 다시 루트노드부터 내려와 데이터 순회 시 시간이 절약됨
3. 데이터의 삽입/삭제 연산은 리프 노드에서만 발생한다.
4. 모든 리프 노드의 첫 번째 key는 index set에 존재한다.

M차 B+Tree라고 가정하면 다음의 성질들을 만족해야 한다.

• 노드는 최대 M개부터 최소 $\lceil \cfrac{M}{2} \rceil$개까지의 자식을 가질 수 있다.
• 위 조건에 따라 노드는 최대 $M - 1$개부터 최소 $\lceil\cfrac{M}{2}\rceil-1$개의 키를 가질 수 있다.
  • 노드의 키가 $n$개라면 자식의 수는 $n+1$개이기 때문!
• 최소차수는 자식 수의 하한선을 의미한다. 따라서, 최소차수가 $t$라면 $M = 2t-1$이다. 최소차수가 적용되지 않는 노드는 root 노드이다.
  • key의 하한이 1개인 경우가 가장 차수가 낮을 것이다. $t-1=1$로 $t=2$가 되며 $M = 2t-1$이므로 3차 B+트리가 된다.

B+Tree에서의 검색(Search)

B-Tree와 동일하나 B-Tree는 Best Case의 경우 루트 노드에서 끝날 수 있지만 B+Tree는 모든 경우에 대해 리프 노드로 가서 순차 탐색함으로써 데이터를 찾아야 한다.

B+Tree에서의 삽입(Insert)

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

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

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

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

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

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

B+Tree에서의 삭제(Delete)

루트에서 출발하여 key가 속한 leaf 노드를 찾아 리프 노드의 key를 삭제한다. 삭제한 뒤 리프 노드가 최소 key 이상인지 체크해야 한다.

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

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

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

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

   • 형제 노드 중 하나라도 key의 개수가 $t-1$보다 큰 경우

     • 왼쪽 노드가 크다면 왼쪽 노드의 가장 큰 값을 받고 현재 노드의 첫 번째 값이 바뀌므로 부모 노드의 key도 바뀐 값으로 변경
     • 오른쪽 노드가 크다면 현재 노드는 변화가 없으나 우측 노드의 최솟값이 현재 노드로 옮겨감에 따라 우측 노드의 부모 key를 다음 값으로 바꿔준다.

   • 형제 노드가 모두 $t-1$인 경우

     • 어떤 경우라도 최소 차수를 만족할 수 없으므로 형제 노드들 중 하나와 병합해야 한다. 왼쪽 혹은 오른쪽 노드와 병합하되 왼쪽은 현재 노드의 부모 key, 오른쪽에 합치면 우측 노드의 부모 key가 삭제된다.
     • 부모 노드의 key 개수가 1 감소한 경우 부모 노드의 key 개수가 $t-1$미만이면 다시 reconstruct를 해야한다.

     

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

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

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

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

   • 형제 노드 중 하나라도 key의 개수가 $t-1$보다 큰 경우

     • 왼쪽에서 가져오면 현재 노드의 첫 번째 값이 바뀌므로 index set의 key 값도 가져온 값으로 교체
     • 오른쪽에서 가져오면 우측 노드의 첫 번째 값이 바뀌므로 index set의 기존 우측 노드의 첫 번째 값을 다음 값으로 교체

   • 형제 노드가 모두 $t-1$인 경우

     • 한쪽 형제와 현재 노드를 병합한다. 왼쪽과 병합한 경우 현재 노드의 부모 key를 삭제, 오른쪽과 병합한 경우 오른쪽 노드의 부모 key를 삭제한다.
     • 부모 key가 삭제되었으므로 부모 노드의 key 개수가 $t-1$미만이면 다시 reconstruct를 수행한다.

     

B*Tree란?

B-Tree의 개량된 형태이다. 순차 탐색 문제를 해결하기 위해 B+Tree가 제시된 것과는 달리 B*Tree는 B-Tree의 메모리 낭비, 보조 연산 문제를 해결하기 위해 제시되었다. 실제 대용량 시스템에서 B-Tree의 운용 시 전체 노드의 상당 부분이 비어있어 메모리 낭비 문제를 초래한다. 그리고 B-Tree의 삽입/삭제 연산 시 노드 혹은 key를 옮기는 등의 작업을 수행하는 분할, 병합 연산을 최소로 줄여 성능 개선을 도모하려는 취지에서 사용된다.

B*Tree의 성질

B*트리는 B-Tree에서 노드 최소용량의 차이의 변화가 주요하다.

1. 루트 노드를 제외한 모든 노드는 최대 $2t-1$에 대해 $\cfrac{2}{3}$이상의 자료가 저장되어야 한다.
   • B-Tree는 $t-1$이므로 약 절반 이상의 자료를 저장해야 했다.
2. 노드가 넘칠 경우(overflow) 일단 양쪽 형제 노드로 key들을 재분배한다. 그리고 모든 형제 노드가 전부 full 상태여야만 B-Tree의 분할 연산을 수행한다.
   • B-Tree는 현재 노드가 full이면 무조건 중간값을 부모 노드로 보내고 split했었다.