GoogleがB-tree実装のSTLコンテナを公開

C++ containers that save memory and time

cpp-btree - C++ B-tree - Google Project Hosting

Googleが、B-tree実装のSTLコンテナー(map, set, multimap, multiset)を発表した。

多くのSTLの実装では、map, set, multimap, multisetは、Red-Black treeで実装されている。Googleの発表によれば、B-tree実装のコンテナーは、赤黒木実装に比べて、速度が上がり、しかもメモリ消費量も削減できるとしている。

紹介まで。

B木は一つのノードに複数の要素を格納する。これにより、ポインターなどのオーバーヘッドを低減でき、メモリ消費量の削減につながる。また、複数の要素を一括してノードに詰め込むため、速度向上もあるのかもしれないが、そのへんはよくわからない。小さな要素を多数扱う際には好都合かもしれない。

STLのコンテナーをB木で実装する欠点としては、メンバー関数emplace系が実装できなくなることだ。というのも、B木ではひとつのノードに複数の要素が格納され、さらにノード単位でバランスを取っているので、単純に任意の順序を取る要素ひとつの都合だけで、ノードのつなぎ変えができない。つまり、置き換えはいかにも無理だ。