インデックス

そもそもの前提

ディスクに保存されてるデータは、Selectの結果で見るように綺麗に並べられてるわけではない。

ランダムアクセスという感じで、データはディスク内にバラバラに置かれている。

もし綺麗に整頓されて保存されてる場合、値を間に入れたい場合などに、大層なデータ移動作業を強いられる。

でも綺麗に並べられてないと、データを探すとき大変じゃない？？ディスク or ファイル内の全てを走査するのか？？

最悪ファイル内全体を走査することにはなる。ただ、そんなことをしてしまうと性能がすんごい遅い。

インデックスとは

データを探しやすくするための情報を別に持っておく仕組み。本の索引と同じ。

実際のデータとは別にデータを探しやすくするための情報を作ってセットにしておこう

インデックスの前に「木（Tree）」構造について

インデックスという仕組みを実現するに当たって、持ってこないなデータ構造が「木（Tree）」だと覚えとく。

二分探索木

「子が 2 つまで かつ 左の子 ≤ 親 ≤ 右の子 の順にノードを並べる」というルールを持つ木。

https://scrapbox.io/files/63bd5eba37998a001d5a8160.png

AVL木

二分探索木に「どのノードにおいても左の子の高さと右の子の高さの差が 1 以下 」というルールを追加した木。

なぜ？

二分探索木だけだと、ノードを付けたり消したりするうちに高さがずれて来てしまう。

高さがズレることによって、データの検索効率が落ちてしまう。

なので、常に高さを等しくしておきたい。

B（Balanced） Tree

二分探索木とは違って 子が 3 以上あってもいい木。

データベースのインデックスに使われる構造は、このB-Treeになる。

理由：

他の構造よりもディスクアクセスが低く保たれるため。

基本的にインデックスの木構造における高さが高くなるほど、ディスクアクセスの回数が増えてしまう。

B-Treeだと1億行のデータがあったとしても、高さは3 ~ 6に抑えられるらしい。

インデックスの特徴を知る

以下に任せる

その他のインデックス

参考