Static B-Trees
lastmod 2026-11-10created 2025-01-032 edits
Static B-Trees are a data structure that speeds up search by rearranging a sorted integer array with no insertions or deletions into B-tree-like nodes. Each node is sized to fit a cache line and compared all at once with SIMD instructions, and children are found by index arithmetic alone without pointers, so there are far fewer cache misses than with binary search over the same data. They are used to optimize operations such as lower_bound on search-only tables, and there is also a B+ tree variant.