MySQL インデックス データ構造の詳細な分析

MySQL インデックス データ構造の詳細な分析

概要

インデックスは、データベース テーブル内の 1 つ以上の列の値を並べ替える構造です。インデックスを使用すると、データベース テーブル内の特定の情報にすばやくアクセスできます。

インデックスデータ構造

バイナリツリー

二分木は、木内のノードの次数が 2 以下である順序付き木です。これは最も単純で最も重要な木です。二分木の再帰的な定義は次のとおりです。二分木は空の木、またはルート ノードとルートの交差しない 2 つの左サブツリーと右サブツリーで構成される空でない木です。左サブツリーと右サブツリーも二分木です。

配列{1,2,3,4,5}の場合、データ構造はリンクリストになります。

特徴:

  • 親ノードの下に 2 つの子ノードがあります。
  • 右ノードのデータは左ノードのデータよりも大きいです。


バイナリツリー.png

赤黒木

赤黒木は、コンピュータ サイエンスで数値などのデータ ブロックを整理するために使用される構造であるバイナリ ツリーの特定の種類です。二分探索木が赤黒木である場合、そのサブツリーのいずれも赤黒木でなければなりません。

赤黒木は、バランスのとれた二分探索木の変形です。左と右のサブツリーの高さの差が 1 より大きい場合があるため、赤黒木は厳密にバランスのとれた二分木 (AVL) ではありませんが、バランスをとるコストは低く、平均的な統計的パフォーマンスは AVL よりも強力です。

各赤黒木は二分ソート木であるため、赤黒木を検索する際には、通常の二分ソート木に適用される検索アルゴリズムを使用でき、検索プロセス中に色情報は必要ありません。

赤黒木のデータ構造は次のとおりです。


赤黒木データ構造.png

特徴:

  • 赤黒木は、各ノードに赤または黒の色属性がある二分探索木です。
  • ノードは赤または黒です。
  • ルートノードは黒です。
  • 葉っぱはすべて黒です。 (葉はNILノードです)
  • すべての赤いノードには 2 つの黒い子ノードがあります。 (各リーフからルートまでのパス上に連続する 2 つの赤いノードが存在することはできません)
  • 任意のノードから各リーフへのすべてのパスには、同じ数の黒いノードが含まれます。
  • これらの制約は、赤黒木の重要な特性、つまりルートからリーフまでの最長パスが最短パスの 2 倍を超えないことを強制します。結果、ほぼバランスの取れた木が完成します。値の挿入、削除、検索などの操作には、最悪の場合、ツリーの高さに比例した時間が必要となるため、高さのこの理論的な上限により、通常の二分探索木とは異なり、赤黒木は最悪の場合でも効率的になります。
  • パス上に連続する 2 つの赤いノードが存在することはできないため、この結果を保証するのはプロパティ 4 です。最短のパスではノードはすべて黒色になり、最長のパスでは赤と黒のノードが交互に現れます。特性 5 により、すべての最長パスには同じ数の黒いノードがあるため、どのパスも他のパスの 2 倍以上長くなることはないことがわかります。
  • 赤黒木は特殊な二分探索木であるため、赤黒木に対する読み取り専用操作は通常の二分探索木に対する操作と同じです。

Bツリー

  • リーフノードは同じ深さを持ち、リーフノードポインタは空です
  • すべての要素はユニークです
  • ノード内のデータ インデックスは、左から右へ昇順に並べられます。

B ツリー データ構造.png

B+ツリー

  • 非リーフノードはデータを保存せず、インデックスのみ(冗長性)を保存し、より多くのインデックスを保存できます。
  • リーフノードにはすべてのインデックスフィールドが含まれます
  • リーフノードはポインタでリンクされており、区間アクセスのパフォーマンスが向上します(範囲検索の効率が向上します)。

B+ ツリーデータ構造.png

キーワード: ノード内の順序、リーフノードのポインタリンク、非リーフノードのストレージインデックス (冗長)

mysql インデックスのデータ ページのサイズを照会します。

mysql> 'Innodb_page_size' のようなグローバル ステータスを表示します。
+------------------+-------+
| 変数名 | 値 |
+------------------+-------+
| Innodb_ページサイズ | 16384 |
+------------------+-------+

なぜ16kbに設定するのですか?

ハッシュ

  • インデックス キーのハッシュ計算により、データ ストレージの場所を特定できます。
  • 多くの場合、ハッシュ インデックスは B+ ツリー インデックスよりも効率的です。
  • 「=」のみがサポートされています。「in」は範囲クエリをサポートしていません。
  • ハッシュ競合の問題が発生しています


ハッシュデータ構造.png

索引

InnoDB インデックスの実装 (クラスタリング)

テーブルデータファイル自体はB+Treeで編成されたインデックス構造ファイルである。

クラスター化インデックス - リーフノードには完全なデータレコードが含まれます

InnoDb テーブルに主キーが必要なのはなぜですか? また、整数の自動増分主キーを使用することをお勧めしますか?

  • インデックスが設定されていない場合、MySQL は、そのような列が見つからないときに、一意のデータを持つ列を主キー インデックスとして選択します。私が行うことは、rowid のような隠し列を作成することです。
  • テーブル データ ファイルは B+Tree データ構造に従って維持され、リーフ ノードは行のデータを維持します。したがって、主キーが存在する必要があります。
  • 整数は B+ ツリー ソートに便利です。整数が自己増加型の場合、多数のツリー バランス操作を必要とせずに、データ構造をより高速かつ連続的に格納できます。

