なぜmysqlインデックスは速いのでしょうか?-mysql チュートリアル-php.cn

インデックスは事前にソートされており、検索時に二分探索などの高効率アルゴリズムを適用できます。一般的な逐次探索の複雑さは O(n) ですが、二分探索の複雑さは O(log2n) であり、n が非常に大きい場合、両者の効率の差は大きくなります。

なぜmysqlインデックスは速いのでしょうか?

このチュートリアルの動作環境: Windows7 システム、mysql8 バージョン、Dell G3 コンピューター。

Mysql はインターネット上で非常に人気のあるデータベースです。基盤となるストレージエンジンとデータ取得エンジンの設計は非常に重要です。特に、Mysql データの格納形式とインデックスの設計がデータ全体を決定します。 Mysqlの検索性能。

インデックスの機能はデータを迅速に取得することであり、高速取得の本質はデータ構造であることはわかっています。さまざまなデータ構造を選択することで、さまざまなデータを迅速に取得できます。データベースには大量のデータが保存されており、効率的なインデックスにより時間を大幅に節約できるため、データベースでは効率的な検索アルゴリズムが非常に重要です。たとえば、次のデータテーブルでは、Mysql がインデックスアルゴリズムを実装していない場合、id=7 のデータを見つけるには、暴力的なシーケンシャルトラバーサルのみを使用できます。id=7 のデータを見つけるには、次のようにします。このテーブルに 1000 万件のデータが格納されている場合、id=1000W のデータを検索するには 1000W 回比較することになり、この速度は許容できません。

1. Mysql インデックスの基礎となるデータ構造の選択

##ハッシュテーブル (ハッシュ)ハッシュテーブルは、データを高速に取得するための効果的なツールです。

ハッシュアルゴリズム: ハッシュアルゴリズムとも呼ばれ、ハッシュ関数を通じて任意の値 (キー) を固定長のキーアドレスに変換し、このアドレスを使用して特定のデータのデータ構造を作成します。

ハッシュアルゴリズムは、最初に物理アドレス addr=hash(7)=4231 を計算して、id=7 のデータを保存します。4231 によってマップされた物理アドレスは 0x77 です。 0x77 は id=7 が格納される場所ですデータの物理アドレス user_name='g' に対応するデータは、この独立したアドレスから見つけることができます。これは、データを迅速に取得するためにハッシュアルゴリズムで使用される計算プロセスです。

しかし、ハッシュアルゴリズムにはデータ衝突の問題があります。つまり、ハッシュ関数は異なるキーに対して同じ結果を計算する可能性があります。たとえば、hash(7) は hash(199) と同じ結果を計算する可能性があります。つまり、異なるキーが同じ結果にマッピングされており、これは衝突の問題です。衝突問題を解決する一般的な方法は、リンクリストを使用して衝突するデータを接続するチェーンアドレス法です。ハッシュ値を計算した後、ハッシュ値がデータリンクリスト内で衝突しているかどうかも確認する必要があります。衝突している場合は、実際のキーに対応するデータが見つかるまで、リンクリストの最後まで走査されます。

从算法时间复杂度分析来看，哈希算法时间复杂度为 O（1），检索速度非常快。比如查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法，这是为什么呢？

因为考虑到数据检索有一个常用手段就是范围查找，比如以下这个 SQL 语句：

select * from user where id \>3;

ログイン後にコピー

针对以上这个语句，我们希望做的是找出 id>3 的数据，这是很典型的范围查找。如果使用哈希算法实现的索引，范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了，没有一点效率而言。

所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。

二叉查找树(BST)

二叉查找树是一种支持数据快速查找的数据结构，如图下所示:

二叉查找树的时间复杂度是 O(lgn)，比如针对上面这个二叉树结构，我们需要计算比较 3 次就可以检索到 id=7 的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？

答案是可以的。观察上面的图，二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id>5 的数据，那我们取出节点为 6 的节点以及其右子树就可以了，范围查找也算是比较容易实现。

