mysql インデックスの基本的な実装原則-mysql チュートリアル-php.cn

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

无忌哥哥

リリース： 2018-07-12 10:14:29

オリジナル

1491 人が閲覧しました

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 サイトの他の関連記事を参照してください。