MySQL Bツリーインデックスとインデックス最適化の概要についての簡単な説明

MySQL の MyISAM エンジンと InnoDB エンジンはどちらもデフォルトで B+ ツリー インデックスを使用します (クエリを実行すると「BTREE」と表示されます)。この記事では、次の 2 つの問題について説明します。

1. MySQL などの主流のデータベースが B+ ツリー インデックス構造を選択するのはなぜですか?
2. インデックス構造に基づいた一般的な MySQL インデックス最適化のアイデアを理解するにはどうすればよいでしょうか?

すべてのインデックスがメモリに収まらないのはなぜですか?

インデックス構造の選択は、データ量が大きい場合、インデックスをメモリに完全にロードできないという特性に基づいています。

なぜインデックス全体がメモリに収まらないのでしょうか?インデックスがツリー構造を使用して構成されていると仮定すると、簡単な見積もりは次のようになります。

1. 単一のインデックス ノードが 12 バイト、データ行が 1,000 万行、一意のインデックスがあると仮定すると、リーフ ノードは合計で約 100 MB を占め、ツリー全体は最大 200 MB を占めます。
2. 1 行のデータが 200B を占めると仮定すると、合計データはおよそ 2G を占めます。

インデックスがメモリに格納されていると仮定します。つまり、物理ディスクに 2G のデータが保存されるたびに 200MB のメモリが占​​有され、インデックス:データの占有率は約 1/10 になります。占有率が 1/10 というのは大きいと言えるのでしょうか?物理ディスクはメモリよりもはるかに安価です。16G のメモリと 1T のハードディスクを搭載したサーバーを例に挙げます。1T のハードディスクをいっぱいにしたい場合は、少なくとも 100G のメモリが必要であり、これは 16G よりもはるかに多くなります。

テーブルに複数のインデックス、結合インデックス、およびより小さなデータ行の占有率がある場合があることを考慮すると、実際の占有率は通常 1/10 より大きくなり、場合によっては 1/3 に達することもあります。インデックスベースのストレージ アーキテクチャでは、インデックスとデータの比率が高すぎるため、インデックスをメモリに完全にロードできません。

その他の構造上の問題

メモリにロードできないため、ディスク (または SSD) ストレージに依存する必要があります。メモリの読み取りおよび書き込み速度は、ディスクの数千倍です (特定の実装によって異なります)。したがって、中心的な問題は、「ディスクの読み取りと書き込みの回数をいかに減らすか」です。

まず、ページ テーブル メカニズムを考慮せずに、各読み取りと書き込みがディスクに直接行われると仮定します。

1. 線形構造: 平均読み取り/書き込み回数 O(n)
2. バイナリ検索木 (BST): 平均して O(log2(n)) 回の読み取り/書き込み。木が不均衡な場合、最悪の場合 O(n) 回の読み取り/書き込み。
3. 自己バランス型二分探索木（AVL）：BSTに基づく自己バランス型アルゴリズムを追加し、最大読み取り/書き込み時間はO(log2(n))
4. 赤黒木 (RBT): 最大読み取り/書き込み時間が O(log2(n)) の別の自己バランス検索木

BST、AVL、RBT は、読み取りおよび書き込み操作の数を O(n) から O(log2(n)) に最適化します。AVL と RBT は BST と比較して自己バランス機能を備えており、読み取りおよび書き込み操作の数を最大 O(log2(n)) に削減します。

自動増分主キーを使用すると、主キー自体が順序付けられ、ツリー構造の読み取りおよび書き込み回数をツリーの高さに合わせて最適化できます。ツリーの高さが低いほど、読み取りおよび書き込み回数が少なくなり、自己バランスによりツリー構造の安定性が確保されます。さらに最適化したい場合は、B ツリーと B+ ツリーを導入できます。

B ツリーはどのような問題を解決しますか?

多くの記事では、B ツリーを誤って B (縮小) ツリーと呼んでいますが、これは英語名の「B-Tree」の誤解である可能性があります (さらに悪いことに、B ツリーはバイナリ ツリーまたはバイナリ サーチ ツリーと呼ばれます)。特に B+ ツリーと話す場合。 B+ (プラス) ツリーがあれば、B- (マイナス) ツリーも必ず存在すると考えられます。実際、B+ ツリーの英語名は「B+-Tree」です。

