索引 (データベース)
インデックスは多くの応用例に役立つが、いくつかの制限事項がある。次のSQLステートメントについて考えてみよう。
SELECT first_name FROM people WHERE last_name = 'Smith';
インデックスなしでこのステートメントを処理するには、データベースソフトウェアは、テーブルのすべての行のlast_name列を確認する必要がある(全表スキャンと呼ばれる)。インデックスを使う場合、データベースは、項目にSmithが見つかるまで、インデックスデータ構造(通常はB木)に従って検索する。この方法は、全表スキャンよりもはるかに計算コストが低くなる。
次のSQLステートメントについて考えてみよう。
SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';
このクエリにより、電子メールアドレスが「@wikipedia.org」で終わるすべての顧客の電子メールアドレスが返されるが、email_address列にインデックスが付けられている場合でも、データベースは完全なインデックススキャンを実行する必要がある。
大規模なデータベースでは線型検索 (liner search)が非効率的であるため、ほとんどのデータベースソフトウェアでは、劣線形時間検索 (sub-linear time lookup)を使ってパフォーマンス向上ができるようにインデックスが作成される。
データベースにN個のデータ項目があって、フィールドのどれか1つの値からデータ項目の1つを取得することを考える。単純な実装では、各項目を取得して調べていく。一致する項目が1つだけとわかっている場合は、その項目が最初に見つかった時点で停止できるが、複数項目ある可能性がある場合は、全項目を検査する必要がある。これは、平均的な場合の操作数がO(N)または線形時間であることを意味する。データベースには多くのオブジェクトが含まれ、検索は一般的な操作であるため、検索アルゴリズムの効率向上はとても重要である。
インデックスは、検索効率を向上させるためのデータ構造である。この目的で使用されるさまざまなデータ構造がある。各データ構造には、検索効率、インデックスサイズ、インデックス更新効率のどれを優先させるかにより複雑な設計上のトレードオフがある。多くのインデックスデザインでは計算時間が対数 (O(log(N)))の検索効率を示し、一部のアプリケーションでは計算時間がフラット (O(1))の検索効率の達成が可能である。