There's a tradeoff between latency and amount of memory touched.
The beautiful thing about the heap layout is that you can prefetch more than one level ahead. If your keys are 4 bytes, 16 of them fit on a cacheline, and you can prefetch 4 levels ahead with a single cacheline.
That means that if nothing is in cache, worst case each loop iteration will take < 20 ns.
With any kind of clustering (really, it's just a variation on B-trees) you touch less memory but you can't prefetch as far ahead.
In practice I suspect a 4-ary heap would perform better than a binary heap for my application, but there's a bunch of math I'd have to work out again that was hard enough for the binary tree version.
Not quite sure how what you're describing would work, but I can't see offhand how you'd implement it without losing the prefetching the heap layout gives you.
Comments
There's a tradeoff between latency and amount of memory touched.
The beautiful thing about the heap layout is that you can prefetch more than one level ahead. If your keys are 4 bytes, 16 of them fit on a cacheline, and you can prefetch 4 levels ahead with a single cacheline.
That means that if nothing is in cache, worst case each loop iteration will take < 20 ns.
With any kind of clustering (really, it's just a variation on B-trees) you touch less memory but you can't prefetch as far ahead.
In practice I suspect a 4-ary heap would perform better than a binary heap for my application, but there's a bunch of math I'd have to work out again that was hard enough for the binary tree version.
Not quite sure how what you're describing would work, but I can't see offhand how you'd implement it without losing the prefetching the heap layout gives you.