B Tree
B Tree는 다수의 키를 가진 Node로 구성되어 다방향 탐색이 가능한 균형 트리이다.
B Tree는 이진트리와 다르게, 하나의 노드에 다수개의 키를 저장할 수 있어, Tree의 높이를 낮추어 대용량 데이터 처리에 효율적임으로, 관계형 데이터베이스의 기본 자료구조로서 활용된다.
( 균형 트리란 ? 왼쪽,오른쪽 subtree의 높이 차이를 줄여, O(logN)의 시간복잡도를 가지고, 탐색,삼입,삭제 연산을 수행할수 있다. )
대표적으로 AVL Tree, RB Tree, B tree…등이 있다.
차수가 M인 B트리는 다음과 같은 정의를 갖는다.
(= 트리 노드의 최대 자식 노드의 개수가 M이며, 이떄 M은 2이상의 정수여야한다.)
- 모든 leef node는 동일한 깊이를 갖는다.
- 각 internal node의 자식수는 M/2 이상 , M 이하이다.
- Root Node의 자식수는 2 이상이다.
- Node의 key값들은 정렬된 상태를 유지한다.
탐색, 추가, 삭제연산
- 탐색연산
이진트리와 동일하게 노드의 키값들을 루트노드에서부터 비교하며 적절한 subtree를 찾아 내려간다. 다만 노드의 키가 정렬된 여러 개의키로 구성되어 있음으로, 각 노드에서 이진 탐색트리를 수행하여, 적절한 서브트리를 찾는다.
- 삼입연산
탐색과정을 거쳐, 새로운 키가 저장되야할 leef node를 찾고, 만약에 leef node에 새 키를 수용할 공간이 있으면, 정렬상태를 유지하도록 key를 삼입한다. 근데 만약에 M-1개의 키를 이미 가지고 있다면, 하나의 키가 추가되면 총 M개의 키에 차수의 개수는 M+1이 될 것이다.
따라서 Split연산을 통해서 M-1개의 키와 새로운 키 중에서 중간값이 되는 키를 부모노드로 올려보내고, 나머지 M-1개의 키들은 각각 위치에 맞게 저장한다.
위에 차수가 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를 삭제하면
- 65는 internal node임으로 중위후속자인 60과 swap
- 65를 leef node에서 삭제
- underflow 발생, 형제노드에서 부모노드를 거쳐 key를 가져올 수 있는 지 확인
- 70 을 부모노드로 이동시키고, 60을 부모노드로부터 key로 받음
두번째로 통합연산이 일어나는 경우를 살펴보았다.
70을 삭제하면,
- 70은 internal node임으로 중위후속자인 60과 swap
- 70을 leef node에서 삭제
- underflow 발생하여, 형제노드에서 부모노드를 거쳐 key를 가져올 수 있는지 확인하였으나, 형제노드도 key를 가져오면 underflow발생함.
- 형제노드(80),underflow일어난 노드, 부모노드의 분기점 key(60)를 하나의 노드로 Fusion한다.
Reference
- 이동, 통합연산 이미지 (http://booryq.blogspot.com/2015/11/here-science-behind-perfect-b-tree.html)
- split연산 이미지 (https://www.programiz.com/dsa/insertion-into-a-b-tree)
- 양성봉 저 - 파이썬과 함께하는 자료구조의 이해 (http://www.yes24.com/Product/Goods/57949931)