但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。比如以下这个情况，二叉树已经极度不平衡了，已经退化为链表了，检索速度大大降低。此时检索 id=7 的数据的所需要计算的次数已经变为 7 了。

#データベースでは、データの自動インクリメントは非常に一般的な形式です。たとえば、テーブルの主キーは id で、主キーは id です。通常、key のデフォルトは自己増加ですが、バイナリツリーなどのデータ構造がインデックスとして使用される場合、上で紹介したアンバランスな状態によって引き起こされる線形探索の問題が必然的に発生します。したがって、単純な二分探索木には不均衡による検索パフォーマンスの低下という問題があり、Mysql の基礎となるインデックスの実装に直接使用することはできません。

AVL ツリーと赤黒ツリー

二分探索ツリーには不均衡の問題があるため、学者たちは自動 By を提案しました。二分木を基本的にバランスのとれた状態に保つように回転および調整することで、二分探索木の最高の検索パフォーマンスを維持できます。この考え方に基づく自己調整平衡状態を持つバイナリツリーには、AVL ツリーと赤黒ツリーが含まれます。

まず、赤黒ツリーについて簡単に紹介します。これは、木の形状を自動的に調整する木構造です。例えば、二分木がアンバランスな状態にある場合、赤黒ツリーは、ノードを自動的に左右に回転させ、ノードの色を変更します基本的なバランスの取れた状態 (時間計算量が O(logn)) を維持するようにツリーの形状を調整することで、検索効率が大幅に低下することはありません。たとえば、データノードが 1 から 7 まで昇順に挿入されると、通常の二分探索木はリンクリストに縮退しますが、赤黒木は図に示すように基本的なバランスを維持するために木の形状を継続的に調整します。下の図のとおりです。以下の赤黒ツリーで id=7 を検索するときに比較されるノードの数は 4 ですが、それでも二分木の良好な検索効率が維持されます。

赤黒ツリーは平均的な検索効率が良く、極端な O(n) 状況はありません。赤黒ツリーは Mysql の基礎となるインデックス実装として使用できますか?実際、赤黒の木にもいくつかの問題があります。次の例を見てください。

赤黒ツリーは 1 ～ 7 個のノードを順番に挿入しますが、id=7 を検索するときに計算する必要があるノードの数は 4 です。

AVL ツリーは 1 ～ 7 個のノードを順番に挿入し、id=7 のノードの比較回数は 3 回です。

#AVL ツリーは 1 ～ 16 のノードを順番に挿入しますが、id=16 を検索する場合に比較するノードの数は 4 です。検索効率の点では、AVL ツリーの検索速度は赤黒ツリーよりも高速です (AVL ツリーは 4 回の比較、赤黒ツリーは 6 回の比較)。樹形から判断すると、AVL の木には赤黒木のような「右傾」の問題がありません。言い換えれば、大量の連続挿入によってクエリのパフォーマンスが低下することはなく、これにより赤黒ツリーの問題が根本的に解決されます。

AVL ツリーの利点を要約します:

AVL ツリーはデータ検索用のデータ構造としては非常に優れているように見えますが、AVL ツリーは Mysql データベースのインデックスデータ構造には適していません。 :

データベースクエリデータのボトルネックはディスク IO です。AVL ツリーを使用する場合、各ツリーノードには 1 つのデータしか格納されません。1 つのノード上のデータを取り出してメモリにロードできるのは、次のコマンドだけです。 1 回のディスク IO たとえば、クエリ ID =7 このデータに対してディスク IO を 3 回実行する必要があり、時間がかかります。したがって、データベースのインデックスを設計するときは、まずディスク IO の数をできるだけ減らす方法を検討する必要があります。

ディスクIOには、ディスクから1Bのデータを読み込むのにかかる時間と、1KBのデータを読み込むのにかかる時間が基本的に同じであるという特性があり、この考えに基づいて、ツリー上で何度でも読み込むことができます。ノード。データをローカルに保存し、1 回のディスク IO でより多くのデータをメモリにロードします。これが B ツリーと B ツリーの設計原則です。

