해시가 더 빠른데 왜 안 쓰나

해시 인덱스의 조회는 O(1)이다. B-Tree는 O(log N)이다. 그런데도 관계형 데이터베이스의 기본 인덱스는 거의 예외 없이 B-Tree다.

이유는 두 가지다. 해시는 범위를 다룰 수 없고, 애초에 비교 횟수가 병목이 아니기 때문이다.

범위 질의

해시는 키를 흩뿌리는 게 목적이라 인접한 값이 인접한 위치에 있지 않다. WHERE age BETWEEN 20 AND 30 같은 질의도, ORDER BY created_at도 도와줄 수 없다. 실무 질의의 상당수가 여기 해당한다.

진짜 비용은 디스크 접근 횟수

디스크는 바이트 단위로 읽지 않는다. 페이지(보통 8~16KB) 단위로 통째로 읽는다. 한 번의 접근 비용이 메모리 연산보다 압도적으로 크기 때문에, 비교를 몇 번 하느냐보다 디스크를 몇 번 건드리느냐가 성능을 결정한다.

이진 트리는 노드마다 자식이 둘이라 높이가 log₂N으로 자란다. 1억 건이면 높이가 27, 최악의 경우 디스크 접근 27번이다.

B-Tree는 노드 하나를 페이지 크기에 맞춰 채운다. 키가 작으면 노드 하나에 수백 개가 들어가고, 자식도 그만큼 갈라진다. 분기 수가 500이면 높이 3으로 1억 건을 덮는다. 디스크 접근 서너 번이면 끝난다.

B+Tree가 실제로 쓰이는 형태

대부분의 구현은 B-Tree의 변형인 B+Tree다.

정리

B-Tree는 “빠른 자료구조”라서 선택된 게 아니다. 디스크가 블록 단위로 동작한다는 제약에 맞춰 설계된 자료구조라서 선택됐다. 모든 데이터가 메모리에 들어가는 환경이라면 답은 달라질 수 있다.