top of page
  • Writer's picturekyle Hailey

Data Structures: Knuth Got It Wrong

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)

0 views0 comments


bottom of page