静的探索木で二分探索を40倍高速化

Static search trees: 40x faster than binary search (2024)

ソート済みデータに対する検索を高速化する静的探索木（S+ツリー）の実装について解説。EytzingerレイアウトやSIMD、バッチ処理などの最適化を組み合わせ、バイナリサーチと比較して最大40倍のスループットを達成。ベンチマーク結果やアセンブリコードの分析も交え、データ構造の設計とCPUの性能を徹底的に追求する。