B ツリー

次の B ツリーは、ノードあたり最大 2 つのキーの保存に制限されています。キーは自動的に分割されます。たとえば、次の B ツリーには 7 個のデータが格納されています。id=7 のデータの特定の場所を知るには、2 つのノードをクエリするだけで済みます。つまり、2 つのディスク IO で指定されたデータをクエリできます。 AVL ツリー。

単一ノードのキー数制限を 6 に設定すると、7 個のデータを格納する B ツリーでは、id=7 のデータをクエリするために 2 つのディスク IO が必要になります。

16 個のデータを格納する B ツリーでは、ID=7 でデータをクエリするには 2 つのディスク IO が必要です。 -レート。 AVL ツリーと比較すると、ディスク IO の数が半分に減ります。

したがって、データベースインデックスデータ構造の選択という点では、B ツリーは非常に良い選択です。要約すると、データベースインデックスとして使用される B ツリーには次の利点があります。

#優れた検索速度、時間計算量: B ツリーの検索パフォーマンスは同等です。から O(h*logn)、そのうち、h はツリーの高さ、n は各ノードのキーワードの数です;
検索を高速化するために必要なディスク IO をできるだけ少なくします;
は範囲検索をサポートできます。
B ツリー

B ツリーと B ツリーの違いは何ですか?

まず、B ツリーは 1 つのノードにデータを格納し、B ツリーはインデックス (アドレス) を格納するため、B ツリーの 1 つのノードには大量のデータを格納できませんが、1 つのノードにはB ツリーのには多くのインデックスを格納でき、B ツリーのリーフノードにはすべてのデータが格納されます。

2 番目、B ツリーの葉ノードは、範囲検索を容易にするために、データステージでリンクリストを使用して直列に接続されます。

B ツリーと B ツリーを比較すると、B ツリーノードにインデックスが格納されていることがわかります。ストレージ容量が限られている場合でも、単一ノードに多数のインデックスを格納できるため、B ツリー全体の高さが減り、ディスク IO が削減されます。次に、B ツリーのリーフノードは、実際のデータが保存される場所です。リーフノードは、リンクリストを使用して接続されます。リンクリスト自体は順序付けされており、データ範囲内で検索する場合に効率的です。そこでMysqlのインデックスには検索効率や範囲検索の性能が非常に優れたB-treeが使われています。

2. Innodb エンジンと Myisam エンジンの実装

Mysql の基礎となるデータエンジンはプラグインの形式で設計されており、最も一般的なものは Innodb エンジンと Myisam です。ユーザーは個人のニーズに応じてカスタマイズできますが、Mysql データテーブルの基礎となるエンジンとして別のエンジンを選択する必要があります。 B-treeはMysqlのインデックスのデータ構造として非常に適していると分析しましたが、データとインデックスをどのように構成するかについても設計が必要であり、設計思想の違いからInnodbやMyisamも登場し、それぞれが独自のパフォーマンスを発揮します。。

MyISAM は優れたデータ検索パフォーマンスを備えていますが、トランザクション処理はサポートしていません。 Innodb の最大の特徴は、ACID 互換のトランザクション関数をサポートし、行レベルのロックをサポートしていることです。 Mysql がテーブルを作成するときにエンジンを指定できます。たとえば、次の例では、user テーブルと user2 テーブルのデータエンジンとしてそれぞれ Myisam と Innodb が指定されています。

#これら 2 つの命令を実行すると、システムは次のように表示されます。 2 つのエンジンのデータとインデックスが異なる方法で編成されていることを示します。

テーブルの作成後に Innodb によって生成されるファイルは次のとおりです:

テーブルの作成後に Myisam によって生成されるファイルは

# です。

##frm: テーブルを作成するステートメント

