B Tree

B Tree는 다수의 키를 가진 Node로 구성되어 다방향 탐색이 가능한 균형 트리이다.

B Tree는 이진트리와 다르게, 하나의 노드에 다수개의 키를 저장할 수 있어, Tree의 높이를 낮추어 대용량 데이터 처리에 효율적임으로, 관계형 데이터베이스의 기본 자료구조로서 활용된다.

( 균형 트리란 ? 왼쪽,오른쪽 subtree의 높이 차이를 줄여, O(logN)의 시간복잡도를 가지고, 탐색,삼입,삭제 연산을 수행할수 있다. )

대표적으로 AVL Tree, RB Tree, B tree…등이 있다.

차수가 M인 B트리는 다음과 같은 정의를 갖는다.
(= 트리 노드의 최대 자식 노드의 개수가 M이며, 이떄 M은 2이상의 정수여야한다.)

  1. 모든 leef node는 동일한 깊이를 갖는다.
  2. 각 internal node의 자식수는 M/2 이상 , M 이하이다.
  3. Root Node의 자식수는 2 이상이다.
  4. Node의 key값들은 정렬된 상태를 유지한다.

탐색, 추가, 삭제연산

  • 탐색연산

이진트리와 동일하게 노드의 키값들을 루트노드에서부터 비교하며 적절한 subtree를 찾아 내려간다. 다만 노드의 키가 정렬된 여러 개의키로 구성되어 있음으로, 각 노드에서 이진 탐색트리를 수행하여, 적절한 서브트리를 찾는다.

  • 삼입연산

탐색과정을 거쳐, 새로운 키가 저장되야할 leef node를 찾고, 만약에 leef node에 새 키를 수용할 공간이 있으면, 정렬상태를 유지하도록 key를 삼입한다. 근데 만약에 M-1개의 키를 이미 가지고 있다면, 하나의 키가 추가되면 총 M개의 키에 차수의 개수는 M+1이 될 것이다.

따라서 Split연산을 통해서 M-1개의 키와 새로운 키 중에서 중간값이 되는 키를 부모노드로 올려보내고, 나머지 M-1개의 키들은 각각 위치에 맞게 저장한다.

split연산

위에 차수가 3인 B Tree에 45를 삼입하면 (25,35) Node에서 (25,35,45) 의 노드 키의 중간 키인 “35”를 부모노드로 올리고, 나머지인 25,45는 각각의 노드에 저장된다.

이러한 과정을 Split 연산이라고 한다.

  • 삭제연산

B트리에서 삭제연산은 항상 Leef node에서 일어난다. 이진 탐색트리의 삭제연산과 동일하게 , 중위선행자 (왼쪽 서브트리의 최댓값) 또는 중위 후속자 (오른쪽 서브트리의 최솟값) 과 삭제할 키를 교환한 후에 Leef node에서 삭제를 수행한다.

삭제연산은 여러가지 Case를 고려해야 한다.

먼저 B tree의 정의를 다시보면


각 internal node의 자식수는 M/2 이상 , M 이하이다.


즉, 삭제 후에 M/2이상의 노드가 남아있어야 하며, M/2이하의 노드가 남았을 경우에는 underflow가 발생했다고 하며, 이동연산(Transfer) 을 통해 underflow가 발생한 좌우의 형제노드 중에서 key를 하나가져와도 B 트리의 정의에 위배되지 않는 형제노드로부터 1개의 key를 부모 노드를 통해 이동시키는 연산을 수행한다.

만약 두 형제노드 모두 1개의 key를 주는 경우에, B트리의 정의가 위반된다면 underflow가 일어난 노드와 그 형제노드를 나눠주는 부모노드의 키를 하나의 노드로 통합시키는 통합연산(Fusion) 수행한다.

위와 같이 차수가 3인 B tree가 있다고 가정할떄,

첫번째로 이동연산이 일어나는 경우를 살펴보았다.
65를 삭제하면

  1. 65는 internal node임으로 중위후속자인 60과 swap
  2. 65를 leef node에서 삭제
  3. underflow 발생, 형제노드에서 부모노드를 거쳐 key를 가져올 수 있는 지 확인
  4. 70 을 부모노드로 이동시키고, 60을 부모노드로부터 key로 받음

두번째로 통합연산이 일어나는 경우를 살펴보았다.
70을 삭제하면,

  1. 70은 internal node임으로 중위후속자인 60과 swap
  2. 70을 leef node에서 삭제
  3. underflow 발생하여, 형제노드에서 부모노드를 거쳐 key를 가져올 수 있는지 확인하였으나, 형제노드도 key를 가져오면 underflow발생함.
  4. 형제노드(80),underflow일어난 노드, 부모노드의 분기점 key(60)를 하나의 노드로 Fusion한다.

Reference

  1. 이동, 통합연산 이미지 (http://booryq.blogspot.com/2015/11/here-science-behind-perfect-b-tree.html)
  2. split연산 이미지 (https://www.programiz.com/dsa/insertion-into-a-b-tree)
  3. 양성봉 저 - 파이썬과 함께하는 자료구조의 이해 (http://www.yes24.com/Product/Goods/57949931)

Comments