The B-Tree: It is like searching in a telephone directory with shuffled pages

Also check out LevelDB: http://code.google.com/p/leveldb. What TokuDB and LevelDB have in common is optimizing inserts, at least if key uniqueness is not required.