私はデータベースを初めて使用し、検索する必要のあるフィールドにインデックスを追加すると、検索時間を大幅に短縮できることを読んでいます。私はこの現実を理解していますが、それが実際にどのように機能するかについて興味があります。私はこのテーマについて少し調べましたが、それがどのように機能するかについて、良い、簡潔な、そして技術的な答えを見つけられませんでした。
本の裏にある索引のようなアナロジーを読んだことがありますが、本の裏にあるアナロジーを使用して、一意の要素（ユーザーデータベースの電子メールアドレスなど）のデータフィールドの場合インデックス付けされていない検索と同じ線形ルックアップ時間を提供します。
検索時間を大幅に短縮するために、ここで何が起こっているのでしょうか。B +-Treesを使用した検索について少し読みましたが、説明が少し深すぎました。私が探しているのは、何が起こっているのかについての高レベルの概要であり、技術的な詳細ではなく、それを概念的に理解するのに役立つものです。
検索アルゴリズムの効率性を拡大すると、データベース パフォーマンスの重要な領域は、データへのアクセス速度です。一般に、ディスクからのデータの読み取りは、メモリからのデータの読み取りよりもはるかに遅くなります。
ポイントを説明するために、すべてがディスクに保存されていると仮定しましょう。フィールド内の特定の値を探すためにテーブル内のデータのすべての行を検索する必要がある場合でも、ディスクからデータの行全体を読み取って一致するかどうかを確認する必要があります。これは一般に「テーブル スキャン」と呼ばれます。 '。
テーブルが 100MB の場合、ディスクから読み取る必要があるのは 100MB です。
検索対象の列にインデックスを付けると、簡単に言えば、インデックスにはデータの一意の値と、対応する完全なデータ行の正確な場所への参照が格納されます。このインデックスは、テーブル全体の 100MB と比較して、10MB しかない場合があります。
ディスクから 10MB のデータを読み取る (そして、マッチごとに完全な行データを読み取るには少し余分にかかるかもしれません) と、100MB を読み取るよりも約 10 倍高速です。
さまざまなデータベースがさまざまな方法でインデックスまたはデータをメモリに格納し、これらをより高速にします。ただし、データ セットが大きくてメモリに収まらない場合は、ディスク速度が大きな影響を与える可能性があり、インデックス作成が大幅に向上する可能性があります。メモリでは、パフォーマンスが大幅に向上する可能性があります (他の効率の中でも特に)。
一般に、メモリに簡単に収まる小さなデータセットのインデックスを作成しても、明確な違いに気付かない場合があるのはそのためです。
根底にある詳細はシステムによって異なり、実際にはもっと複雑になりますが、ディスクの読み取りとメモリの読み取りは、これを説明する簡単に理解できる方法であることが常にわかっています。
さて、少しの調査と議論の後、私が学んだことは次のとおりです。
概念的には、インデックスは、インデックスを作成するデータ フィールドの並べ替えられたコピーであり、各インデックス値は元の (並べ替えられていない) 行を指します。データベースは値がどのようにソートされるかを認識しているため、最初から最後まで値を検索するだけでなく、より高度な検索アルゴリズムを適用できます。二分検索アルゴリズムは、ソートされたリストの検索アルゴリズムの単純な例であり、最大検索時間をO(n)からO(log n)に短縮します。
補足として: 適切な並べ替えアルゴリズムは、通常、完了するまでにO(n log n)かかります。これは、(おそらく以前に聞いたことがあるように) 頻繁に検索するフィールドにのみインデックスを配置する必要があることを意味します。完全な検索を数回実行するよりも、インデックス (並べ替えを含む) を追加する方がコストがかかります。たとえば、1,000,000 エントリを超える大規模なデータベースでは、1 回検索するよりもソートするほうが 20 倍のコストがかかります。
編集：特にディスク操作からの読み取りに関して、検索効率の詳細については、 @ Jarod Elliottの回答を参照してください。
本の類推を続けると、ページがその要素で順序付けられていた場合、インデックスなしの検索と同じルックアップ時間になります。
しかし、あなたの本が著者ごとに並べられた書評のリストで、ISBN しか知らないとしたらどうでしょう。ISBN は一意ですが、探しているレビューを見つけるには各レビューをスキャンする必要があります。
次に、書籍の最後に ISBN でソートされた索引を追加します。ブーム、速い検索時間。これはデータベース インデックスに似ており、インデックス キー (ISBN) から実際のデータ行 (この場合は本のページ番号) に移動します。