はじめに
データベースの索引付けといえば、皆さんもよくご存じでしょうし、日常業務でもよく目にすることでしょう。最近では、関連する記事や書籍、コースをたくさん読んでいます。私はこの記事は確かにオンラインすべての神々ほど良いではありませんが、自分の一度の要約は、常にもっとしっかり覚えているを書いたものの、自分自身の記事を要約することにしました。これはまた、良い学習習慣であるべきで、他の人が美しい言葉を書くことは他の人のものであり、自分の言葉は、少なくとも彼らはそれを認識することができます走り書きであっても。
インデックスとは、クエリの効率を向上させるデータ構造のことです。辞書の目録のようなもので、何百ページもある辞書では、ある単語を素早く調べたいとき、一生懸命回しても当てになりません。
インデックス構造
結論
MySQLインデックスは一般的にハッシュテーブルまたはB+ツリーであり、人気のInnoDBエンジンはデフォルトでインデックスのデータ構造としてB+ツリーを使用します。
なぜハッシュテーブルを使わないのですか？
インデックス・データ構造としてB+木を使用する場合、データの一部へのアクセスや変更にかかる時間の複雑さはO(log n)ですが、これらの作業を行うインデックス構造としてハッシュ・テーブルを使用する場合、時間の複雑さはO(1)です。データの一部を検索したり、データの一部を変更したりするだけなら、ハッシュテーブルをインデックスとして使用することは確かに強力です！しかし、一般的なビジネスシステムはそう単純ではないでしょう。
ビジネス開発では、レンジクエリ、ソートクエリ、その他のニーズにしばしば遭遇します。この時、ハッシュテーブルインデックスはこれらのニーズを効率的に処理することができません。テーブルを掃引することでしかこれらの機能を実現できず、データベースの悪夢となるはずです。
MySQLはB+ツリーデータ構造を使用しています。非リーフノードにはキー値のみが格納され、リーフノードにはデータまたはプライマリキーが格納されます。キーはリーフノードに順番に格納されるため、レンジクエリやソートクエリなどが驚くほど簡単になります。
ハッシュ・テーブル・インデックスは単一カラムのデータを操作する場合には非常に効率的ですが、レンジ・クエリやソート・クエリが必要な場合には、明らかにB+ツリー・データ構造の方が適しています。ビジネス開発では、1行のデータだけを操作することは不可能です。総合的に考えると、B+木の方がインデックスデータ構造として適していると言えます。
ハッシュテーブルインデックスはレンジクエリをサポートしておらず、インデックスを使用してソートすることができません。また、ユニオンインデックスでは左端一致の原則をサポートしておらず、ハッシュの衝突が起こりやすいため、重複するキー値が多くなると効率がさらに低下します。
なぜB-treeを使わないのですか？
B+ツリーは、その非リーフノードにキーと値のみを格納しますが、Bツリーは、その非リーフノードにキーと値だけでなくデータも格納します。MySQLデータベースでは、データページのサイズは固定で、Innodbエンジンのデータページのデフォルトサイズは16KBです。クエリが実行される時、ディスク IO 回数は減少し、クエリの効率は速くなります。
B+木は、すべてのデータがリーフノードに格納され、キーの値によって順序付けされています。しかし、B-treeのデータは各ノードに散らばっています。範囲クエリやソートクエリを実行する場合、B-treeの効率はB+-treeに劣ります。
B+ ツリー検索処理
ディスク・ブロック1には、17個と35個のデータ・アイテム、およびP1、P2、P3ポインタが格納され、P1は17個未満のデータ・アイテムを持つディスク・ブロックを示し、P2は17個と35個の間のデータ・アイテムを示し、P3は35個以上のデータ・アイテムを示します。非リーフノードはデータを格納せず、検索方向を示すデータ項目のみを格納します。
各IOが1データ・ページ、つまり1ディスク・ブロックのサイズを読み取ることを知っています。データ項目29を見つけたい場合、まず最初のIOでディスクブロック1をメモリに読み込み、17 < 29 < 35を見つけ、次にP2ポインタを選んで2番目のIOでディスクブロック3をメモリに読み込み、26 < 29 < 30を見つけ、次にP2ポインタを選んでディスクブロック8をメモリに読み込み、メモリ内でバイセクション・ルックアップを行って29を見つけ、クエリを終了します。
Hはツリーの高さ、Mは各ディスクブロックのデータ項目数、Nはデータ項目の総数です。次の式から、データ量Nが一定であれば、Mが大きいほど対応するHが小さくなることがわかります。
Mはディスクブロックの大きさをデータ項目の大きさで割ったもので、ディスクブロックの大きさは一般に固定されているため、Mを大きくするためにデータ項目の大きさを小さくし、ツリーをより短く太くします。B+木が実データを非リーフノードではなくリーフノードに置くのはこのためです。実データを非リーフノードに置くと、ディスクブロックに格納されるデータ項目が大幅に減り、木が高くなるので、データを照会するときのIOの数が増えます。
B+ ツリーは通常どれくらいのデータを保存できますか？
ここではまず、B+ツリーの高さが2、つまりルートノードとリーフノードが複数あると仮定します。 レコード行のデータサイズが1KBだとすると、1つのリーフノードに含まれるレコード数は16KB÷1KB＝16個に相当します。
主キーIDがbigint型、長さが8バイト、ポインタサイズがInnoDBソースコードで6バイトに設定されていると仮定すると、合計14バイトのポインタを非リーフノードに格納することができます。つまり、高さ2のB+ツリーは、1170 * 16 = 18720個のデータを格納できることがわかります。
同じ原理によると、高さ3のB+ツリーは21902400個のデータを格納できることが計算できます。したがって、InnoDBでは、B+ツリーの高さは通常1～3レベルであり、数百万件のデータ保存に対応できます。データを検索する場合、1ページ検索は1IOを表します。そのため、主キーインデックスクエリは通常、データを検索するのに1～3回の論理IO操作しか必要としません。
結論
- ハッシュテーブルインデックスは、1行のデータに対して非常に高速に動作しますが、範囲クエリをサポートしていません、ソートにインデックスを使用することはできません、ユニオンインデックスの左端の一致の原則をサポートしていません。
- B-treeのデータは非リーフノードに格納される可能性があり、範囲クエリのために余分なランダムディスクIOが発生する可能性があります。また、実データは非リーフノードに格納されるため、同じケースでB-treeの高さはB+-treeの高さよりも確実に高くなります。これも効率向上にはつながりません。
- B+ツリーは、葉ノードに実データを格納することで、ツリーをより短く太くし、IO回数を減らし、効率を向上させます。
最後に
以上、MySQLのインデックス構造について勉強したメモでした。いろいろな神様の記事を読んでから、改めて自分の記事を書くと印象がぐっと深くなることがわかりました。古米の炒飯ですが、自分のための炒飯です。皆さん、もっともっと励ましてくださいね。
