MySQL Innodb インデックス メカニズムの詳細な紹介

MySQL Innodb インデックス メカニズムの詳細な紹介

1. インデックスとは何ですか?

インデックスは、ストレージ エンジンがレコードをすばやく検索するために使用するデータ構造です。

2. インデックスにはどのようなデータ構造がありますか?

  • 順次検索構造: この検索効率は非常に低く、複雑さは O(n) です。データ量が多い場合、クエリの効率は非常に低くなります。
  • 順序付けられたデータ配置: バイナリ検索はハーフ検索とも呼ばれます。

一度比較すると、検索範囲が半分に減ります。 MySQL のデータは順序付けられたシーケンスではありません。

  • 二分探索木: 左のサブツリーのキー値は常に​​ルートのキー値よりも小さく、右のサブツリーのキー値は常に​​ルートのキー値よりも大きくなります。順序付きトラバーサルによって得られたシーケンスは順序付けられたシーケンスですが、バイナリ検索ツリーが適切に構築されていない場合は、順次検索と変わりません。

  • バランスのとれた二分木: 二分探索木のバランスをとる必要がある場合は、バランスのとれた二分木が導出されます。バランスのとれた二分木は、まず二分探索木の定義を満たす必要があり、次に、任意のノードの 2 つのサブツリー間の高さの最大差が 1 である必要があります。明らかに、上記のツリーはバランスの取れた二分木ではありません。バランスの取れた二分木の例は次のとおりです。

バランスのとれたバイナリ検索ツリーの時間計算量は O(logN) です。クエリ速度は確かに非常に高速ですが、バランスのとれたバイナリツリーを維持するためのコストも非常に高くなります。通常、挿入または更新後にバランスをとるには、1 回以上の左回転と右回転が必要です。

  • B ツリー: B ツリーとバランス バイナリ ツリーの違いは、B ツリーがマルチウェイ ツリー (バランス マルチウェイ検索ツリーとも呼ばれる) であることです。
  1. ルート ノードには少なくとも 2 つの子ノード (各ノードには昇順に配置された M-1 個のキーがあります) があり、他のノードには少なくとも M/2 個の子ノードがあります。
  2. リーフノードはすべて同じレイヤー上にあります。
  • B+ ツリー

B+ ツリーは B ツリーの変種であり、B ツリーとインデックス シーケンシャル アクセス メソッドから進化したものです (B ツリーは実際にはほとんど使用されません)。
B+ ツリーは、ディスクやその他の直接ストレージ補助デバイス用に設計されたバランス検索ツリーです。
B+ツリーでは、すべてのレコードノードがキー値の順序で同じレイヤーのリーフノードに配置され、リーフノードポインタによって接続されます。
すべてのクエリはリーフ ノードを見つける必要があり、クエリのパフォーマンスは安定しています。
すべてのリーフ ノードは、範囲クエリを容易にするために順序付けられたリンク リストを形成します。各リーフノードには隣接するリーフノードへのポインタが格納され、リーフノード自体はキーワードのサイズに応じて昇順にリンクされます(双方向リンクリスト)

3. Innodb がインデックスとして B+ ツリーを使用するのはなぜですか?

  1. システムは、ディスクのブロック読み取り特性を効果的に利用して、同じディスク ブロックを読み取りながらできるだけ多くのインデックス データをロードし、インデックス ヒット効率を向上させて、ディスク IO 読み取り回数を削減します (局所性原則とディスク事前読み取り)。
  2. B+ ツリーのディスク読み取りおよび書き込みコストは低くなります。B+ ツリーの内部ノードにはキーワードの特定の情報へのポインタがないため (リーフ ノードのみがそれを格納)、その内部ノードは B ツリーよりも小さくなります。同じ内部ノードのすべてのキーワードが同じディスク ブロックに格納されている場合、ディスク ブロックはより多くのキーワードを収容でき、メモリ内で一度に検索する必要があるキーワードが増えるため、相対的な IO 読み取りおよび書き込み時間が短縮されます。
  3. B+ツリーのクエリ効率はより安定しています。非終端点は、最終的にファイルの内容を指すノードではないため、リーフ ノード内のキーワードのインデックスにすぎません。したがって、キーワード検索では、ルート ノードからリーフ ノードへのパスをたどる必要があります。すべてのキーワード クエリのパスの長さは同じであるため、各データのクエリ効率は同等になります。
  4. B+ ツリーは範囲クエリをサポートしますが、B ツリーはサポートしません。

