MySQLインデックスの基礎となるデータ構造の詳細

MySQLインデックスの基礎となるデータ構造の詳細

1. インデックスの種類

1. B+ツリー

なぜ B ツリーではなく B+ ツリーなのでしょうか?

まず、B ツリーと B+ ツリーの構造上の違いを見てみましょう。

Bツリー構造:

B+ツリー:

以下が見られます:

  • B ツリーでは各ノードにサテライト データ (データ テーブル内のデータ行) がありますが、B+ ツリーではリーフ ノードにのみサテライト データがあります。これは、同じサイズのディスクセクターの場合、B+ツリーはより多くのリーフノードを格納でき、必要なディスクIO時間が短くなることを意味します。また、B+ツリーの検索効率はより安定しており、Bツリーデータクエリの最速の時間計算量はO(1)であることを意味します。
  • B ツリーの各ノードは 1 回だけ表示され、B+ ツリーのすべてのノードはリーフ ノードに表示されます。 B+ ツリーのすべてのリーフ ノードは昇順のリンク リストを形成します。これは間隔範囲の検索に適していますが、B ツリーは適していません。

2. MyISAM と InnoDB の B+ ツリー インデックス実装 (クラスター化インデックスと非クラスター化インデックス) の違いは何ですか?

まず、クラスター化インデックスと非クラスター化インデックスを理解する必要があります。

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

クラスター化インデックスでは、リーフ ページに行のすべてのデータが含まれ、ノード ページにはインデックス列が含まれます。 InnoDB は主キーによってデータをクラスター化します。主キーが定義されていない場合は、代わりに一意の空でないインデックス列が選択されます。そのようなインデックスがない場合、InnoDB は暗黙的に主キーをクラスター化インデックスとして定義します。

クラスター化インデックスのデータ分布:

クラスター化インデックスには、主キー インデックスに加えて、セカンダリ インデックスもあります。セカンダリ インデックスのリーフ ノードには、「行ポインタ」ではなく、行への「ポインタ」として使用される主キー値が格納されます。つまり、セカンダリ インデックスを通じて行を検索する場合、ストレージ エンジンはセカンダリ インデックスのリーフ ノードを見つけて対応するプライマリ キー値を取得し、この値に基づいてクラスター化インデックス内の対応する行を検索する必要があります。これは、「テーブルに戻る」とも呼ばれます。もちろん、カバーリング インデックスやInnoDBのアダプティブ インデックスを使用してテーブルの繰り返しを回避し、このような繰り返し作業を減らすこともできます。

: クラスター化インデックスの各リーフ ノードには、完全なデータ行だけでなく、トランザクション ID、トランザクションのロールバック ポインター、および MVCC も含まれます。

3. 非クラスター化インデックス

非クラスター化インデックスの主キー インデックスとセカンダリ インデックスは構造に違いはなく、どちらもリーフ ノード上のデータの物理アドレスを指す「行ポインター」を格納します。

クラスター化インデックスの主キー インデックスとセカンダリ インデックス:

非クラスター化インデックスの主キー インデックスとセカンダリ インデックス:

4. クラスター化インデックスの利点と欠点

アドバンテージ:

関連データをまとめて保存します(たとえば、すべてのユーザーのメールをユーザーIDごとにグループ化します)。そうしないと、各データの読み取りでディスクIOが発生する可能性があります。
データ アクセスが高速化します。インデックスとデータを同じ B+ ツリーに格納します。通常、クラスター化インデックスからデータを取得する方が、非クラスター化インデックスからデータを取得するよりも高速です。カバーリング クエリを使用すると、ページ ノードの主キー値を直接使用できます。

欠点:

すべてのデータをメモリに格納できる場合、シーケンシャル アクセスは不要になり、クラスター化インデックスの利点はなくなります。挿入速度は挿入順序によって異なります。ランダム挿入はページ分割やページ ホールの原因になります。OPTIMIZE TABLE を使用してテーブルを再構築します。挿入、更新、削除のたびにインデックス変更のメンテナンスが必要になり、コストが非常に高くなります。参照行の主キー列がノードに含まれるため、セカンダリ インデックスが予想よりも大きくなる場合があります。

5. ハッシュインデックス

