データベース索引の検索速度の向上

Question

私はレールチュートリアル（http://ruby.railstutorial.org/book/ruby-on-rails-tutorial#sidebar-database_indices）で読んでいましたが、データベース索引の説明について混乱させましたが、データベースのインデックスを理解するために

、それは便利です：基本的に著者は、次の例を挙げて、インデックスを作成するために、そのはるかに高速O（n）の（ログイン用）の電子メールのリストを探索時間ではなく、その後のことを提案しています本の索引の類推を考えてみましょう 。ある書籍で、与えられた 文字列のすべての出現を見つけるには、 "foobar"と言うと、 "foobar"の各ページをスキャンする必要があります。 ブックインデックスの場合は、 の "foobar"を検索して、 "foobar"を含むすべてのページを見ることができます。 ソース： http://ruby.railstutorial.org/chapters/modeling-users#sidebar:database_indices **

それでは、私はその例から理解することは言葉をテキストに繰り返すことができるということなので、「インデックス・ページには、」一意のエントリで構成されています。しかし、railstutorialサイトでは、各メールアドレスがアカウント固有のものになるようにログイン設定されています。

おかげ

Answer 1

インデックスの重複はほとんどありません。それは注文に関するものです。

検索を実行すると、すべてのレコードを検索して検索する代わりに（たとえば）バイナリ検索を実行して対数的な時間でデータを検索することができます（これは唯一の索引タイプではありませんが、おそらく最も一般的です）。

残念ながら、レコード自体は1つの順序でのみ並べ替えることができます。

インデックスには、検索に使用するデータ（またはそのサブセット）と、実際のデータを含むレコードへのポインタ（または何らかの並べ替え）が含まれます。これは、あなたが気にしている多くの異なるフィールドに基づいて（例えば）検索を行うことができ、各インデックスがそのフィールドで順番に並んでいるので、それらのすべてに対してバイナリ検索を実行することができます。

Answer 2

DBにおける所与の例ではインデックスは、アルファベット順をソートされるからです。生のテーブル/本はありません。次に考える：どのようにあなたはそれを分類して知っているインデックスを検索しますか？私はあなたの興味のポイントまで "A"で読んで始めないと思います。代わりに、おおよそPOIにスキップし、そこで検索を開始します。基本的に、DBは同じインデックスにすることができます。

Answer 3

索引には問題の列の値のみが含まれているため、表全体より小さなページ数に分散されているため、処理が高速になります。また、索引には通常、必要な読取り数を制限するハッシュ表などの追加の最適化が含まれています。