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をアップグレードするとシステム異常(起動できない)になる場合の解決方法

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

推薦する

nginx.conf ファイルの構文強調表示とフォーマット設定には nginx.vim ツールを使用します。

私はtengineを使用しています。インストールディレクトリは/usr/local/tengineで...

フロントエンドの vue+express ファイルのアップロードとダウンロードの例

新しいserver.jsを作成する糸初期化 -y 糸を追加エクスプレスノードモン -D var ex...

Dockerを使用してMySQL 8.0をデプロイする方法の例

1. 公式サイトを参照してdockerをインストールする2. MySQLイメージをプルします(デフォ...

MySQL は information_schema オブジェクトの付与をバイパスし、ERROR 1044 (4200) エラーを報告します

この質問は、MySQL の権限に関する WeChat グループのネットユーザー間の議論です。次のよう...

JS を使用してファイルを操作する (FileReader は --node の fs を読み取ります)

目次JS はファイルを読み取る FileReader書類イベントとメソッド基本的な使い方イベント処理...

CentOS 7.5 に Docker をインストールする詳細なチュートリアル

Docker入門Docker は、アプリケーションをより速く配信するのに役立つオープンソースのコンテ...

MySQL8 ベースの docker-compose デプロイメント プロジェクトの実装

1. まず、次のパスに従って対応するフォルダを作成します。 ローカルのdockerでmysqlを実行...

JavaScript のよりエレガントなエラー処理方法 async await

目次背景なぜエラー処理が必要なのでしょうか? async await より適切なエラー処理まとめ要約...

Vmvare 仮想マシンを使用して Ubuntu のルート ディレクトリをパーティション分割する方法の紹介

目次序文根拠手順1. CDから仮想マシンを起動する2. GPartedツールを使用してパーティション...

Vant Uploaderは1枚以上の写真をアップロードするコンポーネントを実装します

この記事では、1枚以上の写真をアップロードするためのVant Uploaderコンポーネントを紹介し...

MySQL サーバー ログイン エラー ERROR 1820 (HY000) の解決方法

障害サイト: MySQL サーバーにログインし、どのコマンドを実行してもこのエラーが発生します my...

Vueバインディングクラスとバインディングインラインスタイルの実装方法

目次バインディングクラスインラインスタイルのバインディングバインディングクラス方法1:オブジェクト構...

トークン生成と検証を実装するミニプログラム

目次プロセスデモミニプログラムバックエンドインターフェースプロセス各リクエストインターフェースは検証...

Linux環境にJDK1.8をインストールする

目次1. インストール環境2. インストール手順ステップ1: インストールパッケージをダウンロードす...

Docker Consul コンテナ サービスの更新と見つかった問題の概要

目次1. コンテナサービスの更新とDockerコンサルの検出1. サービス登録と検出とは何ですか? ...