B-Tree가 디스크에 맞는 이유는?

노드 하나에 키를 많이 담아 트리 높이를 낮추기 때문이다. 디스크는 한 번 갈 때마다 값을 치른다.

이진 탐색 트리는 노드마다 키가 하나다. 균형이 잡혀 있어도 백만 개면 높이가 스물쯤 되고 내려가는 만큼 디스크를 읽는다. 한쪽으로 기울면 더 나빠진다.

B-Tree는 한 노드를 디스크 블록 크기에 맞춘다. 한 번 읽어 온 블록 안에서 여러 번 비교하므로 내려가는 횟수가 준다. 같은 백만 개라도 서너 번이면 닿는다.

메모리 안에서만 논다면 이 이점이 거의 없다. 읽어 오는 값이 싸기 때문이다. 그래서 인메모리 구조로는 다른 것을 쓴다.

B-Tree는 비교 횟수보다 디스크 읽기 횟수를 줄인다. 총 비교 횟수는 오히려 늘 수도 있다.