Algorithms
Eytzinger Layout
A cache-optimized array layout for binary search that arranges elements in breadth-first order for better memory access patterns.
How Eytzinger Layout Works
The Eytzinger layout arranges a sorted array as an implicit binary search tree in BFS order. This improves cache performance because elements accessed together are stored near each other.
Root at index 1Left child = 2kRight child = 2k + 1Parent = k/2
Eytzinger Tree Structure
Eytzinger Memory Layout
4 elements per cache lineDISK
-
8
4
12
L0
DISK
2
6
10
14
L1
DISK
1
3
5
7
L2
DISK
9
11
13
15
L3
Cache Hit Cache Miss
Standard Memory Layout
4 elements per cache lineDISK
1
2
3
4
L0
DISK
5
6
7
8
L1
DISK
9
10
11
12
L2
DISK
13
14
15
L3
Cache Hit Cache Miss
Why is Eytzinger Faster?
- Cache locality: Elements near the root are accessed first and stored at the beginning of the array
- Predictable access: Child indices (2k, 2k+1) are simple calculations, enabling prefetching
- Fewer cache misses: Siblings are adjacent in memory, often in the same cache line
- Branch-free variants: Can be implemented without branches for even better performance