Статические поисковые деревья: когда правильная структура обставляет бинарный поиск на 40×

Статья 2024 года, занявшая первое место на Hacker News сегодня, показывает, как более продуманная организация памяти делает статическую структуру в 40 раз быстрее, чем бинарный поиск. Настоящий урок не в цифре — это само рассуждение.

Конкретный случай: вам нужно найти ключ в отсортированном массиве из 100 миллионов записей. Ваш первый рефлекс, полученный в школе, — это бинарный поиск — log₂(n) ≈ 27 сравнений. Теоретически оптимально.

Но… в 2026 году на современном CPU бинарный поиск катастрофичен. Почему? Потому что каждое сравнение считывает ячейку, адрес которой зависит от предыдущего результата. Процессор не может ни предсказать, ни предварительно загрузить, ни конвейеризировать данные. На каждом шаге он ожидает промах кэша (около 100 тактов CPU, или ~30 нс на современной DDR5).

Что делает статья

Статья «Static search trees: 40x faster than binary search» (2024, переиздана в топе HN сегодня) исследует именно эту проблему. Предложенное решение — это статическое B-дерево — не динамическое B-дерево из учебника по базам данных, а версия, оптимизированная под CPU:

• Раскладка Эйцингера (названа в честь австрийского генеалога XVI века, придумавшего систему нумерации деревьев) или бесветвленное B-дерево: дочерние узлы одного узла расположены непрерывно в памяти.
• Узлы калибруются под строку кэша (обычно 64 байта, то есть 16 ключей по 4 байта).
• SIMD-сравнения (Single Instruction Multiple Data — одна инструкция обрабатывает несколько данных одновременно): в одном узле сравнение 16 ключей выполняется одной инструкцией AVX2/AVX-512.
• Программный prefetch: как только вы входите в узел, запускается предварительная загрузка (__builtin_prefetch) вероятного дочернего узла.

Результат, измеренный в статье: на 100 миллионах записей поиск занимает от ~150 нс до 4 нс. То есть в 40 раз быстрее.

Что нужно запомнить

Урок не в том, что «бинарный поиск умер». А в том, что классическая алгоритмическая сложность (O log n) игнорирует кэш-память. На современном CPU структура, минимизирующая промахи кэша, почти всегда побеждает ту, что минимизирует сравнения.

Другие примеры, с которыми мы сталкиваемся в наших проектах:

• Хеш-карты «робингуд» (Emmanuel Goossaert, Google Abseil flat_hash_map) против классического std::HashMap.
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters — используется в Rust slice::sort_unstable) против школьного quicksort.
• Фильтры Блума перед точными поисками для быстрого отсеивания отрицательных результатов.
• Хранилища с колоночной организацией (Parquet, ClickHouse), которые используют строки кэша для аналитики.

Что почитать дальше

• Работа Поля-Вирака Кхунга и Пэта Морина (2015): Array Layouts for Comparison-Based Searching — академическая база всего этого направления.
• «What Every Programmer Should Know About Memory» (Ульрих Дреппер, 2007) — морально устарела в деталях, но основа остается актуальной.
• Крейт Rust static-search-tree или аналогичный пример для практического применения.

Запомните

Когда оптимизируете горячий цикл, первым профайлером должен быть не cachegrind — это perf stat -e cache-misses,cache-references под Linux (или Instruments на macOS). Именно здесь в 2026 году решается реальная производительность. Теория сложности говорит, что возможно; кэш-память — что достижимо.