MySQL のインデックスとは何ですか?インデックスストレージモデルの簡単な分析

次のmysqlチュートリアルコラムでは、MySQLのインデックスを詳細に分析し、MySQLインデックスに関する知識を紹介します。

MySQL データベースは、最も一般的に使用されているデータベースの 1 つです。大小さまざまな企業で使用されています。MySQL データベースをどの程度使いこなしていますか? ?ことわざにあるように、労働者が仕事をうまくやりたいなら、まず道具を研ぐ必要があります。 この記事は、MySQL インデックスに関する知識の詳細な分析につながります。まず、インデックスとは何か、インデックス ストレージ モデルの推論、および基礎となるデータ構造がなぜ ## であるかを理解しましょう。 #B木

その理由は？

インデックスとは何ですか?

テーブルには 500 万個のデータがあります。インデックスなしで名前フィールドに対して where クエリを実行します:

select * from user_innodb where name ='小马';

名前フィールドにインデックスがある場合はどうなりますか? name フィールドにインデックスを作成し、同じクエリを再度実行します。

ALTER TABLE user_innodb DROP INDEX idx_name; 
ALTER TABLE user_innodb ADD INDEX idx_name (name);

インデックスを使用しないクエリと比較すると、インデックスを使用したクエリの効率は数十倍異なります。

この事例を通じて、インデックスによってデータ検索のパフォーマンスが大幅に向上することが誰でも直感的にわかるはずです。

それでは、インデックスとは一体何なのでしょうか?なぜクエリにこれほど大きな影響を与えるのでしょうか?インデックスが作成されるとどうなりますか?

インデックス定義

データベース インデックスは、データベース管理システム (DBMS) 内のソートされたデータ構造であり、データベース テーブル内のデータの迅速なクエリと更新を支援します。 . .

#データはファイルの形式でディスクに保存され、データの各行にはディスク アドレスが割り当てられます。インデックスがない場合、500 万行のデータから 1 つのデータを取得する必要があり、このデータが見つかるまでこのテーブル内のすべてのデータを走査することしかできません。

ただし、インデックスを取得した後は、このデータをインデックスから取得するだけで済みます。これは、高速な取得を目的として設計された特別なデータ構造であるためです。データが保存されているディスク アドレスが見つかったら、データを取得できます。

インデックス タイプ

InnoDB には、通常のインデックス、一意のインデックス (主キー インデックスは特殊な一意のインデックス)、およびフルの 3 つのインデックス タイプがあります。 -テキストインデックス。

通常

: 非固有インデックスとも呼ばれ、制限のない最も一般的なインデックスです。

Unique

: 一意のインデックスでは、キー値が重複できない必要があります。さらに、主キー インデックスは特別な一意のインデックスであることに注意してください。また、キー値を空にすることはできないという追加の制限もあります。主キーインデックスは主キーを使用して作成されます。

全文: 比較的大きなデータの場合、たとえばメッセージ コンテンツと数 KB のデータを保存する場合、クエリ効率が低いという問題を解決したい場合は、全文インデックス。フルテキスト インデックスは、char、varchar、text などのテキスト タイプのフィールドに対してのみ作成できます。

インデックスはデータ構造です。効率的なデータ検索を実現するには、どのようなデータ構造を選択する必要がありますか?

インデックス ストレージ モデルの推論

二分探索

##ダブルイレブンが過ぎた後、あなたのガールフレンドはあなたと一緒に数字当てゲームをしました。昨日私がいくら買ったかを推測し、5 回のチャンスを与えます。 ＃＃＃＃＃＃＃＃＃10000？低い。 30000？背が高い。次に何を推測しますか? 20000。なぜ11,000か29,000と推測しなかったのですか？

これは二分探索 (ハーフサーチとも呼ばれます) の考え方で、毎回候補データを半分に減らします。データがソートされている場合、この方法はより効率的です。

