News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search (2024) by hansvm on Saturday July 18, 2026 @10:04AM (#48958271)
Both. The hypothesis with Eytzinger is that you're doing vanilla binary search on a data structure where each hop is one operation. It doesn't, by itself, do anything to optimize around particular hot leaves, so assuming you aren't doing a weighted rebalance operation before construction it additionally assumes access patterns are somewhat uniform. That's the algorithm and input pattern whose cachability we're trying to optimize.

Imagine, e.g., doing a b-tree lookup on a binary Eytzinger layout. You would always grab more cache lines than optimal. Even more obviously, consider an inorder traversal. The properties of an algorithm and data structure depend properly on both components.

There are no comments on this comment yet.