결론은 나왔습니다. 하드 디스크에 상주하는 자료 구조를 설계한다면 한 노드에 최대한 많은 키를 담아 메모리 접근 횟수를 줄여야 합니다. 그렇다고 노드 크기를 무작정 늘릴 수도 없습니다. 그렇게 되면 노드 크기가 페이지 크기를 넘게 되어 한 번에 한 노드를 가져올 수 없기 때문입니다. 그래서 실제로는 페이지 크기에 맞추어서 m 값을 수백 정도로 설정합니다.

B 트리는 m-way 탐색 트리의 일종입니다. 먼저 m-way 탐색 트리를 정의해 보겠습니다.

1. 서브 트리를 최대 m개 가집니다.

2. 한 노드에서 key는 정렬되어 있습니다.

3. 어떤 키 K의 왼쪽 서브 트리의 모든 키는 K보다 작습니다.

4. 어떤 키 K의 오른쪽 서브 트리의 모든 키는 K보다 큽니다.

5. 서브 트리도 m-way 탐색 트리입니다.

세 번째와 네 번째 특징은 마치 BST와 유사합니다. 탐색 트리는 모두 BST를 기반으로 하기 때문입니다. 그림 10-2와 비교하면서 읽어 보면 훨씬 쉽게 이해할 수 있을 것입니다. 여기에 더해 B 트리의 특징도 알아볼까요? 차수가 m인 B 트리는 다음과 같이 정의할 수 있습니다.

1. 2 < = 루트 노드의 서브 트리 개수 < = m

2. m/2 < = 루트를 제외한 노드의 서브 트리 개수 < = m

3. m/2 -1 < = 루트를 제외한 노드의 키 개수 < = m-1

4. 모든 리프 노드는 같은 레벨에 있습니다.