木構造まとめ

▼二分木

　最も単純な木構造。一つのノードから２つの枝が出る形。キーが辞書順で入力されていった場合に構造が偏ってしまい、最悪の場合だとただのリストと同様になってしまう。

▼平衡二分木

　二分木の欠点を補うために構造のバランスを取る機構を備えた二分木。バランスの取り方には様々なアルゴリズムが存在する。

　ex. AVL木、赤黒木 

▼B-Tree

　多分木。一つのノードが多数の枝を持っている。ルート、ブランチ、リーフという階層に分かれており、ブランチはデータの数に応じて階層数が変わる。各ノードには次の階層へのポインタとキーが示すデータへのポインタが存在。

▼B+Tree

　B-Treeの改良版。B-Treeとの違いはデータへのポインタがリーフにしか存在しないこと。これによって以下のメリットがある。

　・ブランチがデータを持たないことで一つのノードに多くのキーを入れられる

　　→階層数を少なく保てる

　・リーフだけを辿ることで関連データを取得していける

　B+Treeはハードディスクにデータを保存する際に適しているためデータベースの構造として広く使われている。各ノードの大きさをディスクアクセスの際に読み出すブロックの大きさと合わせて置くことで、IOの回数＝Treeの階層数とすることができる。連想配列やコレクションなどの実装では平衡二分木が用いられることが多い。ディスクへのアクセスは想定していないためシンプルに実装できる方が用いられているのだろう。

実践ハイパフォーマンスMySQL 第3版