ハッシュ インデックスはハッシュ テーブルに基づいて実装されます。インデックスのすべての列と完全に一致するクエリのみが有効であるため、ハッシュ インデックスは等価値クエリに適しています。

具体的な実装:データの各行について、ストレージ エンジンはすべてのインデックス列のハッシュ コードを計算します。ハッシュ インデックスはすべてのハッシュ コードをインデックスに格納し、各データ行へのポインターをハッシュ テーブルに保存します。

MySQL では、 Memoryエンジンは B ツリー インデックスもサポートしていますが、ハッシュ インデックスを明示的にサポートしているのはMemoryエンジンだけです。

注:メモリ エンジンは、一意でないハッシュ インデックスをサポートします。競合を解決するには、同じハッシュ値を持つ複数のレコード ポインターをリンク リストの形式で保存します。

6. 適応ハッシュインデックス

InnoDB 、特定のインデックス値が非常に頻繁に使用されていることに気付くと、メモリ内に B+ ツリー インデックスに基づくハッシュ インデックスを作成します。これにより、B+ ツリー インデックスにも、高速なハッシュ検索など、ハッシュ インデックスのいくつかの利点が備わります。

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

以下もご興味があるかもしれません:
  • MySQLでテーブルインデックスを構築する方法
  • MySQL のインデックスとデータ テーブルを管理する方法
  • MySQLデータベースインデックスの詳細な紹介
  • MySQLデータベースインデックスの詳細な説明
  • MySQL データの最適化 - 多層インデックス
  • MySQL データベースのインデックスとトランザクション
  • MySQLテーブルのインデックス作成の原理の詳細な説明

<<:  HttpsページでBaiduシェアを使用するためのソリューション

>>: 

推薦する

MySQL のデータ型とスキーマの最適化の詳細な説明

現在、MySQL の最適化について学習しています。この記事では、データ型とスキーマの最適化について紹...

要素シャトルフレームのパフォーマンス最適化の実装

目次背景解決新しい質問高度な背景シャトル ボックスが大量のデータを処理すると、レンダリングされる D...

MySQLのクラスタモードでのgalera-clusterのデプロイメントの詳細説明

目次1: galera-clusterの紹介2. galera-clusterの仕組み3: Mari...

JS 非同期スタック トレース: await が Promise よりも優れている理由

概要async/await と Promise の基本的な違いは、await fn() は現在の関数...

Linux で MongoDB のリモート自動バックアップを実装する方法

序文古いプロジェクトを引き継ぐ苦労 - MongoDB クラスターの学習と構築に関する前回の記事を読...

HTML テーブル マークアップ チュートリアル (30): セルの暗い境界線の色属性 BORDERCOLORDARK

セルでは、暗い境界線の色を個別に定義できます。基本的な構文<TD ボーダーコロダーク=colo...

CentOS8.1 で Gitlab サーバーを構築するための詳細なチュートリアル

Gitlab と Github の違いについては、あまり説明する必要はありません。一言でまとめると、...

Linux アカウントのパスワードを変更する詳細な例

個人アカウントのパスワードを変更する一般ユーザーが個人アカウントのパスワードを変更する場合は、他のコ...

React Router V6 のアップデート

目次ReactRouterV6 の変更1. <Switch> が <Routes&...

Linux Cron によるパラメータ付き PHP コードのスケジュール実行

1. 引き続き PHP スクリプトを使用して実行します。コマンドラインに入力: php /home/...

TypeScript 名前空間のマージの説明

目次同じ名前の名前空間をマージする名前空間とその他の種類のマージ同じ名前の名前空間とクラスをマージす...

JavaScript 関数の高度な説明

目次関数定義方法関数呼び出し(6種類)これは問題を指摘している厳密モード高階関数閉鎖再帰: 自分自身...

TomcatのmaxPostSize属性を設定する際に注意する必要がある問題を解決する

必要:近い将来、大容量ファイルのアップロード機能を実装します。フロントエンドフレームワークのアップロ...

ReactプロジェクトでのTypeScriptの実装

目次1. はじめに2. 使用方法ステートレスコンポーネントステートフルコンポーネント制御コンポーネン...

MySQL でのサブクエリの基本的な使用法

目次1. サブクエリの定義2. サブクエリの分類1. スカラーサブクエリ: 2. MySQLサブクエ...