メンテナンス操作を無視すると、B ツリーは、時間の複雑さが O(logm(n)) である「m 方向検索ツリー」(m はサブツリーの最大数) のようになります。ただし、B ツリーは、B ツリーの深さをおよそ log(ceil(m/2))(n) から logm(n) の間に維持する効率的でシンプルなメンテナンス操作で設計されており、ツリーの高さが大幅に削減されます。

もう一度、

時間の複雑さについては心配する必要はありません。単純なアルゴリズムとは異なり、ディスク IO 時間はより大きな要素です。読者は、B ツリーと AVL の時間計算量は同じであると推測できますが、B ツリーの方がレイヤーが少なく、ディスク IO 時間も少ないため、実際には B ツリーのパフォーマンスは AVL などのバイナリ ツリーよりも優れています。

バイナリ検索ツリーと同様に、各ノードには複数のキーとサブツリーが格納され、サブツリーとキーは順番に配置されます。

ページ テーブルのディレクトリは、外部メモリを拡張し、ディスクの読み取りと書き込みを高速化するためのものです。ページは通常 4K です (ディスク データ ブロックのサイズに等しい、inode とブロックの分析を参照)。オペレーティング システムは、毎回ページ単位でディスクからメモリにコンテンツをロードします (シーク コストを分散するため)。ページを変更した後、適切なタイミングでページをディスクに書き戻します。ページ テーブルの優れた特性を考慮すると、各ノードのサイズをページとほぼ等しくすることができ (m が非常に大きくなります)、読み込まれた各ページはノードを完全にカバーして次のレベルのサブツリーを選択できるようになります。サブツリーにも同じことが当てはまります。ページ テーブルの場合、AVL (または RBT) は 1 つのキーと 2 つのサブツリーを持つ B ツリーに相当します。論理的に隣接するノードは通常物理的に隣接していないため、4k ページが読み込まれると、ページ内のほとんどのスペースが無効なデータになります。

キーとサブツリー ノード ポインターがそれぞれ 4B を占めると仮定すると、B ツリー ノードの最大サイズは m * (4 + 4) = 8MB、ページ サイズは 4KB になります。すると、m = 4 * 1024 / 8m = 512、512 フォークの B ツリー、1000 万データ、最大深度は log(512/2)(10^7) = 3.02 ~= 4 になります。比較すると、AVLなどの二分木の深さはlog(2)(10^7) = 23.25 ~= 24となり、5倍以上の深さになります。ショック！ B ツリー インデックスの深さが非常に高いです。

さらに、B ツリーは局所性の原則に非常に適しています。キーが比較的小さい場合 (上記の 4B の自己増分キーなど)、ページ テーブルの利点に加えて、キャッシュによって事前読み取りをさらに高速化できます。美味しい〜

B+ ツリーはどのような問題を解決しますか?

Bツリーの残された問題

しかし、B ツリーを実際にデータベース インデックスに適用する場合、まだいくつかの問題が残ります。

1. 未配置のデータ行
2. 範囲クエリを処理できません

質問1

データ テーブル内のレコードには複数のフィールドがあります。主キーを見つけるだけでは不十分で、データ行を見つける必要もあります。解決策は3つあります。

1. キーに対応するデータ行 (複数行の場合もある) を子ノードに直接保存します。
2. データ行は個別に保存され、キーに対応するデータ行の位置を特定するためのフィールドがノードに追加されます。
3. キーとサブツリーの判断ロジックを変更して、サブツリーが前のキー以上で、次のキーより小さくなるようにします。最終的には、すべてのアクセスがリーフ ノードに発生します。リーフ ノードには、データ行またはデータ行の場所が直接格納されます。

ソリューション 1 は直接渡されます。データ行を保存すると、ページ内のサブツリーの数が減り、m が減少し、ツリーの高さが増加します。

ソリューション 2 では、ノードにフィールドが追加されます。4B ポインターであると仮定すると、新しい m = 4 * 1024 / 12m = 341.33 ~= 341 となり、最大深度は log(341/2)(10^7) = 3.14 ~= 4 となります。

