[DB/자료구조] B-Tree(B트리), B+ 트리

*부정확한 부분이 있으면 피드백 해주시면 감사하겠습니다.

B-Tree

---

참고 : http://nextcube.tistory.com/m/196

http://scanftree.com/Data_Structure/deletion-in-b-tree

http://www.cs.cornell.edu/courses/cs211/2000fa/AccelStream/B-Trees.pdf

B-tree 를 직접 만들어 보며 확인하는 사이트

http://www.cs.usfca.edu/~galles/visualization/BTree.html

아래와 같이 용어들을 같다고 전제하고 작성하였습니다.

external node == leaf node 

order ==degree 

element==key

⌈⌉ 는 올림 연산을 뜻한다. ⌈3/2⌉=2  이다.

⌈M/2⌉ =t 라고 정의.

M : tree 의 degree

B- Tree 특성

1. root node 가 leaf node 인 경우를 제외하고는 항상 최소 2개의 children 을 가진다.

2. root node 와 leaf node 를 제외한 모든 node 들은 최소 ⌈M/2⌉  , 최대 M 개의 서브트리를 가진다.

3. 모든 leaf node 들은 같은 level 에 있어야한다.

4. 새로운 key 값은 leaf node 에 삽입된다.

5.  node 내의 key 값들은 오름차순이다.

6. leaf node 는 최소  ⌈M/2⌉ -1 개 의 key 를 가지고 있어야 한다.

B-트리(B-tree) 삽입

---

새로운 원소(element)는 leaf node 에 삽입된다.

node에 overflow 가 발생되면(key = M 개) 노드의 t -1 번째 key 를 parent 로 올리고 노드 분할을 한다.

--> 원서를 참고했을 때 중간값을 parent 로 올린다 되어있는데 M 이 짝수일 때의 중간값이 모호해서 visualization tool 로 확인한 결과 t-1 번째 key 이다.

참고:  https://stackoverflow.com/questions/29580238/which-element-is-the-middle-in-a-b-tree-of-even-order

쉽게 생각하면 차수가 홀수이면 가운데 값, 짝수이면 절반으로 나눴을 때 왼쪽그룹의 최댓값이 split point 가 된다.

M=4 인 경우 1, 2, 3, 4 순서로 삽입이 되면 t - 1 번째 key 는 2 이다. 2가 parent node 가 된다.

 

아래 그림은 M=5 인 B-Tree 의 삽입 예시이다.

입력순서 : a g f b k d h m j e s i r x c l t u p  총 20개

b) 에서 k가 삽입되었을 때 t= 3 이고 3번째 key 값인 f 가 상위 레벨로 올라간다.

B-트리(B-tree) 삭제 

---

삭제의 대상은 모든 node 의 원소가 가능하다. 대신, 삭제를 하기 위해서 leaf node 로 해당 원소를 이동시켜야한다.

삭제 연산의 규칙은 꽤 복잡하므로 아래와 같이 정리하였다.

case 1. internal node 삭제하는 경우

삭제할 원소가 k 이고 해당 node를 y 라 하면 k 의 child node 중 원소 수가 t 이상인 child node 로 k를 보낸 후 삭제하고 

child node 가 left 이면 최대값을 , right 이면 최소값을 y로 올린다. (borrow)

만약 y의 child node 둘 다 t -1 개의 최소 개수를 가지고 있으면 두 child node 를 merge 시킨다.

ex. 차수 M=6

원소 5를 삭제 (borrow)

left, right child 둘 다 t 개 이상이기 때문에 left child 를 선택해서 4가 parent 로 올라갔다.

원소 4 삭제 (borrow)

right child만 t 개 이상이기 때문에 4는 삭제되고 8이 parent 로 올라가게 된다.

원소 8 삭제 (merge)

child node 둘 다 t -1 개 이므로 merge 수행

case 2. leaf node 삭제하는 경우

