Google、STLのmap/setと互換性のあるコンテナをBツリーで実装した「C++ B-Tree」を公開

　Googleは2月1日、mapやsetといったコンテナをBツリーで実装したC++テンプレートライブラリ「C++ B-Tree」のリリースを発表した。STLのmapやset、multimap、multisetとほぼ互換性のあるBツリー実装で、STLのmapやsetなどよりも消費メモリが少なく、またキー検索などの処理速度が向上しているという。

　C++ B-TreeはB木（Bツリー）構造を使って実装されたC++向けコンテナライブラリ。STL（Standard Template Library）のmapおよびset、multimap、multisetと同様の機能を持つ「btree_map」および「btree_set」、「btree_multimap」、「btree_multiset」といったコンテナを提供する。

　STLのコンテナは赤黒木（Red Black Tree）を用いて実装されることが多い。この場合、各エントリごとに3つのポインタが必要となるが、B木を用いた実装の場合、エントリごとに必要なポインタ数は平均すると1つ以下になるため、メモリ使用量を大きく削減できるという。また、データが近接したメモリ領域に配置されるためキャッシュミスを最小限に抑えられ、キーの検索パフォーマンスの向上も期待できる。

　C++ B-TreeはSTLのmapやsetなどとほぼ互換性があるため、STLとそのまま置き換えて利用できる。ただし、コンテナに対して挿入や削除といった操作を行うと、使用中のイテレータが無効になってしまうという点が異なるという。btree_mapおよびbtree_setについてはこの問題に対応した「safe_btree_map」および「safe_btree_set」というコンテナが用意されており、こちらを利用することでその問題は解決できるとのこと。また、イテレータのインクリメント/デクリメント操作についてはSTLの標準的な実装と比べて若干遅いという。

　C++ B-TreeはC++ B-Treeのプロジェクトページからダウンロードできる。ライセンスはApache License 2.0。

C++ B-Tree
http://code.google.com/p/cpp-btree/