したがって、まず、順序付けされた配列をインデックス データ構造として使用することを検討できます。

等値クエリと順序配列の比較クエリは非常に効率的ですが、データの更新時に問題が発生します。大量のデータの移動 (インデックスの変更) が必要になる可能性があるため、静的なデータの保存にのみ適しています。データ。

データの挿入などの頻繁な変更をサポートするには、リンク リストを使用する必要があります。連結リストに関しては、単一連結リストの場合、まだ検索効率が十分ではありません。

それでは、二分探索を使用できるリンク リストはありますか?

この問題を解決するために、BST (Binary [ˈbaɪnəri] Search Tree)、いわゆる二分探索木が誕生しました。

二分探索ツリー

左側のサブツリーのすべてのノードは親ノードより小さく、右側のサブツリーのすべてのノードは親ノードより大きいノード。平面に投影すると、規則的な線形テーブルになります。

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

すると、ツリーのノードのサイズは 16K になります。整数フィールドなど、ノードに 1 つの キーと値のデータ参照 だけを格納する場合、使用できるバイト数は数十バイトだけであり、16K の容量には遠く及ばないため、ツリー ノードにアクセスする必要があります。 IO の実行時に多くのスペースを無駄にします。

したがって、各ノードに保存されているデータが少なすぎる場合、インデックスから必要なデータを見つけるために、より多くのノードにアクセスする必要があります。これは、ディスクとのやり取りが多すぎることを意味します。

機械式ハードディスクの時代では、ディスクからデータを読み出すのに毎回約 10ms のシーク時間がかかり、インタラクションが増えるほど時間がかかります。

たとえば、上の図では、1 つのテーブルに 6 つのデータがあります。id=37 をクエリするとき、2 つの子ノードをクエリするには、ディスクと 3 回対話する必要があります。数百件 10,000 件のデータはどうなるでしょうか?今回の時間を見積もるのはさらに困難です。

それでは、私たちの解決策は何でしょうか?

最初の方法は、各ノードがより多くのデータを保存できるようにすることです。

第 2 に、ノード上のキーワードが増えるほど、より多くのポインターが存在することになります。これは、より多くのフォークが存在する可能性があることを意味します。

枝の数が増えるとツリーの深さが減ります(ルートノードは0になります)。このようにして、私たちの木は元の背が高くて細い見た目から、短くて太い見た目に変わるでしょうか？

現時点では、私たちのツリーは二股ではなく、多股、つまり多方向になっています。

マルチパス分散検索ツリー (B ツリー)

AVL ツリーと同様に、B ツリーはキー値、データ アドレス、およびノー​​ド参照をブランチ ノードに格納します。そして葉のノード。

フォークの数 (パスの数) は常にキーワードの数より 1 多いという特徴があります。たとえば、描画したツリーでは、各ノードに 2 つのキーワードが格納されているため、3 つの子ノードを指す 3 つのポインターが存在します。

#B Tree の検索ルールは何ですか?

たとえば、このテーブルで 15 を見つけたいとします。 15 は 17 より小さいので、左に進みます。 15 は 12 より大きいので、右に進みます。 15 はディスク ブロック 7 で見つかり、3 つの IO のみが使用されました。

これは AVL ツリーよりも効率的ですか?では、B Tree は、1 つのノードに複数のキーワードが格納され、バランスが保たれていることをどのように認識するのでしょうか? AVL ツリーとの違いは何ですか?

たとえば、最大次数 (ウェイの数) が 3 の場合、データ 1、2、および 3 を挿入します。3 を挿入する場合、最初のディスク ブロックに挿入する必要がありますが、キーワードが使用されると、ポインターが 4 つあることを意味し、子ノードは 4-way になるため、この時点で分割する必要があります (実際には B Tree)。真ん中のデータ2を取り出し、1と3を2の子ノードにします。

ノードを削除すると、逆マージ操作が行われます。

