MySQL インデックスの背後にあるデータ構造とアルゴリズム原理の詳細な説明
- 高洛峰オリジナル
- 2017-01-16 15:12:231070ブラウズ
要約
この記事では、MySQL データベースを研究対象として取り上げ、データベース インデックスに関連するいくつかのトピックについて説明します。 MySQL は多くのストレージ エンジンをサポートしており、ストレージ エンジンごとにインデックスのサポートが異なることに注意してください。そのため、MySQL データベースは BTree インデックス、ハッシュ インデックス、フルテキスト インデックスなどの複数のインデックス タイプをサポートしています。混乱を避けるために、この記事では BTree インデックスのみに焦点を当てます。これは主に MySQL を使用するときに扱われるインデックスであるためです。ハッシュ インデックスとフルテキスト インデックスについては、この記事では当面説明しません。いる。
記事の主な内容は3つのパートに分かれています。
最初の部分では、主にデータ構造とアルゴリズムの理論レベルから MySQL データベース インデックスの数学的基礎について説明します。
2 番目のパートでは、クラスター化インデックス、非クラスター化インデックス、MySQL データベースの MyISAM および InnoDB データ ストレージ エンジンのインデックスのアーキテクチャに基づくカバリング インデックスなどのトピックについて説明します。
3 番目のパートでは、上記の理論的根拠に基づいて、MySQL で高パフォーマンスのインデックスを使用するための戦略について説明します。
データ構造とアルゴリズムの基本
インデックスの本質
MySQL のインデックスの公式定義は次のとおりです: インデックス (インデックス) は、MySQL がデータを効率的に取得するのに役立つデータ構造です。文のバックボーンを抽出すると、インデックスの本質がわかります。インデックスはデータ構造です。
データベースクエリがデータベースの最も重要な機能の 1 つであることはわかっています。誰もができるだけ早くデータをクエリしたいと考えているため、データベース システムの設計者はクエリ アルゴリズムの観点から最適化を行います。最も基本的なクエリ アルゴリズムは、もちろん線形検索です。このアルゴリズムは、データ量が大きい場合には明らかに問題になります。バイナリなど、より優れた検索アルゴリズムが数多く提供されています。検索、二分木検索など。少し分析すると、各検索アルゴリズムは特定のデータ構造にのみ適用できることがわかります。たとえば、二分探索では取得したデータを順序付けする必要がありますが、二分木検索では二分探索木にのみ適用できます。データ自体 組織構造はさまざまなデータ構造を完全に満たすことはできません (たとえば、両方の列を同時に順番に整理することは理論的に不可能です)。 そのため、データベース システムはデータに加えて、特定の検索を満たすデータ構造も維持します。アルゴリズム。構造は何らかの方法でデータを参照 (ポイント) し、これらのデータ構造に高度な検索アルゴリズムを実装できます。このデータ構造がインデックスです。
例を見てみましょう:
図 1
図 1 は、考えられるインデックス付け方法の 1 つを示しています。左側はデータ テーブルで、合計 2 つの列と 7 つのレコードがあります。一番左はデータ レコードの物理アドレスです (論理的に隣接するレコードがディスク上で物理的に隣接している必要はないことに注意してください)。 Col2 の検索を高速化するために、右に示すように、各ノードにインデックス キー値と、対応するデータ レコードの物理アドレスへのポインターを含めることができます。 O(log2n) の二分探索 計算量内で対応するデータが得られます。
これは本物のインデックスですが、実際のデータベース システムでは二分探索木やその進化系である赤黒木を使用して実装されることはほとんどありません。その理由を以下に紹介します。
B-Tree と B+Tree
現在、ほとんどのデータベース システムとファイル システムは、インデックス構造として B-Tree またはそのバリアント B+Tree を使用しています。この記事の次のセクションでは、メモリと B+Tree の原理について説明します。 B-Tree と B+Tree がインデックス作成に広く使用されている理由について、このセクションではまず純粋にデータ構造の観点から説明します。
B-Tree
B-Treeを記述するには、まずデータレコードをタプル[key, data]として定義します。keyはレコードのキー値であり、異なるデータレコードのキーは互いに異なります。 ; data は、キーを除くデータを記録します。このとき、B-Tree は次の条件を満たすデータ構造です:
1。d は 1 より大きい正の整数であり、これを B-Tree の次数と呼びます。
2. h は、B ツリーの高さと呼ばれる正の整数です。
3. 各非リーフ ノードは、n-1 個のキーと n 個のポインターで構成されます (d
4. 各リーフ ノードには少なくとも 1 つのキーと 2 つのポインターが含まれ、最大で 2d-1 のキーと 2d ポインターが含まれます。リーフ ノードのポインターはすべて null です。
5. すべてのリーフ ノードの深さは同じであり、木の高さ h に等しくなります。
6. キーとポインターは互いに離れており、ノードの両端はポインターです。
7. ノード内のキーは左から右に非減少的に配置されます。
8. すべてのノードはツリー構造を形成します。
9. 各ポインターは null であるか、別のノードを指します。
10. ポインタがノードの左端にあり、null でない場合、それが指すすべてのキーは v(key1) より小さくなります。ここで、v(key1) はノードの最初のキーの値です。 。
11. ポインターがノードの右端にあり、null でない場合、それが指すすべてのキーは v(keym) より大きくなります。ここで、v(keym) はノードの最後のキーの値です。 。
12. ポインタの左側と右側の隣接するキーがそれぞれ keyi と keyi+1 であり、null でない場合、ノードが指すすべてのキーは v(keyi+1) より小さく、v より大きくなります。 （キーイ）。
図 2 は、d=2 の B ツリーの概略図です。
図 2
B ツリーの特性により、B ツリーでキーによってデータを取得するアルゴリズムは非常に直感的です。まずルート ノードから二分探索を実行し、見つかった場合はそのデータを返します。対応するノード、それ以外の場合は対応する間隔 ポインタが指すノードは、ノードが見つかるまで、または null ポインタが見つかるまで再帰的に検索されます。前者は成功し、後者は失敗します。 B ツリーの検索アルゴリズムの疑似コードは次のとおりです。
BTree_Search(node, key)
{
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);たとえば、次数 d の B ツリーのインデックスとして N 個のキーがある場合、その上限は次のとおりです。木の高さ h は logd ((N+1)/2) であり、キーを取得する場合のノード数の漸近複雑さは O(logdN) です。この点から、B-Tree が非常に効率的なインデックス データ構造であることがわかります。
また、新しいデータレコードの挿入と削除はB-Treeのプロパティを破壊するため、挿入と削除の際には、B-Treeのプロパティを維持するためにツリーの分割、結合、転送などを行う必要があります。 B ツリーについて詳しく説明するつもりはありません。B ツリーの数学的特性と挿入および削除アルゴリズムの詳細については、すでに多くの情報が存在するため、興味のある方は、この記事の最後にある参照欄で対応する情報を見つけることができます。読むこと。
B+Tree
B-Tree には多くのバリエーションがあり、その中で最も一般的なのは B+Tree です。たとえば、MySQL は一般的に B+Tree を使用してインデックス構造を実装します。
B-Tree と比較すると、B+Tree には以下の違いがあります:
1. 各ノードのポインターの上限は 2d+1 ではなく 2d です。
2. 内部ノードはデータを保存せず、キーのみがポインターを保存しません。
図 3 は、単純な B+Tree ダイアグラムです。
図 3
すべてのノードが同じドメインを持っているわけではないため、B+Tree のリーフ ノードと内部ノードは通常、異なるサイズになります。これは B-Tree とは異なります。B-Tree の異なるノードに格納されるキーとポインタの数は一致しない可能性がありますが、各ノードのドメインと上限は一致しているため、実装では B-Tree が同様に適用されることがよくあります。各ノードのスペースのサイズ。
一般に、B+Tree は B-Tree よりも外部ストレージ インデックス構造の実装に適しています。その具体的な理由は、以下で説明する外部メモリとコンピュータ アクセスの原理に関連しています。
シーケンシャルアクセスポインタを備えたB+ツリー
データベースシステムやファイルシステムで一般的に使用されるB+ツリー構造は、古典的なB+ツリーに基づいて最適化されており、シーケンシャルアクセスポインタが追加されています。
図4
図4に示すように、B+Treeの各リーフノードに隣接するリーフノードへのポインタを追加すると、シーケンシャルアクセスポインタを持つB+Treeが形成されます。この最適化の目的は、間隔アクセスのパフォーマンスを向上させることです。たとえば、図 4 で、18 から 49 までのキーを持つすべてのデータ レコードをクエリする場合、18 を見つけた後は、ノードとポインターを順番に走査するだけで済みます。すべてのデータノードに一度にアクセスできるため、間隔クエリの効率が大幅に向上します。
このセクションでは、B-Tree と B+Tree について簡単に説明します。次のセクションでは、メモリ アクセスの原則を組み合わせて、B+Tree が現在データベース システムのインデックス作成に推奨されるデータ構造である理由を紹介します。
B-Tree (B+Tree) を使用する理由
前述したように、赤黒ツリーなどのデータ構造もインデックスの実装に使用できますが、ファイル システムやデータベース システムでは一般に B-/+Tree がインデックスとして使用されますこのセクションでは、コンピュータの構成原理に関する知識に基づいたインデックスとしての B-/+Tree の理論的基礎について説明します。
一般に、インデックス自体も非常に大きく、完全にメモリに保存できないため、インデックスはインデックス ファイルの形式でディスクに保存されることがよくあります。この場合、インデックス検索処理中にディスク I/O 消費が発生するため、メモリアクセスに比べて I/O アクセスの消費量が大きくなり、データの品質を評価する最も重要な指標となります。インデックスとしての構造は、検索プロセス中のディスク I/O 操作の数の漸近複雑さです。言い換えれば、インデックスの構造構成により、検索プロセス中のディスク I/O アクセスの数が最小限に抑えられる必要があります。以下では、まずメモリとディスクアクセスの原理を紹介し、次にこれらの原理を組み合わせて、B-/+Tree の効率を指標として分析します。
メインメモリアクセスの原理
現在コンピュータで使用されているメインメモリは基本的にランダム読み書きメモリ (RAM) です。現代の RAM の構造とアクセス原理は比較的複雑です。ここでは、この記事では具体的な違いを無視して抽象化します。非常に単純なメモリ。RAM がどのように機能するかを示すモデルを取り上げます。
写真5
抽象的な観点から見ると、メイン メモリは一連のストレージ ユニットで構成されるマトリックスであり、各ストレージ ユニットには固定サイズのデータが格納されます。各ストレージ ユニットには一意のアドレスがあります。現代のメイン メモリのアドレス指定規則は、ここでは 2 次元アドレスに単純化されています。つまり、ストレージ ユニットは行アドレスと列アドレスによって一意に配置されます。図 5 は、4 x 4 メイン メモリ モデルを示しています。
メインメモリのアクセスプロセスは次のとおりです:
システムがメインメモリを読み取る必要がある場合、アドレス信号をアドレスバスに置き、メインメモリがアドレス信号を読み取った後、それをメインメモリに渡します。信号を解析して指定されたストレージ ユニットの位置を特定し、このストレージ ユニットのデータを他のコンポーネントが読み取れるようにデータ バス上に置きます。
メイン メモリへの書き込みプロセスも同様です。システムは、書き込まれるユニット アドレスとデータをそれぞれアドレス バスとデータ バスに配置し、対応する書き込み操作を実行します。
ここで、メインメモリへのアクセス時間はアクセス数と直線的にのみ関係していることがわかります。機械的な操作がないため、2 回アクセスされるデータの「距離」は時間に影響を与えません。たとえば、最初に A0 を取得します。次に A1 を取得する場合の所要時間は、最初に A0 を取得し、次に D3 を取得する場合と同じです。
ディスクアクセスの原則
上で述べたように、インデックスは通常、ファイルの形式でディスクに保存され、インデックスの取得にはディスク I/O 操作が必要です。メインメモリとは異なり、ディスク I/O には機械的な移動コストがかかるため、ディスク I/O の消費時間は膨大になります。
図6は、ディスクの全体構造の模式図です。
図 6
ディスクは、同じサイズの同軸の円形ディスクで構成されます。ディスクは回転できます (各ディスクは同期して回転する必要があります)。ディスクの片側にはヘッド ブラケットがあり、各ヘッドがディスクの内容にアクセスする役割を果たします。磁気ヘッドは回転できませんが、ディスクの半径に沿って移動できます (実際には斜めの接線方向の移動)。各磁気ヘッドは同時に同軸である必要があります。つまり、真上から見たときに、すべての磁気ヘッドがどの位置でも重なっています。 （ただし、現時点ではこの制約を受けないマルチヘッド独立技術も存在します）。
図7はディスク構造の模式図です。
図 7
ディスクは一連の同心円状のリングに分割されており、各同心円状のリングは同じ半径を持つすべてのトラックと呼ばれます。トラックは半径線に沿って小さなセグメントに分割され、各セグメントはセクタと呼ばれ、各セクタはディスクの最小の記憶単位です。簡単にするために、以下では、ディスクには 1 つのプラッタと 1 つのヘッドだけがあると仮定します。
データをディスクから読み取る必要がある場合、システムはデータの論理アドレスをディスクに転送します。ディスクの制御回路は、アドレス指定ロジックに従って論理アドレスを物理アドレスに変換します。読み取られるデータがどのトラックとセクタにあるかを決定します。このセクタのデータを読み取るには、磁気ヘッドをこのセクタ上に配置する必要があります。このプロセスはシークと呼ばれ、その時間がかかります。このプロセスに費やされる時間は、ディスクの回転時間と呼ばれます。
局所性の原則とディスクの事前読み取り
記憶媒体の特性により、ディスク自体のアクセスはメインメモリよりもはるかに遅く、機械的な移動のコストと相まって、ディスクのアクセス速度は多くの場合、高速です。まず、効率を向上させるために、ディスク I/O を最小限に抑える必要があります。この目標を達成するために、ディスクは厳密にオンデマンドで読み取るのではなく、たとえ 1 バイトしか必要とされない場合でも、毎回事前に読み取りを開始し、この位置から一定の長さのデータを順番に読み取ります。メモリ。これを行うための理論的基礎は、コンピューター サイエンスにおける有名な局所性原理です。
データの一部が使用されると、通常は近くのデータがすぐに使用されます。
通常、プログラムの実行中に必要なデータが集中しています。
ディスクの順次読み取りは非常に効率的であるため (シーク時間が不要で、スピン時間が非常に短い)、先読みにより局所性のあるプログラムの I/O 効率が向上します。
先読みの長さは通常、ページの整数倍です。ページは、コンピュータが管理するメモリの論理ブロックであり、多くの場合、メイン メモリとディスク ストレージ領域は、各ストレージ ブロックを連続した同じサイズのブロックに分割します (多くのオペレーティング システムでは、ページ サイズは通常 4k)。メインメモリとディスクはページ単位でデータを交換します。プログラムによって読み取られるデータがメインメモリにない場合、ページフォールト例外がトリガーされ、システムはディスクに読み取り信号を送信し、ディスクはデータの開始位置を見つけます。 1 つ以上のページを逆方向に読み取ってメモリにロードすると、異常終了してプログラムは実行を続けます。
B-/+Tree インデックスのパフォーマンス分析
この時点で、最終的に B-/+Tree インデックスのパフォーマンスを分析できるようになります。
前述したように、インデックス構造の品質を評価するには、ディスク I/O の数が一般的に使用されます。 B ツリー分析から始めましょう。B ツリーの定義によれば、1 回の検索で最大 h 個のノードを訪問する必要があることがわかります。データベース システムの設計者は、ディスク先読みの原理を巧みに利用し、ノードのサイズを 1 ページに等しくなるように設定しました。これにより、各ノードは 1 つの I/O だけで完全にロードできるようになります。この目標を達成するには、B ツリーの実際の実装で次のテクニックを使用する必要があります:
新しいノードが作成されるたびに、スペースのページが直接適用され、ノードが物理的に保存されます。これらはすべてページごとに調整されます。つまり、1 つのノードに必要な I/O は 1 つだけです。
B ツリーでの取得には最大でも h-1 の I/O (ルート ノードはメモリ内に常駐) が必要で、漸近複雑度は O(h)=O(logdN) です。一般的な実際のアプリケーションでは、出次数 d は非常に大きな数 (通常は 100 を超える) であるため、h は非常に小さくなります (通常は 3 以下)。
要約すると、B-Tree をインデックス構造として使用することは非常に効率的です。
赤黒の木のような構造では、h は明らかにはるかに深くなります。論理的に近いノード (親と子) は物理的に遠く離れている可能性があり、局所性を利用できないため、赤黒ツリーの I/O 漸近複雑度も O(h) であり、効率は明らかにそれよりもはるかに悪くなります。 B ツリーの。
前述したように、B+Tree は外部メモリのインデックスに適しています。その理由は、内部ノードの出次数 d に関連しています。上記の分析から、d が大きいほどインデックスのパフォーマンスが向上し、出力次数の上限はノード内のキーとデータのサイズに依存することがわかります。 / (キーサイズ + データサイズ + ポイントサイズ)) (ページサイズ – dmax >= ポイントサイズ)
または
dmax = Floor(ページサイズ / (キーサイズ + データサイズ + ポイントサイズ)) – 1 (ページサイズ – dmax
フロア切り捨てという意味です。 B+Tree ではデータ ドメインがノードから削除されるため、出次数が大きくなり、パフォーマンスが向上します。
この章では、理論的な観点からインデックスに関連するデータ構造とアルゴリズムの問題について説明します。次の章では、MySQL でのインデックスとしての B+Tree の実装方法についても説明します。また、非クラスター化インデックスと MyISAM に基づくインデックスについても説明します。 InnDB ストレージ エンジンには、クラスター化インデックスの 2 つの異なるインデックス実装形式があります。
MySQL インデックスの実装
MySQL では、インデックスはストレージ エンジン レベルの概念です。この記事では、主に 2 つのストレージ エンジン MyISAM と InnoDB のインデックス実装方法について説明します。
MyISAM インデックスの実装
MyISAM エンジンは、インデックス構造として B+Tree を使用します。リーフ ノードのデータ フィールドには、データ レコードのアドレスが格納されます。次の図は、MyISAM インデックスの概略図です。
図 8
ここのテーブルには主キーとして Col1 を使用すると仮定し、図 8 は主インデックス (Primary.キー) MyISAM テーブルの。 MyISAM のインデックス ファイルはデータ レコードのアドレスのみを保存していることがわかります。 MyISAM では、プライマリ インデックスとセカンダリ インデックス (セカンダリ キー) の間に構造上の違いはありません。ただし、プライマリ インデックスではキーが一意である必要があるのに対し、セカンダリ インデックスのキーは繰り返すことができる点が異なります。 Col2 に補助インデックスを作成すると、このインデックスの構造は次の図のようになります。
図 9
も B+Tree であり、データ フィールドにはデータ レコードのアドレスが保存されます。したがって、MyISAM のインデックス検索アルゴリズムは、まず B+Tree 検索アルゴリズムに従ってインデックスを検索し、指定された Key が存在する場合、そのデータ フィールドの値を取り出し、そのデータ フィールドの値をそのまま使用します。対応するデータレコードを読み取るためのアドレス。
MyISAM のインデックス作成方法は、InnoDB のクラスター化インデックスと区別するために「非クラスター化」とも呼ばれます。
InnoDBのインデックス実装
InnoDBもインデックス構造としてB+Treeを採用していますが、具体的な実装方法はMyISAMとは全く異なります。
最初の大きな違いは、InnoDB のデータ ファイル自体がインデックス ファイルであることです。上記からわかるように、MyISAM インデックス ファイルとデータ ファイルは分離されており、インデックス ファイルにはデータ レコードのアドレスのみが保存されます。 InnoDB では、テーブル データ ファイル自体は B+Tree によって編成されたインデックス構造であり、このツリーのリーフ ノード データ フィールドには完全なデータ レコードが保存されます。このインデックスのキーはデータ テーブルの主キーであるため、InnoDB テーブル データ ファイル自体が主インデックスになります。
写真10
图10是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
图11
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
下一章将具体讨论这些与索引有关的优化策略。
索引使用策略及优化
MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础，实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。
示例数据库
为了讨论索引策略，需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一：employees。这个数据库关系复杂度适中，且数据量较大。下图是这个数据库的E-R关系图（引用自MySQL官方手册）：
图12
MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库，并提供了下载地址和导入方法，如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。
最左前缀原理与相关优化
高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。
这里先说一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组
以employees.titles表为例，下面先查看其上都有哪些索引：
SHOW INDEX FROM employees.titles; +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+ | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type | +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+ | titles | 0 | PRIMARY | 1 | emp_no | A | NULL | | BTREE | | titles | 0 | PRIMARY | 2 | title | A | NULL | | BTREE | | titles | 0 | PRIMARY | 3 | from_date | A | 443308 | | BTREE | | titles | 1 | emp_no | 1 | emp_no | A | 443308 | | BTREE | +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
从结果中可以到titles表的主索引为
ALTER TABLE employees.titles DROP INDEX emp_no;
这样就可以专心分析索引PRIMARY的行为了。
情况一：全列匹配。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26'; +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。这里有一点需要注意，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，例如我们将where中的条件顺序颠倒：
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer'; +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
效果是一样的。
情况二：最左前缀匹配。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
当查询条件精确匹配索引的左边连续一个或几个列时，如
情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
此时索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date（这里由于emp_no唯一，所以不存在扫描）。如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引
首先我们看下title一共有几种不同的值：
SELECT DISTINCT(title) FROM employees.titles; +--------------------+ | title | +--------------------+ | Senior Engineer | | Staff | | Engineer | | Senior Staff | | Assistant Engineer | | Technique Leader | | Manager | +--------------------+
只有7种。在这种成为“坑”的列值比较少的情况下，可以考虑用“IN”来填补这个“坑”从而形成最左前缀：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager') AND from_date='1986-06-26'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 7 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
这次key_len为59，说明索引被用全了，但是从type和rows看出IN实际上执行了一个range查询，这里检查了7个key。看下两种查询的性能比较：
SHOW PROFILES; +----------+------------+-------------------------------------------------------------------------------+ | Query_ID | Duration | Query | +----------+------------+-------------------------------------------------------------------------------+ | 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'| | 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ... | +----------+------------+-------------------------------------------------------------------------------+
“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据，则后者性能优势会更加明显。当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。
情况四：查询条件没有指定索引第一列。
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26'; +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
由于不是最左前缀，索引这样的查询显然用不到索引。
情况五：匹配某列的前缀字符串。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 56 | NULL | 1 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
此时可以用到索引，但是如果通配符不是只出现在末尾，则无法使用索引。（原文表述有误，如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀）
情况六：范围查询。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < 10010' AND title='Senior Engineer' AND from_date BETWEEN '1986-01-01' AND '1986-12-31'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方，那就是仅用explain可能无法区分范围索引和多值匹配，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no BETWEEN '10001' AND '10010' AND title='Senior Engineer' AND from_date BETWEEN '1986-01-01' AND '1986-12-31'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
看起来是用了两个范围查询，但作用于emp_no上的“BETWEEN”实际上相当于“IN”，也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配，否则会对MySQL的行为产生困惑。
情况七：查询条件中含有函数或表达式。
很不幸，如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引（虽然某些在数学意义上可以使用）。例如：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
虽然这个查询和情况五中功能相同，但是由于使用了函数left，则无法为title列应用索引，而情况五中用LIKE则可以。再如：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000'; +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
显然这个查询等价于查询emp_no为10001的函数，但是由于查询条件是一个表达式，MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度，因此在写查询语句时尽量避免表达式出现在查询中，而是先手工私下代数运算，转换为无表达式的查询语句。
索引选择性与前缀索引
既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。
第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。例如，上文用到的employees.titles表，如果title字段经常被单独查询，是否需要建索引，我们看一下它的选择性：
SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles; +-------------+ | Selectivity | +-------------+ | 0.0000 | +-------------+
title的选择性不足0.0001（精确值为0.00001579），所以实在没有什么必要为其单独建索引。
有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。
从图12可以看到employees表只有一个索引
EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido'; +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where | +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
如果频繁按名字搜索员工，这样显然效率很低，因此我们可以考虑建索引。有两种选择，建
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.0042 | +-------------+ SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.9313 | +-------------+
SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.7879 | +-------------+
选择性还不错，但离0.9313还是有点距离，那么把last_name前缀加到4：
SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.9007 | +-------------+
这时选择性已经很理想了，而这个索引的长度只有18，比
ALTER TABLE employees.employees ADD INDEX `first_name_last_name4` (first_name, last_name(4));
此时再执行一遍按名字查询，比较分析一下与建索引前的结果：
SHOW PROFILES; +----------+------------+---------------------------------------------------------------------------------+ | Query_ID | Duration | Query | +----------+------------+---------------------------------------------------------------------------------+ | 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' | | 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' | +----------+------------+---------------------------------------------------------------------------------+
性能的提升是显著的，查询速度提高了120多倍。
前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。
InnoDB的主键选择与插入优化
在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
经常看到有帖子或博客讨论主键选择问题，有人建议使用业务无关的自增主键，有人觉得没有必要，完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点，大多数论据都是业务层面的。如果从数据库索引优化角度看，使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。
上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：
图13
这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：
图14
此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
因此，只要可以，请尽量在InnoDB上采用自增字段做主键。
后记
この記事は半月にわたって断続的に書いており、主な内容は上記の通りです。私の MySQL の使用は初心者レベルであり、データベースのチューニングの経験もあまりないため、この記事がある程度の安楽椅子での練習であることは否定できません。それについて話すのは少しおこがましいかもしれません。データベースインデックスのチューニングはここで行います。私の個人的な勉強メモとして扱ってください。
実際、データベースのインデックスチューニングは技術的な仕事であり、理論だけに頼ることはできません。実際の状況は常に変化しており、MySQL 自体もクエリ最適化戦略やさまざまなエンジンの実装の違いなど、非常に複雑なメカニズムを備えているからです。 、状況はさらに複雑になります。しかし同時に、これらの理論はインデックス調整の基礎であり、理論を理解することによってのみ、調整戦略について合理的な推論を行うことができ、実際に継続的な実験と探索を組み合わせることで、真の意味での理解が可能になります。 MySQL のインデックス作成の目的を効率的に使用します。
さらに、MySQL インデックスとその最適化は非常に広範囲をカバーしており、この記事ではその一部のみに触れます。たとえば、インデックスの最適化やソート (ORDER BY) に関連するインデックスのカバーについては、この記事では取り上げません。MySQL は、B ツリー インデックスに加えて、さまざまなエンジンに基づいたハッシュ インデックス、フルテキスト インデックスなどもサポートしています。 . この記事でも取り上げていません。機会があれば、この記事で紹介しきれなかった部分も追加していきたいと思います。
参考文献
[1] Baron Scbwartz 他、Wang Xiaodong 他訳、High Performance MySQL、2010 年
[2] Michael Kofler、Yang Xiaoyun 他訳、MySQL5 Authoritative Guide (MySQL5 の決定版ガイド)、People's Posts and Telecommunications Press、2006 年
[3] Jiang Chengyao 著、MySQL Technology Insider-InnoDB Storage Engine、2011 年
[4] D Comer、ユビキタス B ツリー; ACM Computing Surveys (CSUR)、1979 年
[5] Codd、E.F. (1970)、「Communications of the ACM」、Vol. 13、No. 6、pp. 377-387
[6] MySQL5.1 リファレンス マニュアル – http://dev.mysql.com/doc/refman/5.1/zh/index.html
MySQL の背後にあるデータ構造とアルゴリズム原理の詳細な説明については、インデックスについては、関連記事 PHP 中国語 Web サイトにご注目ください。