Cook Computing

Btrees and Algorithms

June 8, 2002 Written by Charles Cook

Brad Wilson describes a fundamental difference between hash tables and C++ maps: the latter are implemented as a balanced tree and so maintain ordering of the items by key. This caught my attention because I've recently been reading David McCusker's notes on a design for btree-based blobs (the challenge of understanding these notes makes for pleasant occasional reading). I have to admit that before this I didn't know anything about btrees. Not having studied Computer Science I've not had much exposure to algorithms; I don't even own a copy of Knuth's seminal Art of Computer Programming. Similarly, as I mentioned in an earlier post, I've not learnt how to program in Lisp until now. However, I don't think this matters all that much when it comes to producing working software: after working with a large number of developers I've not noticed any correlation between ownership of a Computer Science degree and competence.