B-트리

• 이진트리를 확장한 트리이다.
• 하나의 노드가 가질 수 있는 자식노드의 갯수가 여러개(쵀대 숫자가 2이상)인 트리 구조를 의미
• 대량의 데이터를 메모리가 아닌 디스크에서 효율적으로 읽고 쓰기 위해 설계되었다.

B-트리의 특징

• 균형트리이다.
• 모든 리프 노드가 같은 위치를 갖고 있게 설계되어 있다.
• 따라서 검색에 걸리는 시간이 일정하다.
• 노드가 꽉 찰 때 분할하고, 특정 수준 이하로 내려가면 병합한다.
• B+, B*, B# 등 다양한 변형이 존재한다.