MySQLインデックスの原理

MySQL データベースは、B ツリー インデックス、ハッシュ インデックス、フルテキスト インデックスなど、さまざまなインデックスをサポートしています。この記事では、B ツリー インデックスに焦点を当てます。 (推奨: 「mysql チュートリアル 」)

インデックスの原理と本質

MySQL 公式説明: インデックスはデータ取得の効率を高めるデータですMySQL の場合、データの高速クエリのための構造。インデックスは特定の検索アルゴリズムを満たすデータ構造であり、これらのデータ構造は効率的なデータ検索を実現するために特定の方法でデータを指します。

B ツリー

MySQL は一般に B ツリーをインデックス構造として使用しますが、B ツリーにはどのような特徴があるのでしょうか?

ツリー次数が n の場合、各ノード ポインターの上限は 2n 1

非リーフ ノードはデータを格納せず、ポインター インデックスのみを格納します。リーフ ノードはすべてのデータを格納しますが、ポインタを格納しない

従来の B ツリーに基づいて、シーケンシャル アクセス ポインタが追加され、図に示すように、各リーフ ノードは次の隣接するリーフ ノードへのポインタを持ちます。主にインターバルアクセスの性能向上のため、例えばキー20～50のデータを全て検索したい場合、シーケンシャルアクセスルートに従って全てのデータノードに一度にアクセスするだけで済みます。

シーケンシャル アクセスを使用した B ツリー ダイアグラム

局所性原則とディスク先読み

なぜデータベースを使用するのかシステムは通常、赤黒ツリーなどの他の構造ではなく、B ツリーをインデックス構造として使用しますか?

まず、局所性の原則とディスク先読みの概念を紹介します。

一般に、インデックス自体は大きいため、完全にメモリに保存されることはなく、インデックス ファイルの形式でディスクに保存されます。したがって、インデックス検索プロセス中にディスク IO 操作が発生しますが、ディスク IO はメモリ アクセスに比べて非常に遅いため、インデックス構造ではディスク IO アクセスの数を最小限に抑える必要があります。

ディスク IO を削減するために、ディスクはデータの事前読み取りを実行することが多く、特定の位置から開始して、一定の長さのデータを逆方向にメモリーに事前読み取りします。これは局所性の原理です。ディスクの順次読み取りは効率が高く、シーク時間が不要なため、IO 効率が向上します。

一般に、先読み長はページの整数倍であり、メインメモリとディスクはページ単位でデータを交換します。読み取る必要のあるデータがメモリにない場合、ページ フォールト割り込みがトリガーされます。システムはディスク データを読み取るリクエストをディスクに送信します。ディスクはデータの開始位置を見つけて、1 つまたは複数のデータを連続的に読み取ります。数ページのデータを逆方向に遡ってメモリにロードすると、割り込みが戻り、システムは動作を継続します。一般的なデータベース システムを設計する場合、B ツリー ノードのサイズは 1 ページに設定されるため、各ノードのロードに必要な IO は 1 回だけです。

以上がMySQLインデックスの原理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。