MySQL インデックスによってクエリ効率が大幅に向上する理由は何ですか?-mysql チュートリアル-php.cn

背景

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

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

本文

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

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

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

まずはディスク IO について説明します。ディスクのデータ読み取りは機械的な動作に依存します。データを一度に取得するには、シーク、ポイントの検索、メモリへのコピーという 3 つのステップが必要です。

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

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

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

隣接するデータ

もメモリバッファに読み込まれます。これは、コンピュータがあるアドレスのデータにアクセスすると、そのデータはそのアドレスに隣接するためです。データへのアクセスも迅速になります。毎回 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 を表します。次のディスクブロックの場所。

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

1 回

]

2. ディスクブロック 1 には、17、35、および 3 つのポインターデータが格納されます。 173. 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 は本当に長すぎます。。。

まとめ

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

私は Ao Bing です。知れば知るほど、知らないことが増えます。次号でお会いしましょう!

タレント 私たちの 【三连】 が Ao Bing の創作の最大の動機です。このブログに間違いや提案がある場合は、タレントの方はコメントを残してください。メッセージ！