https://code.google.com/p/cpp-btree/
I have been thinking about adding this to libts. It's licensed AL2 already. It currently requires C++11 but there is also a patch to remove that dependency that is AL2 licensed as well. I personally need this because it implements an ordered set where all our hash table implementations are obviously unordered. Since std::map is off the table, this seems like a good replacement. They even bench it against std::map for comparison. Thoughts?