MySQL インデックスがクエリ効率を向上させる理由

mysqltutorial 列では、インデックスによってクエリ効率が向上する理由を紹介します。

背景

データベースを最適化する際には、誰もがインデックスについて話すと思います。私も例外ではありません。私は基本的に、データ構造の最適化に関するいくつかの質問と、ページ キャッシュに関するいくつかの質問に答えることができますが、あるとき Alibaba P9 の面接官が「コンピューター レベルのインデックス データについて話してもらえますか? 読み込みとは何ですか?」と尋ねたことがあります。プロセス？ (IO について話してほしかっただけです)

私はその場で死にました。コンピューター ネットワークとオペレーティング システムの基本的な知識は私の盲点だったのですが、後で補ったので、ナンセンスな話はしません。コンピューターがデータをロードするところから始めて、インデックス作成について別の角度から話しましょう。

本文

MySQL のインデックスは本質的にデータ構造です

まず、コンピューターへのデータの読み込みについて理解しましょう。

ディスク IO と事前読み取り:

まずディスク IO について話しましょう。ディスクからのデータの読み取りは機械的な動作に依存しており、データを読み取るたびにシーク、ポイントの検索、メモリへのコピー3 ステップの操作。

シーク時間は磁気アームが指定されたトラックに移動するのに必要な時間で、通常は 5ms 未満です。

サーチ ポイントはトラックからデータが存在するポイントを見つけるまでの平均時間は半回転、7200 rpm のディスクの場合、ポイントを見つけるまでの平均時間は 600000/7200/2=4.17ms;

メモリへのコピー 時間は非常に高速ですが、前の 2 回と比較すると無視できるほどであるため、1 回の IO の平均時間は約 9ms です。速いように思えますが、データベース内の数百万のデータを処理するには 9000 秒かかります。これは明らかに災害レベルです。

ディスク IO は非常にコストのかかる操作であることを考慮して、コンピューターのオペレーティング システムは先読みを最適化しています。現在のディスクアドレスのデータだけでなく、コンピュータがアドレスのデータにアクセスするとき、隣接するデータも非常に高速であるため、 隣接するデータ もメモリバッファに読み込まれます。 。

毎回 IO によって読み取られるデータをページと呼びます。ページ上のデータの具体的なサイズはオペレーティング システムによって異なります。通常は 4k または 8k です。つまり、1 ページでデータを読み取ります。この時点で、実際に発生した IO は 1 回だけでした。

(卒業直後に私が尋ねられた質問を突然思い出しました。64 ビット オペレーティング システムでは、Java の int 型は何バイトを占めますか?最大値はいくらですか?なぜですか?)

データベース クエリを最適化したい場合は、ディスク IO 操作を可能な限り削減する必要があります。そうすれば、インデックスが表示されます。

インデックスとは何ですか?

MySQLインデックスの正式な定義は次のとおりです。インデックス (インデックス) は、MySQL がデータを効率的に取得するのに役立つデータ構造です。

MySQL 一般的に使用されるインデックスは、B ツリー インデックスとハッシュ インデックスの 2 つのカテゴリに物理的に分類されます。

今回は主にBTreeインデックスについてお話します。

BTree インデックス

BTreeマルチパスバランスドサーチツリーとも呼ばれ、m-fork BTree の特徴は次のとおりです。

#ツリー内の各ノード ノードには最大 m 個の子が含まれます。

