검색을 위한 자료구조 중에서 잠재력이 가장 큰 것은 이진 트리입니다. 비록 하나의 부모가 두개의 자식밖에 가지질 못하고, 자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지긴 하지만요.
그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있어서, 이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔습니다.
그 중에서도 이번 장에서는 두마리의 토끼를 모두 잡은 B-트리에 대해 알아봅니다.