みなさん、こんにちは。現在、検索アルゴリズムの最適化に関する研究を行っています。
今のところ、私はデータベースについて研究しています。
SQLサポート付きのデータベース内。
特定のテーブルのクエリを書くことができます。
1は、名前がTestであるTable1の番号を検索し、2はすべての列で名前Testを検索します。
関数の概念は理解していますが、検索のアプローチを知りたいのは何ですか？
条件が真である限り、最初のインデックスからn番目のインデックスまでが取得され、O（n）の速度が得られる単純な線形探索ですか、それともプロセスを高速化する独自のアルゴリズムがありますか？
インデックスがない場合は、はい、線形検索が実行されます。
ただし、データベースは通常、列をキーとして指定するときにB ツリーインデックスを使用します。これらは、磁気ディスク ハードウェアで適切に動作するように特別に調整された (高い B ツリー分岐係数) 特別なデータ構造形式です。最も時間のかかる要因はシーク操作です (磁気ヘッドはファイルの差分部分に移動する必要があります)。 ）。
インデックスは、列内の値の並べ替えられた/構造化されたコピーと考えることができます。検索対象の値がインデックスに含まれているかどうかは、すぐに判断できます。見つかった場合は、メイン データ ファイル内の対応する行の正しい位置を指すポインターも見つけます (そのため、行内の他の列を読み取ることができます)。場合によっては、クエリによって要求されたすべてのデータが複数列のインデックスに含まれている場合、メイン ファイルにスキップして戻る必要はなく、見つかったものを読み取るだけで済みます。
他の種類のインデックスもありますが、データを複製し、検索が高速になるように配置するというアイデアは理解できると思います。
大規模なデータベースでは、インデックスによって、複雑なクエリが完了するまで数秒待つか、場合によっては数日待つかの違いが生じます。
ところで、B ツリーは単純で理解しやすいデータ構造ではなく、トラバーサル アルゴリズムも複雑です。さらに、データベースではデータのチャンクをディスクから常にロード/アンロードし、メモリ内で管理しているため、トラバーサルはほとんどのコードよりもさらに醜いものであり、これによりコードが大幅に醜くなります。ただし、二分探索木に精通している場合は、その概念を十分に理解していると思います。
まあ、それはデータの保存方法と何をしようとしているかによって異なります。
kツリーの最上位レベルは RAM に格納でき、最下位レベルはわずかしかディスクに格納されず、それぞれに対してディスク読み取りが必要になるため、通常はごく少数のディスク アクセスしか許可されません。O(1)ディスク アクセス (通常はデータベースを扱う場合のボトルネック) だけなので、比較的高速です。
上記のすべての欠点は、キーが 1 つしか必要ないことです。つまり、リレーションのフィールド「id」に従ってハッシュ テーブルまたは B+ ツリーが構築され、次に「キー」に従って検索すると、役に立たなくなります。
リレーションのすべてのフィールドの高速検索を保証したい場合は、それぞれが異なるキーに従っていくつかの構造体が必要になり、メモリ効率があまり良くありません。
現在、特定の用途に応じて考慮すべき多くの最適化があります。たとえば、検索の数が非常に少ないと予想される場合 (合計 ops の loglogN が小さいなど)、B+ ツリーを維持することは全体的に効率が悪く、要素をリストとして保存し、検索のまれな機会にのみ実行します。線形検索。
非常に良い質問ですが、テーブルの構造と正規化の方法によっては、多くの回答が得られる可能性があります...
通常、クエリでseacrhを実行するためにSELECT、DBMSはテーブルをソートします（このアルゴリズムはクイックソートではなくディスクのI / Oに適しているため、マージソートを使用します）。インデックスに応じて（テーブルにある場合）、数字と一致するだけですが、構造はより複雑です。DBMS はツリー内で検索を実行できますが、これは深すぎます。私が取ったメモでもう一度調べさせてください。
クエリ実行プランをアクティブにすることをお勧めします。Sql Server 2008 で実行する方法の例を次に示します。次に、WHERE 句を使用して SELECT ステートメントを実行すると、DBMS 内で何が起こっているかを理解し始めることができます。