RustでB+Treeかいたよ

Rust アルゴリズム

2021年2月24日4月18日追記：
新しいほうがあります。
(見返すと大分筋が悪く思えてはずかしかったので再実装しました)
totechite.hatenablog.com









素の二分木とかAVL木かいたりと細々と継続していた、アルゴリズムとデータ構造の学習の延長です。こいつ木しか書いてねえな

totechite.hatenablog.com

totechite.hatenablog.com 今見返すとその記事の頃からBtreeやるやるとかいており、氏ぬまでに実装できてよかったと思う

はじめに

B+木については自分が解説するよりこちらの記事を読んでもらうほうがわかりやすいと思います
christina04.hatenablog.com

B木の変形にB*木やB+木と呼ばれるものがありますが、B+木の実装はあまり公開されていない様にみえた為今回B+木をを書いてみました。

実装した操作はinsert（挿入）, find（探索）, update（更新）, delete（削除）, print（出力）
deleteははりきって物理削除を採用した　えらいね

グチャグチャに書いてしまったので気が向いたらコメントでも書いて整理したい

gistf4ea94b6095b31d4f62e71baa48135a1

結び

以前よりRDBMSの実装には興味があり、インデックスのデータ構造の一つであるB木にはかねてより関心があったので今回実装出来て楽しかった。今後自作RDBMSとか作るときに使うと思う。
とりあえず一通り動くところまではできたが、きっと余分な処理をしていたりコードが冗長になってしまっている為その解消と、諸々の最適化には手を付けられていないことを次の課題にしたい。

参考リンク