4. インデックス分類

ストレージ構造による分類: BTreeインデックス、ハッシュインデックス、フルテキストインデックス

アプリケーションからの分類: 主キーインデックス、ユニークインデックス、複合インデックス

物理ストレージの観点から:クラスター化インデックスと非クラスター化インデックス(補助インデックス)

クラスター化インデックスと非クラスター化インデックスとは何かについて説明します。

  • クラスター化インデックス

各テーブルの主キーに応じて B+ ツリーが構築され、テーブル全体の行レコードデータがリーフ ノードに格納されます。クラスター化インデックスのリーフ ノードはデータ ページとも呼ばれ、各データ ページは二重リンク リストを通じてリンクされます。

クラスター化インデックスは、主キーのソート検索や範囲検索に非常に高速です。

  • 補助索引

インデックス列の格納に加えて、リーフ ノードへのポインタも格納されます。

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

以下もご興味があるかもしれません:
  • MySQL Innodbの主な機能挿入バッファ
  • MySQL InnoDB ストレージエンジンのメモリ管理の詳細な説明
  • MySQL InnoDB ReplicaSet の簡単な紹介
  • MySQL InnoDB トランザクション ロック ソースコード分析
  • MySQLのInnoDBストレージエンジンにおけるさまざまなロックの詳細な説明
  • MySQL ストレージ エンジン InnoDB と MyISAM
  • MySQL の innoDB でファントム リードを解決する方法

<<:  閲覧時に作成されたWebページの下部にある余分な空白スペースを削除する方法

>>:  HTMLウェブページテーブル構造化マークアップの応用に関する簡単な説明

推薦する

Win10 64ビットMySQL8.0のダウンロードとインストールのチュートリアル図

公式サイトから MySQL をダウンロードしてインストールし、クライアントにログインするにはどうすれ...

Ubuntu ブート自動起動サービス設定

Ubuntu でサービスを作成し、自動的に起動する方法: 1. [/lib/systemd/syst...

MySQLコンテナ間のレプリケーション構成例の詳細な説明

背景先週、会社で MySQL レプリケーションのトレーニングを受けたので、今週末は学んだことを実践す...

MySQLデータ損失の原因と解決策

目次序文問題の説明原因分析拡大する総括する序文最近、データの欠落やデータの損失に関するフィードバック...

VMware 仮想マシンのインストール Linux システムのグラフィック チュートリアル

この記事では、LinuxシステムのVMwareインストールの具体的な手順を参考までに紹介します。具体...

Swiper.jsプラグインを使用すると、カルーセル画像を非常に簡単に実装できます。

Swiper は、携帯電話やタブレットなどのモバイル端末向けに設計された、純粋な JavaScri...

MySQL複合インデックスの詳細な研究

複合インデックス (結合インデックスとも呼ばれます) は、複数の列に対して作成されるインデックスです...

HBuilderX で Tomcat 外部サーバーを設定して、JSP インターフェイスを表示および編集する方法の詳細な説明

1. 最初の方法は、ローカルのTomcatを起動してJSPを表示することです。 tomcatのweb...

Mysql は非集計列を選択できません

1. はじめに最近ブログをアップグレードし、記事ページの下部に前の記事と次の記事に直接ジャンプできる...

ネイティブ js はカスタム スクロール バー コンポーネントを実装します

この記事の例では、カスタムスクロールバーコンポーネントを実装するためのjsの具体的なコードを参考まで...

MySQL マスタースレーブレプリケーションの遅延の原因と解決策

目次レプリケーション ロジックの簡単な概要:遅延の原因と解決策〇メインデータベースへの頻繁なDMLリ...

Linux システムで Vim を使用してリモート ファイルを読み書きするコマンドの詳細な説明

vim の動作モードを設定する (一時的) :set (モード情報) :set nu — 行番号を表...

docker を使用してシンプルな C/C++ プログラムをデプロイする方法

1. まずhello-world.cppファイルを作成しますプログラムコードは次のとおりです。 #i...

オペレーターが知っておくべき 18 個の Nginx プロキシ キャッシュ構成のヒント (どれを知っていますか?)

アプリケーションや Web サイトのパフォーマンスが成功の重要な要素であることは誰もが知っています。...

Centos7 ベースの Nginx Web サイト サーバーの構築の詳細説明 (仮想 Web ホストの構成を含む)

1. Nginx サービス基盤Nginx (エンジン x) は、パフォーマンスの最適化のために特別...