그림 10-2를 보면 왼쪽이 BST고 오른쪽이 4-way 검색 트리입니다. 찾고자 하는 키는 15입니다. 두 자료 구조 모두 하드 디스크에 저장되어 있다고 합시다. BST에서 노드는 하나의 키를 가지고 있기 때문에 하드 디스크에 저장된 노드를 읽어 오는 메모리 접근 횟수, 읽어 온 데이터를 찾고자 하는 키와 비교하는 연산 횟수 모두 트리 높이(height of tree)와 같습니다.

BST가 완전 이진 트리라면 트리 높이 h=log n이 되지요. 오른쪽의 4-way 검색 트리를 살펴보면 m이 2에서 4로 커지면서 트리 높이는 2로 줄어들었습니다. 하드 디스크에서 메인 메모리로 노드를 하나씩 가져온다고 했을 때 트리 높이가 줄어들었다는 이야기는 메모리 접근 횟수가 줄어들었다는 것을 의미합니다. 실제로 하드 디스크에서 메인 메모리로 가져올 때는 큰 단위로 가져오는 데, 가상 메모리가 적용된 시스템은 페이지(page) 크기(일반적으로 4kb=4096byte)만큼 가져옵니다. 그 대신 한 노드에서 찾고자 하는 키를 찾기 위해 선형 탐색을 하기 때문에 비교 연산 횟수는 늘어났지요.

메모리 접근 횟수는 줄어든 대신 비교 연산 횟수는 늘어났으니 결국 성능은 비슷하지 않나 하는 의문이 들 수 있지만 그렇지 않습니다. 이 자료 구조가 하드 디스크에 저장되어 있기 때문입니다. 비교 연산은 메인 메모리에 있는 두 값을 가져다 뺄셈 한 번만 하면(비교 연산은 CPU에서 두 수를 빼서 알아냄) 알 수 있습니다. 이때 두 값을 가져오는 데 40클럭이 걸립니다. 여기에 연산 후 값을 메모리에 쓰는 데 20클럭 그리고 뺄셈 연산에 1클럭을 더해 61클럭이면 충분하지만, 메모리 접근 횟수는 하드 디스크에 대한 접근이므로 한 번에 50만 클럭이 필요합니다. 자료 구조가 어디에 저장되어 있느냐에 따라 메모리 접근과 비교 연산의 차이가 이렇게도 극명하게 나는 것입니다.