静的検索ツリー：良い構造がバイナリ検索を40倍にする

2024年の記事が、今日Hacker Newsのトップに戻ってきました。この記事では、よりよく考えられたメモリレイアウトが、バイナリサーチよりも40倍速い静的な構造を実現する方法を示しています。真の教訓は数字ではなく、その推論です。

具体例：100百万エントリのソート済み配列からキーを検索する必要があります。最初の反射は、学校で学んだバイナリサーチです - log₂(n) ≈ 27 比較。理論的に最適です。

しかし… 2026年、現代のCPU上では、バイナリサーチは災難です。なぜか？ それぞれの比較は、前の結果に依存するアドレスのメモリを読み込みます。プロセッサは予測できず、事前読み込みできず、パイプライン化できません。各ステップで、キャッシュミスを待ちます（約100 CPUサイクル、DDR5最新では~30 ns）。

この記事で行うこと

2024年の記事「Static search trees: 40x faster than binary search」（本日HNのトップに再掲載）は、この問題を深掘りしています。提案されたソリューションは静的Bツリー - データベースのマニュアルにある動的Bツリーではなく、CPU向けに最適化されたバージョンです：

• レイアウト・アイツィンガー（16世紀のオーストリアの系図学者の名前）またはブランチレスBツリー：ノードの子はメモリ上で連続しています。
• キャッシュラインに合わせたノード（典型的には64バイト、4バイトのキーが16個）。
• SIMD比較（Single Instruction Multiple Data - 1つの命令で複数のデータを処理）：ノード内で16のキーを1つのAVX2/AVX-512命令で比較。
• ソフトウェアプレフェッチ：ノードに入るたびに、推定される子ノードの事前読み込みを開始します（__builtin_prefetch）。

記事で測定された結果：100百万エントリで、検索は約150 nsから4 nsに低下。40倍速いです。

覚えておくべきこと

教訓は「バイナリサーチは死んだ」ではありません。古典的なアルゴリズム複雑度（O log n）はキャッシュメモリを無視しています。現代のCPUでは、キャッシュミスを最小化する構造は、ほとんどの場合、比較を最小化する構造よりも優れています。

私たちのプロジェクトで出会う他の例：

• 「ロビンフッド」ハッシュマップ（Emmanuel Goossaert、Google Abseil flat_hash_map） vs. 古典的な std::HashMap。
• PDQソート（Pattern-Defeating Quicksort、Orson Peters - Rust slice::sort_unstableで使用） vs. 教科書のクイックスォート。
• 正確なルックアップ前にブルームフィルタを使用して、負のケースを迅速に排除。
• 列指向ストレージ（Parquet、ClickHouse）は、分析のためにキャッシュラインを活用。

次に読むべきもの

• Paul-Virak KhuongとPat Morinの論文（2015年）：Array Layouts for Comparison-Based Searching - この分野の学術的基盤。
• Ulrich Drepperの「What Every Programmer Should Know About Memory」（2007年） - 一部の詳細では古いですが、メンタルモデルは健全です。
• Rustのstatic-search-treeクレートまたは、生産的な例の対応物。

覚えておくべきこと

ホットループを最適化する際、最初に取り出すプロファイラはcachegrindではありません - Linuxのperf stat -e cache-misses,cache-references（またはmacOSのInstruments）です。2026年の真のパフォーマンスはここで決まります。複雑度理論は可能なことを教えてくれますが、キャッシュメモリは達成可能なことを教えてくれます。