백인감자

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

데이터베이스

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

백인감자 2017. 7. 8. 14:20

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


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글자만 입력되어서 글자가 잘렸으니 주의.




6 Comments
  • 프로필사진 ㅎㅎ 2017.12.05 00:24 혹시 B-tree의 6번 규칙이 어디서 나왔는지 아시나요??
  • 프로필사진 백인감자 2017.12.12 23:39 신고 http://www.cs.cornell.edu/courses/cs211/2000fa/AccelStream/B-Trees.pdf


    제가 게시글에 참고로 올려놓은 링크를 참조하였고 연습삼아 B-Tree 를 계속 만들다 보면 6번 규칙이 항상 성립함을 확인할 수 있습니다.
  • 프로필사진 질문 2018.09.15 10:53 위의 예에서..원소가 t개 이상일때, 삭제를 하면 단말노드에서만 key를 삭제하면 되는데 왜 부모 노드가 merge를 하죠?
  • 프로필사진 질문 2018.09.28 14:40 자세한 설명으로 b트리 이해하는데 큰 도움이 되었습니다.
    허나 질문이 하나 있는데..

    b트리 삭제 case2의 a)예시에서 보면 x, x's sibling node 중 한 개, x's parent node 를 merge 한다 라고 하였는데
    그림을 보면 x, x's silbling node, x's parent node가 모두 merge를 하였습니다.
    이 부분에 대해 설명 좀 부탁드립니다.
  • 프로필사진 백인감자 2018.11.09 15:55 신고 안녕하세요 해당 그림에서 x's sibling node 가 1개 밖에 존재하지 않기 때문에
    x, x's sibling node, x's parent node가 모두 merge를 한 것입니다. 제 포스팅에서 node(노드) 와 element(원소) 에 대해서 설명이 헷갈렸을 수도 있을 것 같은데 한 번 확인부탁드릴게요~

    node x --> 0004,0008이 있는 사각형
    node x's sibling--> 0014,0017 이 있는 사각형
  • 프로필사진 질문충 2019.05.07 23:26 좋은 글 잘봤습니다. 이렇게 그림으로 잘 나타낸 포스트를 찾았는데 정말 도움이 많이 되었습니다.
    다만 질문이 있는데 m/2의 천장함수를 t라고 하셨는데 internal node 8을 삭제할 때 양쪽이 둘다 element수가
    ceil(m/2)-1개라고 하셨는데 여기서는 m이 3아닌가요? 루트의 자식이 3개라서 3-way search, 즉 m=3인 b tree라고 생각했는데 혹시 아닌가요?
    그래서 제 생각엔 양 쪽 노드가 2개니까 ceil(m/2)개 라고 생각하는데 뭐가 틀린거죠 ㅠㅠ
댓글쓰기 폼