B+ Tree

B+ 트리는 키에 의해서 식별되는 레코드의 효율적 삽입, 검색, 통해 정렬된 데이터를 표현하기 위한 자료구조입니다.

 

다음과 같은 특성이 있습니다.

 

B+ tree는 root, internal nodes, leaves로 구성됩니다.

 

B+ 가치는 블록 중심 storage context 특히 파일 시스템에서 효율적을 검색을 위해 데이터를 저장하는 것입니다.

 

- insert

 

차수 M이 홀수인 경우 t-1번째 index를 상위로 올리고, 차수 M 이 짝수인 경우 t번째 index를 상위로 올립니다.

 

 

 

- delete

 

삭제의 경우에는 다양한 케이스가 존재하는데

 

삭제할 키가 leaf node에만 존재할 때

 

- 노드의 최소 개수 이상의 키가 있을 때는 간단하게 키를 삭제하면 됩니다.

 

- 노드에 최소 개의 키가 있을 때는, 키를 삭제하고 sibling에서 키를 빌려 중간 키를 parent에 추가합니다.

 

 

 

 

 

 

 

 

 

 

 

그래프 그리기 - https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

 

 

참조

[1] - https://potatoggg.tistory.com/174

[2] - https://en.wikipedia.org/wiki/B%2B_tree

[3] - https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC