B+ Treeを書く 個人的にgenericsが欲しい場面としてarray,map以外のデータ構造を使う時を考えていたので、B+ Treeを書いてみることにしました。 B+ Treeをチョイスした理由としてはDBのインデックスでいつも使っているのに一度も書いたことないのどうなんだと前々から思っていたためです。 B+ Treeとは 詳細な説明は省きますが、B+ TreeはB Treeの亜種です。 BTreeは二分探索木の各ノードが2本以上の枝を持つもので、B+ TreeはBTreeの内部ノードにはキーのみを保存し、実データは全て葉ノードに保存します。 この葉ノードを連結リストでつなぐことにより、範囲検索が効率的に行えるという特徴が有ります。 B+木のノードが配列として構成される場合、挿入や削除で配列の要素をずらす必要が生じ、性能が悪くなる。そのため、ノード内の要素は2分木やB+木で構成するの
