MySQLのインデックスシステムがB+ツリーを使用する理由の分析

MySQLのインデックスシステムがB+ツリーを使用する理由の分析

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

インデックスは、テーブル内のデータ行の取得を高速化するために作成される分散ストレージ構造です。 (子供の頃に使っていた辞書と同じように、辞書で対応する単語を探す方が早いでしょう)

2. インデックスはなぜ必要なのでしょうか?

まず、いくつかの概念と知識を理解する必要があります

  1. mysql データはどこに保存されますか? - - ディスク
  2. データのクエリが遅い場合、通常どこに問題がありますか? ----IO
  3. (IOの効率を上げる必要があるのですが、どうやって上げればいいのでしょうか?----頻度と量の2つのレベル。例えば、レンガを1回動かすのと10回動かすのに費やされる労力は異なります。レンガを1個ずつ動かすのと10個ずつ動かすのに費やされる労力(IOリソースを占有する)も異なります。そのため、自分たちのニーズを満たしながら、IOとのやりとりをできるだけ減らすようにしています)
  4. ディスクからデータを読み取るとき、必要なだけ読み取りますか? ----ディスクの事前読み取り
  5. ディスクの事前読み取り: メモリとディスク間でデータが交換されるとき、通常はページ (データページ) と呼ばれる最小の論理単位があります。ページのサイズは一般にオペレーティング システムによって決定され、通常は 4k または 8k です。データを交換するとき、ページの整数倍でデータを読み取ることができます。InnoDB ストレージ エンジンは、毎回 16k のデータを読み取ります。
  6. 局所性原則: データとプログラムは一緒にクラスター化される傾向があり、以前アクセスされたデータは再度クエリされる可能性があり、空間的局所性と時間的局所性が関係します。

上記の概念を通じて、インデックスが何のために使用されるのか大まかにわかります。つまり、事前にインデックス システムを設計し、データをクエリするときに IO とのやり取りを減らして、クエリの効率を向上させます。

3. インデックス システムをどのように設計するか?

まずはいくつかの概念を理解しましょう

  • インデックスはどこに保存されますか? ----ディスク、データをクエリするときに、インデックスが最初にメモリにロードされます
  • インデックスを保存するときに必要な情報は何ですか?どのようなフィールド値を保存する必要がありますか?

——キー: 実際のデータ行に格納されている値 -ファイル アドレス(ポインター、データ ファイルが保存されている場所を見つけるにはファイル アドレスに頼る必要があります)
—— offset : オフセット(ファイル内のデータを取得する場合は、オフセットを使用する必要があります)

  • 上記の形式でデータを保存するには、どのようなデータ構造を使用する必要がありますか?

—— 上記から、データ形式が KV タイプであることがわかります。KV 形式のデータがわかれば、ハッシュ テーブル、ツリー (バイナリ ツリーバイナリ検索ツリーバイナリ バランス ツリー赤黒ツリーB ツリーB+ ツリー) など、データを格納するために使用するデータ構造がわかります。
まとめると、上記のデータ構造を使用してインデックスシステムを設計することができます。

4.MYSQL インデックス システムとは何ですか?

上記の形式で保存してみませんか?

ご存知のとおり、MySQL のインデックス システムはB+ ツリーを使用します。なぜ B+ ツリーなのでしょうか?次に、他のストレージ構造が機能しない理由を 1 つずつ分析します。その前に、OLAPとOLTPという2つの前提条件を理解する必要があります。

保存するデータが増えるほど、対応するインデックスも大きくなります。ディスクからメモリに読み込むときに、IO 問題が発生します。それでは、インデックスにインデックスを作成するのでしょうか?いいえ、MySQLはB+ツリーを使用します

5. ハッシュテーブル

ここに画像の説明を挿入

上記はハッシュ テーブルのストレージ構造です。このタイプのストレージ構造の利点と欠点について説明します。

  • ハッシュ衝突により、データ ハッシュが不均一になり、大量の線形クエリが生成され、時間がかかります。
  • 範囲クエリはサポートされていません。範囲クエリを実行するときは、各
  • メモリスペースの要件が比較的高い(すべてのデータをメモリに追加する必要がある)

アドバンテージ:
等価値クエリであれば、非常に高速になります

