Data Structures: Knuth Got It Wrong

June 16th, 2010
(Via Slashdot
Full article at
Data structures and how data is grouped, stored and manipulated seems to be a lost art in computer programming yet it’s the cornerstone to programming.
Poul-Henning Kamp’s article is a refreshingly clear perspective on performance and datastructures, check it out.
Reminds me somewhat of the Oracle notion of how deep is your index
As you can see the traditional binary heap, on left, is deeper than the new structure, the “b-heap”, on the right. The “b-heap” is slightly computationally more expensive but if less pages are visited avoiding visiting any paged out pages, the “b-heap” will perform much better.
The article goes into detail quite normal situations where the new structure performs an order of magnitude better than the traditional binary heap.

(thanks to Mark Bobak for sharing this link with me)


  1. Trackbacks

  2. July 29th, 2019: Instagram Followers: Their Benefits and Why the Cheat is Necessary |

  2. Ignacia Mondragon
    November 25th, 2019 at 12:47 | #1

    Frankly, I guess such articles should be printed more and more due to the current situation and modern demands of the Millenials.
    I read them to get some fresh information that
    will correspond to your own needs.

  3. Obryan
    November 25th, 2019 at 20:32 | #2

    Thank you for bringing up this topic. I was searching for
    up to date advice on this subject for a few days. Now I’m satisfied like I have finally attained your article.

    I enjoy the way you present and argue all the facts in addition to your overall writing
    style. From time to time, there’s a scarcity of time to read lengthy bits, but yours is brief and concise, I spent just
    a couple of minutes to read the entire article. It is essential, since no one has time to

  4. Kopp
    November 28th, 2019 at 09:25 | #3

    I spend a few minutes on studying, and I am so excited about
    the information that I obtained. It is truly tough to
    find something precious on this particular topic.
    However, this writer appears to be a true professional because there is a unique personality in his writings.
    I’m likely to subscribe to his new publications, simply not
    to skip anything. This post works its own reading.

  5. Mcdowell Mandy
    January 10th, 2021 at 20:08 | #4

    I’ll certainly subscribe for additional author’s books.
    This one has just blown up my mind! From the the
    previous post that made the exact same expression was of these guys https://WRITE-MY-PAPER.COM SAME
    DAY ESSAY SERVICE . I am so glad, you have made my life!
    Proceed at the exact same pace and style, thanks.

You must be logged in to post a comment.