정적 검색 트리: 좋은 구조가 이진 검색을 40배나 능가하게 만들 때

2024년 기사 하나가 오늘 헤커 뉴스 상단에 다시 올라왔는데, 더 잘 설계된 메모리 레이아웃이 이진 탐색보다 정적 구조를 40배나 빠르게 만든다는 내용을 담고 있습니다. 중요한 교훈은 그 숫자가 아니라, 그 추론 방식이라는 점입니다.

실제 사례: 1억 개의 항목으로 정렬된 배열에서 키를 검색해야 합니다. 학교에서 배운 첫 번째 방법은 binary search(이진 탐색)입니다. log₂(n) ≈ 27회의 비교가 필요합니다. 이론적으로는 최적입니다.

그런데… 2026년, 현대 CPU에서 binary search는 katastrofik(재앙적)입니다. 왜일까요? 각 비교가 이전 결과에 따라 달라지는 메모리 주소를 읽기 때문입니다. 프로세서는 예측, 사전 로딩, 파이프라이닝을 할 수 없습니다. 매 단계마다 캐시 미스(최신 DDR5 기준 약 100 CPU 사이클, 약 30ns)를 기다려야 합니다.

이 글에서 다룬 내용

2024년 작성된 「Static search trees: 40x faster than binary search」라는 글(오늘 HN 헤드라인에 다시 게재됨)은 정확히 이 문제를 다룹니다. 제안된 해결책은 정적 B-tree입니다. 데이터베이스 교과서의 동적 B-tree가 아니라 CPU 최적화 버전입니다.

• Eytzinger Layout (16세기 오스트리아 유전학자 Eytzinger가 고안한 트리 번호 매기기 시스템) 또는 B-tree branchless: 노드의 자식들이 메모리에서 연속적입니다.
• 캐시 라인(64바이트, 4바이트 키 16개)에 맞춰 노드 크기 조정
• SIMD 비교: 한 노드에서 16개의 키를 AVX2/AVX-512 한 번의 명령으로 비교
• 소프트웨어 프리페치: 노드에 진입하자마자 예상 자식 노드(__builtin_prefetch)를 미리 로드

글에서 측정한 결과: 1억 개의 항목에서 검색 시간이 약 150ns에서 4ns로 떨어졌습니다. 40배나 빨라졌습니다.

핵심 요점

교훈은 “binary search가 죽었다”가 아닙니다. 고전적 알고리즘 복잡도(O log n)는 캐시 메모리를 무시한다는 점입니다. 현대 CPU에서 캐시 미스를 최소화하는 구조가 비교 횟수를 최소화하는 구조보다 거의 항상 더 빠릅니다.

우리가 프로젝트에서 접하는 다른 예시:

• ‘로빈 후드’ 해시 맵 (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. 기존 std::HashMap
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters - Rust slice::sort_unstable에 사용) vs. 학교식 quicksort
• Bloom filters: 부정확한 검색을 빠르게 걸러내기 위한 사전 필터
• 컬럼 지향 저장소 (Parquet, ClickHouse): 분석 작업 시 캐시 라인을 활용

다음에 읽을 자료

• Paul-Virak Khuong과 Pat Morin(2015)의 논문: Array Layouts for Comparison-Based Searching - 이 분야의 학문적 기반
• Ulrich Drepper(2007)의 「What Every Programmer Should Know About Memory」 - 일부 세부 사항은 outdated되었지만 기본 개념은 유효
• Rust crate static-search-tree 또는 실용 예시를 위한 동등한 라이브러리

기억하세요

핫 루프(hot loop)를 최적화할 때 첫 번째로 꺼내야 할 프로파일러는 cachegrind가 아닙니다. Linux의 perf stat -e cache-misses,cache-references(또는 macOS의 Instruments)입니다. 2026년의 진정한 성능은 여기에서 결정됩니다. 복잡도 이론은 무엇이 가능한지를 말해주지만, 캐시 메모리는 무엇이 도달 가능한지를 결정합니다.