MySQL にはハッシュ インデックスがあるのでしょうか?

  • メモリ ストレージ エンジンはハッシュ インデックスを使用します。
  • InnoDBは適応ハッシュをサポート

6. 木

6.1 二分木

ここに画像の説明を挿入

バイナリ ツリー自体は順序付けられていません。データを検索するときは、データ要件を満たしているかどうかを確認するために、各ノードとデータを 1 つずつ比較する必要があり、非効率的です。

6.2 二分探索木 (BST)

ここに画像の説明を挿入

二分探索木の特性: データは順番に挿入する必要があり、左のサブツリーはルート ノードよりも小さく、右のサブツリーはルート ノードよりも大きくなることが保証される必要があります。したがって、バイナリ ツリーと比較してバイナリ検索ツリーを使用すると、クエリの効率が明らかに向上します。
ただし、データが昇順または降順で挿入されると、バイナリ検索木はリンクリストに退化し、検索効率が低下します。

ここに画像の説明を挿入

6.3 バランス二分木 (AVL 木)

ここに画像の説明を挿入

バイナリ検索ツリーによって明らかになった問題に応じて、AVL ツリーを使用してツリーを左または右に回転させてバランスをとります。ただし、バランスを確保するためには、データを挿入するときにローテーションが必要であり、クエリのパフォーマンスの向上を挿入パフォーマンスの低下で補うことになります。読み取りが多く、書き込みが少ない場合は問題ありませんが、読み取り要求と書き込み要求の数が同じ場合は適していません。

6.4 赤黒木

ここに画像の説明を挿入

赤黒木も左右の回転でバランスが取れており、色が変わる動作もあります。最長のサブツリーは最短のサブツリーの 2 倍以下であればよいので、クエリ パフォーマンスと挿入パフォーマンスはほぼバランスが取れます。ただし、データが挿入されると、ツリーの深さが深くなることがわかります。深さが深くなるほど、IO 時間が増え、データ読み取りの効率に影響します。

6.5 Bツリー

赤黒木によって明らかになった問題を考慮すると、読み取りの効率をどのように向上させるべきでしょうか?より多くのデータを保存できるように、順序付きバイナリ ツリーから順序付きマルチブランチ ツリーに変更できますか?

ここに画像の説明を挿入

次数 4 は、ノードが 3 つのデータ値を格納し、それを超える値は変換する必要があることを意味します。では、実際のデータはどのように保存されるのでしょうか?キー完全なデータ行が必要です

ここに画像の説明を挿入

上の図は、B ツリーが実際にデータを格納する方法を示しています。各ノードには、キーポインタデータの3 つの要素があります。
たとえば、データ 28 を見つけたい場合、まずディスク ブロック 1 から開始しますが、読み取れないことがわかります。p2 ポインターが指すディスク ブロック 3 と範囲を比較した後も、まだ見つかりません。次に、ディスク ブロック 8 を指しているディスク ブロック 3 の p2 ポインターに従って 28 を見つけます。分析してみましょう。各ディスク ブロックのサイズは 16kb です。3 つのディスク ブロックを検索するには、 48kb を読み取るだけで済みます。3層の B ツリーには、いくつのレコードを保存できますか

理想化して、キーとポインターはスペースを占有せず、1 つのデータが 1k のスペースを占有すると仮定します。すると、ディスク 1 には 16 個のデータが保存でき、ディスク 3 にも 16 個のデータがあり、ディスク 8 にも 16 個のデータがあります。この場合、16 + 16 + 16 = 4096レコードしか保存できませんが、明らかに少し少なすぎます。実際、キーとポインターもスペースを占有します。

では、なぜ保存されるデータの量がこんなに少ないのか疑問に思わざるを得ません。
ストレージの各層のサイズはデータによって占有されていることがわかりましたが、キーとポインターのみを保存できますか?このため、B+ツリーが導入される。

6.6 B+ツリー

ここに画像の説明を挿入

BツリーからB+ツリーへの進化:非リーフノードはデータを保存せず、リーフノードのみがデータを保存します

ここに画像の説明を挿入

上図では、p1と28は10バイトのグループであると仮定すると、第1層は16000/10=1600のサイズを保存でき、第2層も1600、第3層のデータは1kbを占め、これは16レコードであるため、合計ストレージは1600 1600 16=40960000( 4096万)レコードになります。

