DBのインデックスについて

データを高速に検索するにはどうすればよいか

DBからデータを取得する場合、通常順次検索して条件に合ったものを取ってくる。 順次検索するより、索引を作成して、索引を基準とした検索方法の方が検索スピードが速くなる。 つまりDBにもインデックスを張るカラムを指定する事と、索引の格納している位置を明示する事で、 順次検索するよりも、素早く対象の値を取得する事ができる。

インデックスを張る事で検索スピードが上がるDBの特徴

• データが大量に格納されている。 少量のデータだと順次検索したほうが早い場合がある。

• 値が重複していない。 インデックスを張るカラムに格納されているデータが重複していると、索引を付ける箇所が少なく、効果が薄い

データ構造

データの特性や検索の仕方によって、インデックスのデータ構造は変わってくる。

• B木 ツリー構造をしていて、根から検索を開始して、子ノードを条件によって分岐してデータを求める構造 BETWEEN等を用いた範囲指定検索において有効です

• B+木 B木と同じツリー構造をしているが、データの持ち方が異なり、データはリーフノードに持つ。 B+木の場合、最後のリーフノードまで検索しないと、データを取得できないので、B+木の2分木の特徴を持ちながら、順次検査をしていく形を取ります。 ANDやOR操作だけで行う検索やNOTを用いた否定検索において有効

B木とB+木の違い B TreeとB+ Treeの違い - Carpe Diem

• ビットマップインデックス ビットマップを使った検索方法で、値とレコード番号（値を特定する値）を図表にして求める値を特定していく。 格納されている値のパターンが少ない場合に有効 OR検索にも有効

↓わかりやすい記事 ビットマップインデックスの仕組み - Qiita

• ハッシュインデックス Hash関数を用意して検索時にその関数を通して検索する。 例えば、値を100で割ったときの余り返す関数をHash関数とした場合、ID=234のHash値は34になり、この34に対応する位置にHash値とTIDを格納します。

第2回「Hashインデックス」 | NTTデータ先端技術株式会社

参考サイト データベース性能を向上させる「インデックス」を理解する：「データベーススペシャリスト試験」戦略的学習のススメ（26） - ＠IT