B 트리는 m-way 탐색 트리(m-way search tree)의 일종입니다. 여기서 m은 노드가 가질 수 있는 최대 자식 개수를 의미합니다. BST의 노드는 자식을 두 개 가질 수 있지요. 그러므로 BST는 2-way 탐색 트리입니다. 자식은 둘이지만 노드가 가지는 키는 하나입니다. 이를 일반화하면 m-1은 노드가 가질 수 있는 최대 키 개수입니다.

m-way 검색 트리에서 중요한 점은 노드에 키가 여러 개 있을 수 있다는 것이지요. 여기서 한 가지 궁금점이 생깁니다. 노드에 키가 하나일 때와 여러 개일 때 어떤 차이가 있을까요? 어떤 상황에서 노드에 키를 여러 개 두어야 할까요? 이진 탐색 트리가 결국에는 선형 탐색을 피하고자 트리에 이진 탐색을 적용한 것인데, m을 1001처럼 큰 수로 잡는다면 다시 선형 탐색으로 회귀하는 모습이지요. 노드에 있는 키 개수 차이는 메모리 접근 횟수와 비교 연산 횟수의 차이를 의미합니다.

그림으로 확인해 봅시다.

▲ 그림 10-2 m-way 검색 트리 비교