In a binary heap, there's a single root, but after that, there are pairs of nodes. In your case, the item has the same size of a cache line, so things are not t

In a binary heap, there's a single root, but after that, there are pairs of nodes. In your case, the item has the same size of a cache line, so things are not too bad. During traversal, you'll always read two whole lines for each pair of nodes. You could still worry about the CPU cache's n-way associativity, but either that requires a lot of control over memory allocation layout or it will provide diminishing returns. Anyway, the interesting case is when items are smaller than a line. Look at an array-based implementation of a heap: https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementation https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementat... Root is item 0. Assume it's aligned to a multiple of 64 bytes and you have two 32-byte items per line. When comparing array items 1&2, 3&4, 6&7, etc., notice how the two items are always in different cache lines. Item 1 is in the same line as item 0, not item 2. You're always crossing the line boundary. If the root were at item 1 in the same array (or, equivalently, item 0 in case the array started at a multiple of 64, plus an offset of 32), then each pair would be always in the same cache line. In case it wasn't clear, I was pointing out a similar phenomenon with other data structures; it wasn't about linked lists.