またRustでB+Treeかいたよ

Rust アルゴリズム

Rust標準ライブラリのBTreeMapの実装コードを参考にB+Treeをフルスクラッチで実装しました。
get, insert, remove, rangeなどの基本的な操作は実装できているので、ひとまずここに記録します。
ソースコードはGitHubリポジトリに公開しています。そちらもみて見てください

github.com

どなたかのB+Treeの実装や理解の参考になれば幸いです。
(1600行程度で収まったのでstd::collections::btree_mapより追いやすくなっていればいいなと)

実装した主な操作

Rustっぽい疑似コードです。細かい仕様はソースコードみてください。

  • fn get(key) -> Option<value>
    入力に全順序なkeyを取る。もし要素が存在すれば、そのvalueを出力する。

  • fn insert(key, value) -> Option<old_value>
    入力にkeyとvalueを取る。もしkeyが既に存在すれば、値を更新し、古いvalueを出力する。

  • fn remove(key) -> Option<value>
    入力にkeyを取る。もしkeyの要素が存在すれば、その要素を削除しvalueを出力する。

  • fn iter() -> Iter<key, value>
    全要素のイテレータを出力する。

  • fn range(range) -> Range
    入力にstd::ops::Rangeを取る（"0..10"などはstd::ops::Rangeの糖衣構文）。指定範囲の要素のイテレータを出力する。

  • fn keys() -> Keys
    全要素のkeyのイテレータを出力する。

  • fn values() -> Values
    全要素のvalueのイテレータを出力する。

ほかにもあるが割愛

感想

前回の実装ではRc<Refcell<T>>の多用による性能悪化、key, value型のトレイト境界が厳しいことやバグの存在などの課題がありました。
今回はRust標準ライブラリのBTree実装を参考にすることで上記の課題を解決するに至りました。
BTree系のデータ構造はFileSystem,やDBMSのインデックス技術への採用で有名ですが、今回B+Treeの実装を足掛かりに私も簡単なKVSをつくってみたいですね。