おはようございます、私は現在、検索アルゴリズムの最適化に関する研究を行っています。データベース内のクエリ検索のアルゴリズムとは何ですか？
今のところ、私はデータベースについて研究しています。
SQLサポート付きデータベースの場合。
私は特定のテーブルのクエリを書くことができます。
1は、名前がTestである場所からTable1の番号を検索し、2は名前Testのすべての列を検索します。
私は関数の概念を理解していますが、私は何が検索のアプローチであるかを学ぶことに興味がありますか？
最初のインデックスからn番目のインデックスまでの条件は真であるため、O（n）の速度を持つか、プロセスを高速化するユニークなアルゴリズムを持っている限り、それを取得します。通常、DBMSは（それがマージを使用してテーブルをソートSELECTクエリでseacrhを実行するために
非常に良い質問が、それはあなたのテーブルの構造に応じて、多くの答えを持っているとどのように正規化されていることができます...
このアルゴリズムはディスク上のI/Oには適していますが、クイックソートではありません）、インデックスに応じて（テーブルがあれば）番号に一致しますが、構造が複雑な場合はDBMSがツリー内で検索を実行できますあまりにも深いので、私が取ったノートで再び研究しましょう。
Sql Server 2008でクエリ実行プランhere is an exampleを有効にする方法をお勧めします。その後、WHERE句を使用してSELECTステートメントを実行すると、DBMS内部で何が起きているのかを理解することができます。
インデックスがない場合は、はい、線形検索が実行されます。
しかし、データベースは、キーを列として指定するときに通常B Treeのインデックスを使用します。これらは、最も重要な時間を要する要因がシーク動作である磁気ディスクハードウェアでうまく機能するように特別に調整された（高いBツリー分岐ファクタ）特別なデータ構造フォーマットです（磁気ヘッドはファイルのdiff部分に移動する必要があります）。
インデックスは、列内の値のソート済みまたは構造化コピーと考えることができます。検索される値が索引内にあるかどうかを迅速に判断できます。見つかった場合は、メインデータファイルの対応する行の正しい位置を指すポインタも検索されます（行内の他の列に移動して読み取ることができます）。クエリによって要求されたすべてのデータが複数列のインデックスに含まれている場合、メインファイルにスキップする必要はなく、見つかったものと完了したものを読み取ることができます。
インデックスには他のタイプもありますが、データを複製して検索するのが早い方法でアレンジできると思います。
大規模なデータベースでは、インデックスは複雑なクエリが完了するまで数分を待つことと、多分数日待つことの違いになります。
btw- Bツリーは、単純で理解しやすいデータ構造ではなく、トラバーサルアルゴリズムも複雑です。さらに、データベース内では、ディスクからデータを読み込んだり、メモリ上で管理したりするため、コード内のほとんどのコードよりもトラバーサルが醜いです。しかし、もしあなたがbinary search treesに慣れていれば、あなたは十分にそのコンセプトを理解していると思います。
データはどのように格納され、何をしようとしているかによって異なります。
kレベルがRAMに格納され、いくつかのボトムレベルのみがディスクに格納され、それぞれのディスクの読み取りが必要となるため、通常は非常に少数のディスクアクセスが許可されます。O(1)だけが必要となるため、比較的高速でなければなりません。 上記のすべての欠点は、単一のキーが必要であることです。つまり、ハッシュテーブルまたはB +ツリーがリレーションのフィールド「id」に従って作成されている場合、「key " - それは役に立たなくなる。
リレーションのすべてのフィールドをすばやく検索するには、それぞれが異なるキーに応じていくつかの構造が必要です。これはメモリ効率があまり高くありません。
ここでは、特定の用途に応じて考慮する必要がある多くの最適化があります。たとえば、検索数が非常に少ないと予想される場合（たとえば、loglogNの合計操作数がより少ない場合）、B +ツリーを維持するのは全体的に効率が悪く、単にリストとして、まれにしか検索できません線形検索。
ほとんどの場合、MySQL（InnoDB）はBツリーを使って検索クエリを最適化します。 – nullpotent