ノードmとソリューション3の深さは変更されませんが、時間計算量は安定してO(logm(n))になります。

オプション3を検討できます。

質問2

実際のビジネスでは、範囲クエリの頻度が非常に高くなります。B ツリーでは 1 つのインデックス位置 (複数の行に対応する場合があります) しか見つけることができないため、範囲クエリの処理が困難になります。マイナーチェンジは2つ

プラン：

1. 変更はありません。検索するときは、最初に左の境界を見つけ、次に右の境界を見つけ、最後に DFS (または BFS) を使用して左の境界と右の境界の間のノードをトラバースします。
2. 「問題 1 - 解決方法 3」に基づき、すべてのデータ行はリーフ ノードに格納されるため、B ツリーのリーフ ノードも順序付けられます。主キーの順序で現在のリーフ ノードの次のリーフ ノードを指すポインタを追加できます。クエリを実行するときは、最初に左の境界をチェックし、次に右の境界をチェックし、左の境界から境界のある境界まで直線的に移動してください。

一見すると、ソリューション 1 の方がソリューション 2 よりも優れているように見えます。時間の計算量と定数項は同じであり、ソリューション 1 を変更する必要はありません。ただし、局所性の原則を忘れないでください。ノードがデータ行を格納するか、データ行の場所を格納するかに関係なく、ソリューション 2 の利点は、ページ テーブルとキャッシュを使用して次のノードの情報を事前に読み取ることができることです。ただし、ソリューション 1 では、ノードは論理的には隣接しているものの、物理的には分離されているという欠点があります。

B+ Treeのご紹介

要約すると、問題 1 のソリューション 2 と問題 2 のソリューション 1 は 1 つのソリューションに統合できます (B ツリー インデックスに基づく)。また、問題 1 のソリューション 3 と問題 2 のソリューション 2 は 1 つのソリューションに統合できます (B+ ツリー インデックスに基づく)。実際、一部のデータベースとファイル システムでは B ツリーが使用され、他のデータベースとファイル システムでは B+ ツリーが使用されます。

一部のサルにはまだ理解されていない理由により、MySQL を含む主流のデータベースは主に B+ ツリーを選択します。今すぐ：

主な変更点は次のとおりです。

1. キーとサブツリーの組織ロジックを変更して、インデックスアクセスがリーフノードに落ちるようにします。
2. リーフノードを順番に連結する（範囲クエリを簡単にするため）

BツリーとB+ツリーの追加、削除、チェックのプロセス

B ツリー、B+ ツリー、B* ツリーから R ツリーまでの B ツリーの追加と削除のプロセスは、「6. B ツリーの挿入と削除の操作」のセクションで一時的に参照できます。B+ ツリーの追加と削除についても同様です。ここでは詳細には触れません。

MySQL インデックスの最適化

B+ ツリーの特性に基づいて、さまざまな一般的な MySQL インデックス最適化のアイデアを簡単に理解できます。

今のところ、異なるエンジン間の違いについては考慮しないことにしましょう。

自動増分キーを主キーとして使用することを推奨

前回の分析では、4B の自動インクリメント キーがインデックスとして使用されると仮定すると、m は 512 に達し、レイヤーの高さは 3 のみになります。自動増分キーを使用すると、次の 2 つの利点があります。

自動インクリメント キーは通常、int などの整数型であり、キーは比較的コンパクトなので、m は非常に大きくなり、インデックスが占めるスペースは少なくなります。最も極端な例では、50B の varchar (長さを含む) が使用される場合、m = 4 * 1024 / 54m = 75.85 ~= 76 となり、最大深度は log(76/2)(10^7) = 4.43 ~= 5 となります。これにキャッシュ ミスと文字列比較のコストが加わり、時間コストは大幅に増加します。同時に、キーは 4B から 50B に増加し、インデックス ツリー全体が占めるスペースも恐ろしく増加します (セカンダリ インデックスがプライマリ キーを使用してデータ行を検索する場合、スペースの増加はさらに深刻になります)。

自己増分の性質により、新しいデータ行の挿入要求は必然的にインデックス ツリーの右端に落ち、ノード分割の頻度は低くなります。理想的には、インデックス ツリーは「フル」状態に到達できます。インデックス ツリーがいっぱいになると、レイヤーの高さが低くなり、ノードを削除するときにノードがマージされる頻度も低くなります。