• ルート ノードとリーフ ノードを除き、各ノードには少なくとも [ceil(m/2)] 個の子があります (ceil() は切り上げられます)。
• ルート ノードがリーフ ノードでない場合、ルート ノードには少なくとも 2 つの子があります。
• すべてのリーフ ノードは同じレイヤー上にあります。
• 各非リーフ ノードは、n 個のキーと n 1 個のポインターで構成されます ([ceil(m/2)-1]

これは 3 つのフォークを含む BTree 構造図です (一例であり、実際には多数のフォークがあります) それぞれの正方形のブロックはディスク ブロックと呼ばれます。またはブロックと呼ばれ、これはオペレーティング システムが 1 回の IO でメモリに読み取るものです。1 つのブロックは 4 つのセクターに対応します。紫はディスク ブロック内のデータ キーを表し、黄色はデータを表し、青はディスク ブロックを指すポインタ p を表します。次のディスク ブロックの場所。

キー 29 でデータを検索するプロセスをシミュレートするには:

1. ルート ノード ポインタに従って、ファイル ディレクトリのルート ディスク ブロック 1 を読み取ります。 [ディスク IO 操作

1 回

]2. ディスク ブロック 1 には、17、35、および 3 つのポインター データが格納されます。 17

3. p2 ポインタに従って、ディスク ブロック 3 を見つけて読み取ります。 [ディスク IO 操作 2 回 ]

4. ディスク ブロック 3 には、26、30、および 3 ポインター データが格納されます。 26

5. p2 ポインタに従って、ディスク ブロック 8 を見つけて読み取ります。 [ディスク IO 操作 3 回 ]

6、ディスク ブロック 8 には 28、29 が格納されます。 29 を見つけて、29 に対応するデータを取得します。

BTree インデックスにより、メモリからフェッチされたデータが各ディスク I/O で役割を果たし、クエリ効率が向上することがわかります。

しかし、最適化できることはあるのでしょうか?

この図から、各ノードにはデータのキー値だけでなくデータ値も含まれていることがわかります。各ページの記憶容量は限られており、データデータが大きい場合、各ノード (つまり 1 ページ) に保存できるキーの数は非常に少なくなります。 to B- ツリーの深さが大きくなり、クエリ中のディスク I/O の数が増加し、クエリの効率に影響します。

B Tree Index

B Tree は B-Tree に基づいた最適化であり、外部ストレージ インデックス構造の実装により適しています。 B Treeでは、すべてのデータレコードノードがキー値順に同じ階層のリーフノードに格納され、非リーフノードにはキー値情報のみが格納されるため、各ノードに格納されるキー値の数を大幅に増やすことができます。 . B ツリーの高さを下げます。

B ツリーには、B ツリーと比較していくつかの違いがあります。

非リーフ ノードは、キー値情報、データ レコードのみを保存します。前節で B ツリーを最適化すると、B ツリーの非リーフ ノードにはキー値情報のみが格納されるため、B ツリーの高さを特に低いレベルに圧縮できます。

具体的なデータは次のとおりです:

InnoDB ストレージ エンジンのページ サイズは 16KB、一般テーブルの主キーのタイプは INT (4 バイトを占有) または BIGINT です(8 バイトを占有します。バイト)、ポインタ タイプは通常 4 または 8 バイトです。これは、1 つのページ (B ツリーのノード) に約 16KB/(8B 8B)=1K のキー値が格納されることを意味します (計算の便宜上、ここでの K の値は 〖10〗^3) とします。

つまり、深さ 3 の B ツリー インデックスは、10^3 * 10^3 * 10^3 = 10 億レコードを維持できます。 (この計算方法にはエラーがあり、リーフ ノードは計算されません。リーフ ノードが計算される場合、実際の深さは 4 になります。)

データを取得するために必要な IO 操作は 3 回だけです。必要なデータを見つけるには、9,000 秒の最初の 100 万個のデータよりも何倍優れているかわかりません。

そして通常、B ツリーには 2 つのヘッド ポインターがあり、1 つはルート ノードを指し、もう 1 つは最小のキーを持つリーフ ノードを指し、すべてのリーフ ノード間にはチェーン リング構造があります (つまり、データノード) 。そのため、B Treeでは主キー範囲検索やページング検索に加えて、ルートノードからのランダム検索も行うことができます。

データベースの B ツリー インデックスは、クラスター化インデックス (クラスター化インデックス) と補助インデックス (セカンダリ インデックス) に分類できます。

上記の B ツリーの例の図をデータベースに実装すると、クラスター化インデックスが作成されます。クラスター化インデックスの B ツリーのリーフ ノードには、テーブル全体の行レコード データが格納されます。補助インデックスとの違いは、次のとおりです。補助インデックスのリーフ ノードには、行レコードのすべてのデータが含まれるのではなく、対応する行データを格納するクラスター化インデックス キー、つまり主キーが含まれます。

補助インデックスを通じてデータをクエリする場合、InnoDB ストレージ エンジンは補助インデックスを走査して主キーを見つけ、主キーを通じてクラスター化インデックス内の完全な行レコード データを見つけます。

ただし、インデックスを使用するとクエリが高速化され、MySQL の処理パフォーマンスが向上しますが、インデックスを過度に使用すると、次の 欠点 :

• インデックスの作成と維持には時間がかかり、データ量が増えるとこの時間も長くなります。
• データ テーブルが占有するデータ領域に加えて、各インデックスも一定量の物理領域を占有します。クラスター化インデックスを作成する場合、必要なスペースはさらに大きくなります。
• テーブル内のデータを追加、削除、変更する場合、インデックスも動的に維持する必要があるため、データのメンテナンス速度が低下します。

注: インデックスを使用するとクエリを高速化できる場合もありますが、効率が低下する場合もあります。

インデックスは効率を向上させるための 1 つの要素にすぎないため、インデックスを作成するときは次の原則に従う必要があります。

• 頻繁に検索される列にインデックスを作成すると、検索を高速化できます。
• 列を主キーとしてインデックスを作成し、列の一意性を確保し、テーブル内のデータの配置構造を整理します。
• テーブル接続に頻繁に使用される列にインデックスを作成します。これらの列は主に外部キーであり、テーブル接続を高速化できます。
• 範囲に基づいて検索する必要が多い列にインデックスを作成します。インデックスは並べ替えられているため、指定された範囲は連続しています。
• 頻繁に並べ替えが必要な列にインデックスを作成します。インデックスは並べ替えられているため、インデックスの並べ替えを使用してクエリの並べ替えを高速化できます。
• WHERE句を頻繁に使用する列にインデックスを作成し、条件の判定を高速化します。

これで、インデックスがこれほど高速になる理由が誰でもわかりました。実際、これはほんの 1 文です。インデックス構造により、データベースの IO 回数を最小限に抑えることができます。結局のところ、1 回の IO 時間は本当に長すぎます。 。 。

まとめ

面接に関しては、実際には多くの知識を簡単に習得できますが、学習するためには、やらなければならないことがたくさんあることがわかります。 「コンピュータの基礎を深く理解して、それを発見してください。不思議です。どうしてそんなにたくさんのことを覚えているのかとよく聞かれます。実際、学ぶこと自体はとても無力なことです。学ばなければならないのですから、よく学べばいいのではありませんか。」楽しむことを学ぶには？最近は基礎の勉強もしているので、これからパソコンの基礎やネットワーク関連の知識も更新していこうと思います。

#その他の関連する無料学習の推奨事項: mysql チュートリアル(ビデオ)

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