木構造について調べる
相変わらずwikipediaをメインに調べていく。
親に子供がぶら下がっている構造のこと。
こんな感じで親に当たる根ノードとその子供である葉ノードに分別できる。
深さをカウントするときは根ノードよりも下をカウントする。
木構造なぜやるのか、木構造によって何が幸せかというと、データを取得するときに効率よく取得できるということ。
HDDのデータを取得するのも木構造(B+Tree)で、データ探索の効率がよいから。
*1
この動画みたいに何通りあるのかの処理の実行に260億年とかかけられると非常に困るわけで。
www.youtube.com
それを効率よくデータを取得しようという考えがあって、アルゴリズムのひとつとして木構造が存在するということ。
木構造の走査法
木構造を処理するとしたときに実行方法(走査法)はいくつか存在している。主に2つ。
深さ優先探索
簡単に言うと、- 根ノードから葉ノードまでの1ルート、分岐気にせず全部見る。※左側から順番に見る
- 末端までたどり着いたら、末端の直前の分岐まで戻ってまだ行っていないルートを末端まで行ってみる。
- それを繰り返す。
そんな感じ。
俺が一番しっくり来たのはノベルゲームのルートをいったん全部やってED見た後、行っていない選択肢選びつづけてルート制覇する感じ。
この探索方法も3つある。
- 前順・先行順・前置順・行きがけ順
- 間順・中間順・通りがけ順
- 後順・後行順・後置順・帰りがけ順
前順・先行順・前置順・行きがけ順
上で書いた内容の通り順番に実行する。間順・中間順・通りがけ順
木の左側の末端の葉ノードから走査する。ABCFのような節になっているところは、上から下とのきにカウントするのではなく、下から上になったときにカウントする。
※B→Fのときに1ではなく、I→Fのときに1カウントする
後順・後行順・後置順・帰りがけ順
前順・先行順・前置順・行きがけ順の逆版みたいなイメージ。この場合も木の左側の末端の葉ノードから走査する。
幅優先探索
深さが同じノードを浅い方から順に走査していく。木構造の種類
二分探索木とかAVL木は以下動画がわかりやすくておすすめ。www.nicovideo.jp
B-Treeは上の動画のAVL木を少し変えたもの。
何が変わっているのかっていうと、多分木であるのでその要素が違う。
多分木って何かっていうと、ひとつの親にぶら下がれる子供が複数件OKってだけ。
二分探索木やAVL木はそもそもそものルール上、ひとつの親にぶら下がれる子供が2つのみ。
じゃあなぜAVL木ではなくB-Treeをつかうのか。
B-treeとは、1つのノードがm個 (m>=2) の子ノードを持つことができる平衡木構造のことです。
なぜAVL木だと問題があるかというと、大規模なデータを補助記憶装置(ハードディスクなど)へ格納し検索する場合、コンピュータの処理に時間がかかってしまうためです。
ハードディスクは主記憶装置に比べ、アクセス時間が非常に長く、そのためハードディスクを効率的に扱うには、なるべくブロックの読み取り回数を少なくする必要があります。ブロックの読み取り回数は木の深さになります。
AVL木の場合、log n 回なのに対して、B-treeの場合、log n / log m 回 (※計算は省略) になります。そのためmが大きくなるほど、処理時間に差が出てきます。
このことから、MySQLではインデックスのデータ構造にB-treeが採用されているようです。