개인적으로 삭제에서 가장 헷갈린다 생각하는 부분이다.

삭제할 원소가 k 이고 해당 node를 y , y의 parent node 를 x 라 하면,

a)

y의 원소 수가 t 개 이상이면 

1. 원소 k 삭제 수행

2. 만약 x 와 x의 sibling node 둘 다 원소 수가 t -1 개 이면 원소 k 삭제 후 x, x's sibling node 중 1개 , x's parent node 를 merge 한다.  

M=6 

원소 1 삭제

b)

y의 원소 수가 t -1 개 일 때 삭제할 경우 ( underflow 발생 시 ) 

b-1. y 의 sibling node z 의 원소 수가 t 개 이상 이면 원소 k 삭제 후 x에서 y로 원소 보내고 z에서 x로 원소 보낸다. ( borrow operation )

b-2. z 도 t-1 개이면 원소 k 삭제 후 underflow 가 발생하고 parent node 의 원소를 가져와서 y, z 와 merge 한다. ( merge operation)

parent node 의 key 개수가 t-1 이 되면 재귀적으로 위 과정을 반복해서 underflow 를 해결한다.

M=6

원소 2 삭제 후 원소 3 삭제 

아래 예시는 차수 M=6 인 B-tree 이다. t=[M/2]=3 이다.

같은 방식을 숫자로만 적용했을 때의 그림이다.

초기상태

6 삭제 Case-I

13 삭제

7 삭제 Case-II-c

4 삭제 Case-III-b

2 삭제 Case-III-a

B+ 트리

---

Index node 들과 data node(레코드) 로 구성이 되어있다 .

Index node : leaf node 를 제외한 나머지 node 들.

Data node : leaf node 를 일컫는 동의어.

Data node 는 연결리스트로 형성되어있고  Data node 하나의 크기는 Index node 하나의 크기와 똑같지 않아도 된다.

B+ 트리의 높이는 B 트리 보다 낮게 구성되므로 검색시간과 디스크에 접근하는 횟수가 줄어든다.

index node 에 존재하는 key는 자신의 right subtree 의 data node 의 가장 첫번째 위치에 존재하게 된다.

삽입

overflow 발생 시 차수에 따라 방식이 다르다.

차수 M 이 홀수인 경우 : t-1 번째 index 를 상위로 올린다.

차수 M=5

차수 M 이 짝수인 경우 : t 번째 index 를 상위로 올린다. (B 트리의 짝수 overflow 와의 차이점)

이렇게 해야 정확히 반으로 쪼갤 수 있기 때문이다. 직접 트리를 그리면서 balance 가 맞춰지는 것을 확인하는게 더 이해가 빠를것이다.

차수 M=6

삭제

B 트리는 삭제과정이 복잡하지만 B+ 트리는 data node  에서 삭제를 수행한다. 삭제 된 key 값이 index node 에 존재한 경우 재귀적으로 확인하여 index node 를 변경시킨다.

삭제하는 원소 k 가 있는 node 를 y라 하면

1. y 의 key 개수가 t 개 이상이면 원소 k 삭제 후 index node 에 k 가 있으면 index node 에서도 삭제 후 적절한 key 값을 그 자리에 넣는다.

예시. 차수 M=4

leaf node의 3 삭제 후 index node 의 3도 삭제된다. 그 후  4를 추가해준다.

2. y 의 key 개수가 t-1 개 이면 y 의 sibling node z 의 원소 수가 t 개 이상인 경우 borrow 한다.

원소 k 삭제 후 x에서 y로 원소 보내고 z에서 x로 원소 보낸다.

삽입 삭제과정은 직접 본인이 수행하면서 확인하는 게 좋은 것 같다.

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

연습문제 ( 기술고시 기출문제 )

tree 이미지에서 node 에 글자가 4글자만 입력되어서 글자가 잘렸으니 주의.

B-tree

mouse 삭제

B+ tree

mouse 삭제