MySQL インデックスがクエリ効率を向上させる理由-mysql チュートリアル-php.cn

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

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

背景

データベースを最適化する際には、誰もがインデックスについて話すと思います。私も例外ではありません。私は基本的に、データ構造の最適化に関するいくつかの質問と、ページキャッシュに関するいくつかの質問に答えることができますが、あるとき 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 時間は本当に長すぎます。。。

まとめ

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