[CS] B- tree

0. B Tree 시리즈의 효용에 대해서는 (아주) 간단히 아래 글에 정리해놓음

*하나의 노드에 여러 자료를 배치하며, 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담음

https://lets-hci-la-ai-withme.tistory.com/190

 

*일반적으로 이진트리를 다룰 때, 하나의 노드에는 하나의 데이터가, 둘 이하의 자식 노드.

B-Tree(비 트리)

'균형' 이진 탐색 트리의 일종- 그러나 자식 노드를 2개 이상 가질 수 있음

핵심 성질 1: 하나의 노드가, 최대 M개의 자식을 가질 수 있음 (M차 B-Tree)

*internal nodes는 모두 2개 이상의 자식을 가져야 함

핵심 성질 2: 하나의 노드 내에, 2개 이상의 key(데이터)가 저장될 수 있음

 

M차 B-Tree는,

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

1. internal nodes의 자식 개수: ceil(M/2) ~ M개 - M값과 자식 개수의 관계

2. 각 노드 내 key의 개수: floor(M/2)-1 ~ (M-1)개 (항상 정렬된 상태, 중복 허용x)  - M값과 k의 관계

3. 한 노드 key의 개수 k에 따라, 그것의 자식 노드의 개수가 k+1로 결정됨 - k와 자식 개수의 관계

4. 특정 노드의 left subtree는 특정 노드 내 '모든 keys'보다 작은 값으로, right subtree는 큰 값으로 정렬

5. 모든 leaf nodes가 같은 레벨에 존재함

 

1) Search가 아주 쉽다 (하향식)

2) Insertion은 좀 복잡하다 (하향해서 적당한 leaf 자리 찾은 후 '적절한 상태'가 되기까지 상향)

case1: 분리가 일어나지 않는 경우 (상향 불필요)

case2: 분리가 일어나는 경우 (상향 필요)

 

3) Deletion은 더 복잡하다...

 

---

아주 훌륭한 레퍼런스들,,

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

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

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정

https://escapefromcoding.tistory.com/731

DB의 인덱스와 B-tree, B+tree