Data Structures: Knuth Got It Wrong

June 16th, 2010
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)


Uncategorized

  1. Trackbacks

  1. Comments

  2. 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. 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
    read.

  4. 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.


four + 4 =