MySQL のインデックス構造は一般的に3 ~ 4層ですが、注意が必要な問題が 1 つあります。 3 層のストレージ構造があると仮定した場合、より多くのデータを保存するにはどうすればよいですか?
p1 と 28 のサイズが 10 バイトであると仮定しました。1 バイトの場合はどうなるでしょうか? その場合、合計ストレージ容量は 16000 16000 10 = 4096000000 になります。したがって、面接で常に尋ねられる質問につながります。インデックスを作成するには、int と var のどちらを使用する方が良いですか?

回答: キーの長さが短いほど良いです。長さが 4 バイト未満の varchar の場合は varchar を使用し、長さが 4 バイトを超える varchar の場合は int を使用します。

B+ ツリーの特性として、ストレージ容量が大きく、クエリが高速であることから、MySQL では B+ ツリーが採用されています。

要約する

これで、MySQL インデックス システムが B+ ツリーを使用する理由の説明は終わりです。何か間違ったことを言っていたら、指摘して訂正していただければ幸いです。

これで、MySQL のインデックス システムが B+ ツリーを使用する理由に関するこの記事は終了です。MySQL インデックス B+ ツリーの詳細については、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。

以下もご興味があるかもしれません:
  • MySQL データベース インデックスが B+ ツリーの使用を選択するのはなぜですか?
  • MySQL でインデックス構造として B+ ツリーを使用する利点は何ですか?
  • MySQL で B+ ツリー インデックスを使用する利点は何ですか?
  • MySQLが基礎データ構造としてB+ツリーを使用する理由
  • MySQL の B ツリー インデックスと B+​​ ツリー インデックスの違いの詳細な説明
  • MySQL B+ツリーインデックスとハッシュインデックスの詳細な説明
  • MySQL インデックス データ構造が B+ ツリーを使用する理由を理解するための記事

<<:  Flexレイアウトを使用してdiv内のサブ要素を垂直方向に中央揃えする例

>>:  DockerにElasticsearch7.6クラスタをインストールしてパスワードを設定する方法

推薦する

JavaScript の Set データ構造の詳細な説明

目次1. セットとは何か2. セットコンストラクタ2.1) 配列2.2) 文字列2.3) 議論2.4...

Vue での ref の使用法とデモンストレーション

ref 定義:要素またはサブコンポーネントの参照情報を登録するために使用されます。参照情報は、親コン...

Windows で MySQL サービスを停止または削除できない問題の解決策

圧縮パッケージを解凍して Windows に MySQL をインストールしました。インストール方法は...

海外の無料写真素材サイトベスト9

良い画像素材のウェブサイトを見つけるのは難しいです。特に無料です。良い写真には非常に目を引く視覚効果...

PHP で JSON バックスラッシュを削除する例

1. 「stripslashes($_POST['json']);」メソッドを使用し...

Linux環境でタイムゾーンを設定できない問題を解決

Linuxでタイムゾーンを変更する場合、常に変更することはできませんAsia/Shanghai に変...

ウェブページレイアウトデザインのシンプルな原則

この記事では、Web ページ レイアウト デザインのいくつかの簡単な原則をまとめ、Web ページ デ...

HTMLは角丸四角形を簡単に実装します

質問: div+css と配置を使用して角丸四角形を実現するにはどうすればよいですか?ソリューション...

Vueはカードフリップ効果を実現します

この記事では、カードフリップ効果を実現するためのVueの具体的なコードを例として紹介します。具体的な...

Pythonは出力をcsv操作に書き込む

以下のように表示されます。 def test_write(self): フィールド=[] field...

JavaScript Alert関数の実行順序の詳細な説明

目次質問分析する解決するAlert() 関数を置き換えるsetTimeOut関数まとめ質問数日前、J...

DockerとDocker-Composeの使用例

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

MySQLを使用して列内の異なる値の数をカウントする例

序文この記事で実装されている要件は、実際には非常に一般的です。たとえば、ユーザーが登録したチャネルを...

Linux の GRUB ブート プログラムの暗号化の概要

目次1. GRUB暗号化とは何か2. grub暗号化手順3. grub暗号化のロック属性1. GRU...

入力と画像を揃えるためにvertical-alignを使用します

input と img を同じ行に配置すると、img タグが常に input より 1 つ上になり、...