最適化の経験:

かつて、コンテナ ID を保存するために、varchar(100) 列を主キーとして使用していました。3、4 日後、100G のデータベースがいっぱいになりました。DBA の女性は電子メールで私に対する軽蔑を表明しました。 。 。その後、自動インクリメント列が主キーとして追加され、containerId が一意のセカンダリ インデックスとして追加されました。時間とスペースの最適化効果は非常に顕著でした。

左端のプレフィックス一致

インデックスは、単一の列 (a) のように単純なものから、複数の列 (a、b、c、d) のように複雑なもの (つまり、結合インデックス) にすることもできます。結合インデックスの場合、キーも複数の列で構成されます。同時に、インデックスはキーが存在するかどうか (等価性) を調べるためにのみ使用できます。範囲クエリ (>、<、between、左一致など) に遭遇すると、それ以上の一致は不可能になり、その後は線形検索に退化します。したがって、列が配置される順序によって、インデックスにヒットできる列の数が決まります。

インデックス (a、b、c、d) があり、クエリ条件が a = 1 かつ b = 2 かつ c > 3 かつ d = 4 の場合、各ノードで a、b、c が順番にヒットしますが、d はヒットしません。これが左端のプレフィックス一致の原則です。

=、自動最適化順序

=、in などの順序を考慮する必要はありません。MySQL は、これらの条件の順序を自動的に最適化して、できるだけ多くのインデックス列と一致するようにします。

インデックス (a、b、c、d) がある場合、クエリ条件 c > 3 かつ b = 2 かつ a = 1 かつ d < 4 かつ a = 1 かつ c > 3 かつ b = 2 かつ d < 4 はすべて可能です。MySQL は自動的に a = 1 かつ b = 2 かつ c > 3 かつ d < 4 に最適化され、a、b、c が順番にヒットします。

インデックス列は計算に使用できません

計算にインデックス列が含まれるクエリ条件は、from_unixtime(create_time) = '2014-05-29' など、インデックスに適していません (またはインデックスを使用できません)。

理由は簡単です。ノード内の対応するキーを見つけるにはどうすればよいでしょうか?線形スキャンを実行する場合、計算を毎回再計算する必要があり、コストがかかりすぎます。バイナリ検索を実行する場合は、from_unixtime メソッドのサイズ関係を決定する必要があります。

したがって、インデックス列は計算に参加できません。上記の from_unixtime(create_time) = '2014-05-29' ステートメントは、create_time = unix_timestamp('2014-05-29') と記述する必要があります。

拡張できる場合は新しいインデックスを作成しないでください

すでにインデックス (a) があり、インデックス (a, b) を作成したい場合は、インデックス (a) をインデックス (a, b) に変更してみてください。

新しいインデックスを作成するコストは簡単に理解できます。インデックス (a) がインデックス (a, b) に変更された場合、MySQL は分割、マージなどによってインデックス a の B+ ツリーをインデックス (a, b) に直接変更できます。

プレフィックス包含関係を持つインデックスを作成する必要はありません

すでにインデックス (a, b) がある場合は、インデックス (a) を作成する必要はありませんが、必要な場合は、インデックス (b) の作成を検討する必要があります。

識別力の高い列をインデックスとして選択する

とてもわかりやすいです。たとえば、性別をインデックスとして使用した場合、インデックスは 1,000 万行のデータを 2 つの部分 (男性 500 万行と女性 500 万行など) に分割することしかできず、インデックスはほとんど効果がありません。

識別の式は count(distinct <col>) / count(*) で、一意のフィールドの割合を示します。割合が大きいほど、識別が優れています。一意のキーの識別度は 1 ですが、一部のステータスおよび性別フィールドはビッグ データに対して 0 に近い識別度を持つ場合があります。

この値を決定するのは困難です。通常、結合する必要があるフィールドは 0.1 を超える必要があり、平均して 1 回のスキャンに 10 件のレコードが必要になります。

以上がこの記事の全内容です。皆様の勉強のお役に立てれば幸いです。また、123WORDPRESS.COM を応援していただければ幸いです。