Or AVL trees, for example. These make inserting and searching very fast if you access the same datum shortly after a previous acess. If the accesses are truly random, you might check out a self-balancing tree.

--traveler