これは分割と結合であり、AVL ツリーの左右の回転とは異なることに注意してください。

引き続き 4 と 5 を挿入すると、B ツリーが分割され、再び結合されます。

このことから、インデックスの更新時に多数のインデックス構造の調整が必要になることもわかります。これが、頻繁に更新される列を更新したくない理由の説明になります。上記のインデックスを構築するか、主キーを更新してみてはいかがでしょうか。

ノードの分割とマージは、実際には InnoDB ページの分割とマージです。

B Tree (B Tree の強化版)

B Tree はすでに非常に効率的ですが、なぜ MySQL はさらに B Tree を改良して最終的に使用する必要があるのでしょうか? B ツリーはどうですか?

一般に、この改良された B-Tree バージョンは、B-Tree よりも包括的な問題を解決します。

InnoDB の B ツリーのストレージ構造を見てみましょう:

MySQL の B ツリーには、いくつかの特徴があります。

1. キーワードの数はパスの数と同じです;

2. B ツリーはルート ノードにデータを保存しませんまたはブランチ ノードの場合、リーフ ノードのみがデータを保存します。キーワードの検索は直接返されず、最後のレイヤーのリーフ ノードに移動します。例えば、id=28を検索すると、最初の階層で直接ヒットしますが、データはすべてリーフノードにあるので、下方向にリーフノードまで検索を続けます。

3. B ツリーの各リーフ ノードは、隣接するリーフ ノードへのポインタを追加し、その最後のデータは次のリーフ ノードの最初のデータを指し、順序付けられた構造を形成します。リンクされたリスト。

4. 左側が閉じ、右側が開いている間隔 [ ) に基づいてデータを取得します。

B Tree のデータ検索プロセス:

1. たとえば、28 を検索する場合、ルート ノードでキー値が見つかりますが、ページの子ノードではないため、下方向に検索を続けます。28 は、 left closed right of [28,66) 開いた区間の臨界値です。したがって、中央の子ノードが探索され、その後、検索が続行されます。これは、次の左閉区間と右開区間の臨界値でもあります。 [28,34) なので、左側の子ノードがたどられ、最後に葉ノードで必要なデータが見つかりました。

2. 2 番目に、範囲クエリの場合、たとえば、22 から 60 までのデータをクエリする場合、22 を見つけた後は、ノードとポインタを順番に走査するだけで済みます。すべてのデータ ノードに一度にアクセスできるため、間隔クエリの効率が大幅に向上します (検索を繰り返し実行するために上位の親ノードに戻る必要がありません)。

InnoDB の B ツリーの特徴:

1. B ツリーのバリアントであり、B によって解決できます。ツリーの問題は解決できます。 B Tree が解決する 2 つの主要な問題は何ですか? (各ノードはより多くのキーワード、より多くのパスを保存します) ;

2. データベースとテーブルのスキャン機能が強化されました (テーブルに対して完全なテーブル スキャンを実行したい場合は、リーフ ノードを走査するだけで済みます)十分です。すべてのデータを取得するために B ツリー全体を走査する必要はありません);

3. B ツリーのディスク読み取りおよび書き込み機能は、B ツリーのディスク読み取りおよび書き込み機能よりも強力です (ルート ノード ブランチ ノードはデータ領域を保存しないため、ノードはより多くのキーワードを保存し、一度にディスクからより多くのキーワードをロードできます);

4. ソート機能がより強力です (なぜなら、次のデータ領域へのポインタがあり、データはリンクされたリストを形成します);

5. 効率がより安定しています (B ツリーは常にリーフ ノードでデータを取得するため、その数はIO の数は安定しています)。

追記

これを見れば、MySQL がインデックスのデータ構造モデルとして B ツリーの使用を選択する理由が誰もがわかるはずです。

プログラミング関連の知識について詳しくは、プログラミング入門をご覧ください。 ！

以上がMySQL のインデックスとは何ですか?インデックスストレージモデルの簡単な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。