B-tree는 왜 디스크에 유리한가?

한 번 읽을 때 많이 가져오기 때문이다. 디스크는 블록 단위로 읽으므로 노드 하나를 블록만큼 크게 잡으면 읽기 횟수가 준다.

균형 잡힌 이진 트리도 백만 건이면 깊이가 스물이다. 갈래를 백으로 늘리면 셋이면 닿는다. 캐시가 비어 있다면 깊이만큼 디스크를 읽는다.

모든 잎이 같은 깊이에 있다. 넣고 지울 때 노드를 쪼개거나 합쳐서 균형을 지키므로 최악도 O(log n)을 지킨다.

위쪽 노드는 대개 버퍼 캐시에 남아 있어 실제 읽기는 깊이보다 적다. 메모리만 쓰는 색인에서는 이 이점이 줄어든다.