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

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

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

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

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

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

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

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

#このデータベース テーブル ユーザーについて考えてみましょう。テーブルには 7 つのデータがあります。id= を使用してデータを取得する必要があります。 7. SQL 構文は次のとおりです。

select * from user where id=7;

ハッシュ アルゴリズムは、最初に物理アドレス 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 です。

#赤黒ツリーは 1 ～ 16 個のノードを順番に挿入し、比較する必要があるノードの数を決定します。 id=16 の検索は 6 回です。このツリーの形状を観察してください。データを順番に挿入すると、ツリーの形状は常に「右傾」傾向になるというのは本当ですか?基本的に、赤黒ツリーは二分探索ツリーを完全に解決するわけではありません。この「右傾化」の傾向は、線形リンク リストに縮退する二分探索ツリーほど誇張されていませんが、データベースでは、主キーは通常、数百万、数千万です。この問題が赤黒ツリーに存在すると、検索パフォーマンスも膨大に消費されます。私たちのデータベースは、この無意味な待機を許容できません。

次に、別のより厳密な自己平衡型バイナリ ツリーである AVL ツリーについて考えてみましょう。 AVL ツリーは完全にバランスの取れたバイナリ ツリーであるため、バイナリ ツリーの形状を調整する際により多くのパフォーマンスを消費します。

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

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

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

優れた検索パフォーマンス (O(logn)) により、極端に非効率な検索状況は発生しません。
1. 
   
範囲検索やデータソートを実現できます。
2. 
   

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 ツリー。

#次は 16 個のデータを格納する B ツリーです。同様に、各ノードには最大 2 つのキーが格納されます. クエリ id=16 のデータは 4 つのノードでクエリおよび比較する必要があり、これは 4 倍のディスク IO を意味します。クエリのパフォーマンスは AVL ツリーと同じのようです。

ただし、ディスク IO で 1 つのデータを読み取るのにかかる時間は、基本的に読み取り時間と同じであることを考慮します。 100 個のデータ、その後の最適化 この考え方は、1 回のディスク IO でできるだけ多くのデータをメモリに読み取るように変更できます。これはツリーの構造に直接反映され、各ノードが格納できるキーを適切に増やすことができます。

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

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

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

1. #優れた検索速度、時間計算量: B ツリーの検索パフォーマンスは同等です。から O(h*logn)、そのうち、h はツリーの高さ、n は各ノードのキーワードの数です;
   
2. 検索を高速化するために必要なディスク IO をできるだけ少なくします;
   
3. は範囲検索をサポートできます。
   
4. 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 によって生成されるファイルは次のとおりです:

frm: テーブルを作成するステートメント
• 
  
idb: テーブル内のデータ インデックス ファイル
• 
  

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

# です。

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

• 
  MYD: テーブル内のデータ ファイル (myisam データ)
• 
  MYI: テーブル内のインデックス ファイルtable (myisam インデックス)
• 
  
生成されたファイルからは、2 つのエンジンの基礎となるデータとインデックスが異なる方法で編成されていることがわかります。MyISAM エンジンは、データとインデックスを 1 つのファイルごとに分離します。インデックス モード: Innodb エンジンはデータとインデックスを同じファイルに配置します。これはクラスター化インデックス モードと呼ばれます。以下では、これら 2 つのエンジンが B ツリー データ構造にどのように依存して、基礎となる実装の観点からエンジンの実装を整理するかを分析します。

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 の基礎となる実装を紹介します。最後に、テーブル内のフィールドにインデックスを追加する必要がある場合をまとめてみましょう:

# クエリ条件として頻繁に使用されるフィールドにはインデックスを付ける必要があります。
1. 
   
一意性の低いフィールドは、クエリ条件として頻繁に使用される場合でも、インデックスのみの作成には適していません。
2. 
   
フィールドが非常に頻繁に更新される場合は、インデックスの作成には適していません。
3. 
   

[関連する推奨事項:

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

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