B-Heap vs. Binary Heap (2010)

Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of for (register int i = 0; i < 299; i++) ; can pay for itself by saving a cache miss. The log N cache…

A great reminder that spatial locality can be critical to performance. But that's actually quite well-known, and maybe a more important lesson would be: don't take performance for granted, even in standard libraries of well stablished languages or algorithms, there might be much room for improvement for your use case (if you need it). This said, the article feels quite arrogant. As other commenters say, the idea behind the optimization is nothing new, just some basic concepts well applied. Which…

This is a great article and the diagrams illustrating the difference between a binary heap and a B-heap are awesome. The comments are amusingly negative, too. It's worth noting that it was published in 2010, though. The Wikipedia article on B-heaps actually references this article: http://en.wikipedia.org/wiki/B-heap

Summary: A common way to store a binary heap is so that the children of n are located at {2n, 2n+1}. This has the effect that parent and child are usually located in different memory pages if the tree is big. Traversing the tree is faster if it's stored so that each page contains a small subtree that is a few levels deep. So we go from [1] to [2] where the white boxes are memory pages and the numbers…