MYD: テーブル内のデータファイル (myisam データ)
MYI: テーブル内のインデックスファイルtable (myisam インデックス)

MyISAM エンジンの基盤となる実装 (非クラスター化インデックス方式)

MyISAM は非クラスター化インデックス方式、つまりデータとインデックスを使用します。ファイル上では 2 つの異なるものに分類されます。 MyISAM はテーブルを作成する際、主キーを KEY として主インデックス B ツリーを作成し、ツリーの葉ノードには対応するデータの物理アドレスが格納されます。この物理アドレスを取得したら、MyISAM データファイル内の特定のデータレコードを直接見つけることができます。

Innodb エンジンの基盤となる実装 (クラスター化インデックスメソッド)

InnoDB はクラスター化インデックスメソッドであるため、データとインデックスは同じ場所に保存されます。ファイル。まず、InnoDB は左下図のように主キー ID を KEY としてインデックス B ツリーを構築し、B ツリーの葉ノードには主キー ID に対応するデータが格納されます。 select * from user_info where id=15, InnoDB 主キー ID インデックス B ツリーがクエリされ、対応する user_name='Bob' が検索されます。

これは、テーブルの作成時に InnoDB が主キー ID インデックスツリーを自動的に構築するときです。これが、Mysql がテーブルの作成時に主キーを指定する必要がある理由です。テーブル内のフィールドにインデックスを追加するとき、InnoDB はどのようにインデックスツリーを構築しますか?たとえば、user_name フィールドにインデックスを追加する場合、InnoDB は user_name インデックス B ツリーを作成します。user_name の KEY はノードに格納され、リーフノードに格納されるデータは主キー KEY になります。リーフには主キー KEY が格納されることに注意してください。主キー KEY を取得した後、InnoDB は主キーインデックスツリーに移動し、user_name インデックスツリーで見つかった主キー KEY に基づいて対応するデータを検索します。

#問題は、なぜ InnoDB は特定のデータを主キーインデックスツリーのリーフノードにのみ保存し、他のデータには保存しないのかということです。インデックスツリーはどうですか? 特定のデータはどうですか? まず主キーを見つけてから、主キーインデックスツリーで対応するデータを見つける必要がある場合はどうすればよいですか?

InnoDB はストレージスペースを節約する必要があるため、実際には非常に簡単です。。テーブルには多数のインデックスが存在する可能性があります。InnoDB はインデックス付きフィールドごとにインデックスツリーを生成します。各フィールドのインデックスツリーに特定のデータが格納されている場合、このテーブルのインデックスデータファイルは非常に巨大になります (データが非常に冗長です)。ディスク領域を節約するという観点から見ると、各フィールドインデックスツリーに特定のデータを保存する必要は実際にはありません。この一見「不必要」な手順により、クエリのパフォーマンスが低下する代わりに、膨大なディスク領域が節約されます。これは非常に価値があります。

InnoDB と MyISAM の機能を比較したときに、MyISAM の方がクエリパフォーマンスが優れていると述べましたが、その理由は上記のインデックスファイルデータファイルの設計からわかります: MyISAM は物理アドレスを直接検索できるため、データはレコードですが、InnoDB がリーフノードをクエリした後、特定のデータを見つけるために主キーインデックスツリーを再度クエリする必要があります。つまり、MyISAM では 1 ステップでデータを見つけることができますが、InnoDB では 2 ステップ必要ですが、当然ながら MyISAM の方がクエリパフォーマンスは高くなります。

この記事では、まず Mysql の基礎となるインデックスの実装としてどのデータ構造がより適しているかを説明し、次に Mysql の 2 つの古典的なデータエンジン、MyISAM と InnoDB の基礎となる実装を紹介します。最後に、テーブル内のフィールドにインデックスを追加する必要がある場合をまとめてみましょう:

[関連する推奨事項:

mysql ビデオチュートリアル ]

以上がなぜmysqlインデックスは速いのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。