B-Tree

• 정렬된 균형이진트리
• 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있음
• 중복없음
• 모든 leaf node는 같은 레벨에 있음
• root node는 자신이 leaf node가 아닌 이상 최소 2개 이상의 자식을 가짐
• 내부 노드(root, leaf node 이외) M/2 ~ M개의 자식을 가짐
• 노드는 M/2 - 1 ~ M - 1 개의 데이터(키)가 포함될 수 있음
• 자식 수의 하한값이 t, M = 2t - 1
• 데이터가 k, 자식 노드의 수는 k+1
• 검색은 O(logn)

구조 유지를 위해 추가적인 연산이 수행되거나 새로운 노드를 생성함 -> 최소화를 위해 B*Tree 등장

탐색을 위해서 노드를 찾아서 이동해야함 -> 해소를 위해 B+Tree 등장

아래의 조건 위반 시 재구조화

• 내부노드는 M/2 ~ M개의 자식을 가짐
• 각 노드는 M/2-1 ~ M/2 개의 데이터를 가짐
• 노드의 key가 k개, 자식 노드의 개수는 k+1개

삭제 시

리프 노드 삭제 - 최소 유지 개수 조건을 만족하는 경우 - 만족못할 경우 형제 노드에게 빌려올 수 있는 경우 - 못 빌려온 경우 부모 노드를 분할 할 수 있는 경우 - 분할도 안되는 경우(합치고, 서로 부모-자식이 되도록 연결 후 분할/합친다)

내부 노드 삭제 - 최소 유지개수의 최소보다 큰 경우(왼쪽 자식 중 가장 큰 노드, 오른쪽 자식 중 가장 작은 노드와 자리를 바꿔주고 이후 처리) - 크지 않고 최소인 경우(합치고, 서로 부모-자식이 되도록 연결 후 분할/합친다)

삽입 시

1. 데이터를 삽입할 리프 노드 탐색
2. 데이터 삽입
3. 적절한 상태가 아니면 분리

 

 

Reference

https://ssocoit.tistory.com/217

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

https://code-lab1.tistory.com/217

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정