Full article at http://queue.acm.org/detail.cfm?id=1814327
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)
No comments:
Post a Comment