Search data structure とは

コンピュータサイエンスでは、検索データ構造は、データベースの特定のレコードなど、項目のセットから特定の項目を効率的に取得できる任意のデータ構造です。
最も単純で、最も一般的で、最も効率の低い検索構造は、すべての項目の順不同の単なるリストです。そのようなリスト内の所望のアイテムを線形サーチ法によって見つけることは、必然的に、アイテムの数nに比例した多数の演算を必要とする(最悪の場合と同様に)。有用な検索データ構造により、より迅速な検索が可能になります。ただし、特定の種類のクエリに限定されています。さらに、このような構造を構築するコストは少なくともnに比例するため、同じデータベース(またはクエリ間でほとんど変化がないデータベース)で複数のクエリを実行する必要がある場合にのみ効果があります。
静的検索構造は、固定データベース上の多くのクエリに応答するために設計されています。動的構造はまた、連続したクエリの間でアイテムの挿入、削除、または変更を可能にする。動的なケースでは、データベースの変更を考慮して検索構造を修正するコストも考慮する必要があります。