B*Tree

• B-Tree의 노드의 추가적인 생성관 연산을 최소화하기 위해
• 삽입, 삭제 시 발생하는 노드 분리를 줄이려고 고안됨
• 노드가 가득찰 경우 분열 대신 형제 노드로 재배치
• 정렬되어있고 중복 X
• 모든 leaf node는 같은 레벨
• root node는 leaf node가 아닌 경우 적어도 2개 이상의 자식 노드를 가짐
• root node, leaf node 가 아닌 내부 노드는 2((M-2)/3) + 1 ~ M 개의 자식 노드를 가지고 있음

References

https://ssocoit.tistory.com/217

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