非主キー インデックス構造のリーフ ノードに主キー値が格納されるのはなぜですか?

  • 一貫性: 主キーインデックスを最初に成功させ、次に非主キーインデックスの関係を更新します。
  • ストレージスペースを節約します。

主キーインデックス図:


InnoDB インデックスの実装.png

非主キーインデックス図

クエリが name = Alice に基づいている場合:

  1. 非主キー インデックスを使用してクエリを実行し、クエリ後の情報 (Alice、18) を取得します。実はこれも非クラスタ化インデックスです
  2. 次に、バックテーブル クエリを実行し、主キーを使用してテーブルを再度クエリします。

2 つのデータ ファイル:

.frmは主にテーブル構造情報を保存します

.ibdは主にインデックスとデータを保存します

MyISAM インデックス ファイル (非クラスター化)

インデックスファイルとデータファイルは別々です(非クラスター化)


MyISAM ストレージ エンジン インデックス.png

3 つのデータ ファイル:

.frm データ構造ファイル

.mydファイルは主にデータを保存するために使用されます

.myiファイルは主にインデックス情報を保存します

クラスター化インデックスと非クラスター化インデックス

特徴:

クラスタリング/非クラスタリングは、主にインデックス ファイルがデータ ファイルと一緒にあるかどうかを指します。

クエリの効率性という点では、クラスター化インデックスはファイル間でクエリを行わないため、クエリが高速になります。

ジョイント/複合インデックス

複数のフィールドが共通のインデックスに整理される


結合されたインデックス.png

なぜこのように左端接頭辞の原則が使用されるのでしょうか?

インデックス化されたデータはソートされており、フィールドがスキップされている場合は使用できません。

例:

name = 'Jeff' かつ age = 22 の場合 -- インデックスにヒットします。 age = 30 かつ postatin='manager' の場合 -- インデックスにヒットしません。 postation = 'dev' の場合 -- インデックスにヒットしません。

参考文献

百度百科事典

要約する

これで、MySQL インデックス データ構造に関するこの記事は終了です。MySQL インデックス データ構造に関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。

以下もご興味があるかもしれません:
  • MySQLインデックス構造の詳細な分析
  • MySQLインデックストランザクションの詳細な分析
  • MySQL インデックスの長さ制限の原理の分析
  • MySQLインデックスの詳細な分析
  • MySQLインデックスの役割を分析する

<<:  Centos7でglibcをアップグレードするとシステム異常(起動できない)になる場合の解決方法

>>:  フレックスレイアウトを使用してページレイアウトを簡単に実装するためのサンプルコード

推薦する

ウェブのさまざまなフロントエンド印刷方法: CSS はウェブページの印刷スタイルを制御します

CSS は Web ページの印刷スタイルを制御します。 CSS を使用して印刷スタイルを制御します。...

JavaScript offsetParent のケーススタディ

1. offsetParentの定義: offsetParentは子要素に最も近い位置に配置された親...

グループ化されたクエリでのGROUP BYの使用とSQL実行順序の説明

SQL では、GROUP BY は SELECT の結果のデータをグループ化するために使用されます。...

JavaScriptでマクロを使用する方法

言語では、DSL を実装するためにマクロがよく使用されます。マクロを使用すると、開発者は JSX 構...

MySQLテーブルシャーディングとパーティショニングの具体的な実装方法

縦型テーブル垂直テーブル分割とは、多数の列を持つテーブルを複数のテーブルに分割することを意味します。...

Docker Nginxコンテナの制作と展開の実装方法

クイックスタート1. Docker Hubでnginxイメージを見つけるdocker 検索 ngin...

MySQL のデータの偶発的な削除の解決策と kill ステートメントの原則

mysql が誤ってデータを削除しました削除ステートメントを使用して誤ってデータ行を削除する誤ってデ...

マウスが画像のハイパーリンク上を通過するときに画像のサイズ(幅、高さ)を変更する CSS

マウスが画像の上を通過したときに画像のハイパーリンクを変更する方法:コードをコピーコードは次のとおり...

JavaScript ツールチェーンの不完全なガイド

目次概要静的型チェックコードスタイルチェック(Linter)パッケージマネージャーモジュールローダー...

dockerコンテナにvimをインストールするソリューション

目次物語の始まりvimをインストールし、hadoop-hive.envを編集します。不注意で回避しま...

ブラウザのキャッシュを防ぐために、js または css の後に ?v= バージョン番号を追加します。

コードをコピーコードは次のとおりです。 <span style="font-size...

MySQL テーブルの読み取り、書き込み、インデックス作成、その他の操作の SQL ステートメントの効率最適化の問題を分析します。

前回は、Explain 実行プランの表示、インデックスの分析など、MySQL での SQL クエリの...

スキニングを実現するネイティブJavaScript

ネイティブJavaScriptでスキニングを実装するための具体的なコードは参考までに。具体的な内容は...

高度な CSS の 3 つの方法を使用して複数行の省略を実装するサンプル コード

序文これは古くからの要望ですが、オンラインで解決策を探している人はまだ多く、特に検索結果の上位にラン...

js を使ってシンプルな虫眼鏡効果を実現

この記事の例では、参考までに簡単な虫眼鏡効果を実現するためのjsの具体的なコードを共有しています。具...