谷歌發布基于 B-Tree 的 C++ 模板庫

　　谷歌開源團隊近日發布了C++ B-Tree，這是一個 C++ 模板庫，實現了基于B-tree 數據結構的有序內存容器。類似于 STL 的 map、set、multimap 和 multiset 模板，C++ B-tree 也提供了 btree_map、btree_set、btree_multimap 和 btree_multiset 等模板。 

　　B-tree（多路搜索樹，并不是二叉的）是一種常見的數據結構。使用B-tree 結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。這個數據結構一般用于數據庫的索引，綜合效率較高。 

　　由于B-trees 可以保持磁盤尋道到最低限度，通常作為二次存儲數據結構。對于內存中數據結構來說，將緩存未命中率保持在最低限度，可以產生更高的性能。C++ B-tree 在搜索樹時，通過在每個節點執行多個鍵比較，更好地利用了緩存。緩存行為的改善，可以使訪問大型容器時的性能有顯著提升。 

　　谷歌開源團隊同時也表示，C++ B-tree 容器也不是沒有缺點，與標準 STL 容器不同的是，修改C++ B-tree 容器，會令所有未在該容器中的迭代器失效。出于這個原因，谷歌在該庫中還增加了一個“安全”容器版本，安全容器中的迭代器會保存當前 key 的副本，并會在使用迭代器時自動復位。 

　　詳細信息：C++ containers that save memory and time 

　　項目地址：https://code.google.com/p/cpp-btree/