See http://mysite.verizon.net/beman/btree/preliminary_timings.html Notice that under some test conditions, some operations are faster on a btree_map than a std::map. But do be aware that these timings are preliminary. Bugs in either the test code or the implementation code could be skewing results. The test program can be viewed at http://github.com/Beman/Boost-Btree/blob/master/libs/btree/tools/bt_time.cpp Comments appreciated! --Beman