mysql インデックスの基本的な実装原則

MySQL インデックスの背後にあるデータ構造とアルゴリズム原則

1. 定義

インデックス定義: インデックス (インデックス) は、MySQL がデータを効率的に取得するのに役立つデータ構造です。
本質: インデックスはデータ構造です。

2. B ツリー

m 次の B ツリーは次の条件を満たします:
1. 各ノードは最大 m 個のサブツリーを持つことができます。
2. ルート ノードには少なくとも 2 つのノードしかありません (または、極端な場合には、ツリーにはルート ノードが 1 つだけあります。単細胞生物はルート、リーフ、およびツリーです)。
3. 非ルートおよび非リーフ ノードには少なくとも Ceil (m/2) のサブツリーが必要です (Ceil は 5 次の B ツリーなどの切り上げを意味し、各ノードには少なくとも 3 つのサブツリーがあります)少なくとも 3 つのフォーク)。
4. 非リーフノードの情報には [n,A0,K1,A1,K2,A2,...,Kn,An] が含まれます。n はノードに保存されているキーワードの数を表し、K はキーワードを表します。 Ｋｉ＜Ｋｉ＋１、Ａはサブツリーのルートノードへのポインタである。
5. ルートからリーフまでの各パスは同じ長さです (リーフ ノードは同じレイヤーにあります)

1. キーワード セットはツリー全体に分散されます。キーワードは 1 つのノードにのみ表示されます。

4. ノード内のキーは、左から右に向かって順番に配置されます。 ;

6. すべての葉ノードの深さは同じであり、木の高さ h に等しい。

B-Tree の検索アルゴリズムの疑似コードは次のとおりです。

3. B+Tree

B+Tree と B-Tree の違いは次のとおりです。ツリーの非リーフ ノードはデータを格納せず、キーのみを格納します。

3. 各リーフ ノードには隣接するリーフ ノードへのポインタが含まれ、連続アクセス ポインタを持つ B+ ツリーにより間隔検索が向上します。機能。 ;

4. 非リーフ ノードはインデックス部分と見なされ、ノードにはそのサブツリー (ルート ノード) の最大 (または最小) キーワードのみが含まれます。

4. B/B+ ツリーのパフォーマンス分析。インデックス


基本: ディスク I/O の数を使用してインデックス構造の品質を評価します
メイン メモリとディスクはページ単位でデータを交換するため、ノードのサイズが 1 ページに等しくなるように設定します。完全にロードされた I/O が 1 つ必要です。

B ツリーの定義によれば、取得には一度に最大 h 個のノードにアクセスする必要があることがわかります

漸近複雑さ: O(h)=O(logdN) dmax=floor(pagesize/(keysize+ datasize+pointsize)) 一般的な実用的なアプリケーションでは、出次数 d は非常に大きな数で、通常は 100 を超えます。そのため、h は非常に小さくなります (通常は 3 以下で、レイヤー 3 は約 100 万のデータを保存できます)

B-Tree での取得には最大でも h-1 の I/O が必要です (ルート ノードはメモリ内に常駐します)

B+Tree のノードにはデータ フィールドが含まれていないため、出次数 d は大きくなり、h は小さくなります、I/O の数が少なく、効率が高いため、B+Tree は外部メモリのインデックスに適しています。


5. MySQL インデックスの実装

1. MyISAM エンジンは、インデックス構造として B+Tree を使用します。
MyISAM プライマリ インデックスとの間に構造的な違いはありません。プライマリ インデックスには一意のキーが必要ですが、補助インデックスのキーは繰り返し可能です。InnoDB データ ファイル自体はインデックス ファイルであり、リーフ ノードには完全なデータ レコードが含まれます。インデックスはクラスター化インデックスと呼ばれます。
InnoDB のデータ ファイル自体は主キーによって集約されるため、InnoDB ではテーブルに主キーが必要です (MyISAM には必要ありません)。明示的に指定されていない場合、MySQL システムはデータ レコードを一意に識別できる列を自動的に選択します。そうでない場合、MySQL システムはデータ レコードを一意に識別できるカラムを主キーとして自動的に選択します。そのようなカラムが存在する場合、MySQL は InnoDB テーブルの主キーとして暗黙的なフィールドを自動的に生成します。

InnoDB の補助インデックス データ フィールドには、アドレスの代わりに、対応するレコードの主キーの値が格納されます。

補助インデックスの検索では、インデックスを 2 回取得する必要があります。最初に補助インデックスを取得して主キーを取得し、次に使用します。プライマリ インデックス内のレコードを取得するためのプライマリ キー 3. ページ分割の問題

プライマリ キーが単調増加する場合、ページがいっぱいになると、新しいレコードが順番にページに挿入されます。

書き込みの順序が正しくない場合、InnoDB は新しい行にスペースを割り当てるためにページ分割を頻繁に行うことができません。ページ分割により大量のデータが移動されるため、挿入には 1 ページではなく少なくとも 3 ページの変更が必要になります。

ページが頻繁に分割されると、ページがまばらになり、不規則に埋められるため、最終的にはデータが断片化します。

6. まとめ

さまざまなストレージエンジンのインデックス実装方法を理解することは、インデックスの正しい使用と最適化に非常に役立ちます

1. 主キーとして長すぎるフィールドを使用することが推奨されないのはなぜですか?

2. 主キーとして自動インクリメントフィールドを選択する理由は何ですか?

3. 頻繁に更新されるフィールドにインデックスを付けることが推奨されないのはなぜですか?

4. 高度に差別化された列をインデックスとして選択する理由は何ですか?区別の式は count(distinctcol)/count(*) です

5. 可能な限りカバーインデックスを使用します

7. LIMIT ページングクエリを最適化します

SELECT * FROM table  where condition LIMIT offset , rows ;

上記の SQL ステートメントの実装メカニズムは次のとおりです。
1. 「table」テーブルから offset+rows 行レコードを読み取ります。
2. 前のオフセット行レコードを破棄し、次の行レコードを最終結果として返します。
対象となるインデックス:

select  a.id, sid, parent_s_id from cashpool_account_relationship a join (select id from cashpool_account_relationship LIMIT 1000000,10)b on a.id = b.id;
select  id, sid, parent_s_id from cashpool_account_relationship where id >=(select id from cashpool_account_relationship LIMIT 1000000,1) LIMIT 10;

8. Q&A

1. InnoDB はハッシュ インデックスをサポートしていますか? --Ma Xin
InnoDB はハッシュ インデックスをサポートしますが、サポートするハッシュ インデックスは適応型であり、InnoDB ストレージ エンジンはテーブルの使用状況に基づいてテーブルのハッシュ インデックスを自動的に生成し、ハッシュの生成に人間の介入は許可されません。テーブル内のインデックス。
2. InnoDB の主キー インデックスのリーフ ノードには、完全なデータ レコードが含まれていますか? --Xu Caihou
1)。 Innodb エンジンでは、主キー インデックスのリーフ ノードにレコード データが含まれており、主キー インデックス ファイルがデータ ファイルです。
2). tables テーブルでカウントされる data_length データは主キー インデックスのサイズであり、index_length はこのテーブル内のすべての補助インデックス (セカンダリ インデックス) のカウントされたサイズです。

以上がmysql インデックスの基本的な実装原則の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。