インデックス

どうも、69です。

今日こそは、本分のAndroidやろうかと思いましたが
眠いので…

今日は許してください。
自分には甘いので。。。


さらっと行きます。
インデックスです。

インデックスとは大量のデータから目的のデータを素早く見つけるための仕組みです。
書籍の目次や索引みたいなものです。

このたとえはわかりやすかった！！


インデックスを使わない検索では
目的のタプルが見つかるまでテーブルのレコード全体を順次読み込んでいきます。
上のほうにあれば、すぐ見つかるけど…ねぇ。

インデックスをつかうと
インデックステーブル（あらかじめ作成しておく）を探して、目的のデータの位置情報を取得します。
ただ、件数が増えちゃうと、インデックステーブルから探し出すだけで時間食っちゃう。。。

なので、効率を上げるために「Bツリー」というデータ構造でインデックスを作成します。

Bツリーはバランスツリーといいまして、
ツリー構造で、各ノードに一定の個数のキーとポインタ（位置情報）のペアを格納します。

一番上のノードをルートノード。
一番下のノードをリーフノード。
その間のノードをブランチノード。
と言います。層が増えるとブランチノードが増えてきます。

これを見て、思ったのが、二分探索ってやつ。
真ん中の値より小さいから小さい側だけを探せばいいや。みたいな。
それを繰り返して、キーを見つけ出す。のかな？

でも、これだと順番にアクセスしようとしたら
ノードを行ったり来たりしないといけなくなってまう。。。

そこで「B+ツリー」です！

B+ツリーではキーとポインタは全てリーフノードに格納されます。
その格納されたリーフノードをシーケンスセットと言います。
リーフノードはポインタでつながれているので、
Bツリーの弱点を解決できます！

よくわかりませんが、B+ツリーってのがいいらしい！

おしまい。