📚 Reference

📜 Chapter

‣

BST (Binary Search Tree)

B-Tree

B-Tree
B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리이다.
또한 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조 중 한 종류라고 한다.
실제 DB에서는 B트리에서 발전한 B+트리를 실제로 사용한다.

B-Tree 특징

B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다.
최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며 다음과 같은 특징을 갖는다.