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クラスタをインストールしてパスワードを設定する方法

推薦する

Vue Element Sortablejs を使用してテーブル列をドラッグする詳細な説明

1. css: ドラッグテーブル.css @charset "UTF-8"; ....

MySQL における一般的なランキングの問題をいくつかまとめます

序文:一部のアプリケーション シナリオでは、成績や年齢によるランキングなど、ランキングの問題が発生す...

MySQL パーティション関数の詳細な説明と例の分析

まず、データベース パーティショニングとは何でしょうか?以前、MySQL のテーブル パーティショニ...

HTML マークアップ言語 - フォーム

123WORDPRESS.COM HTML チュートリアル セクションに戻るには、ここをクリックして...

Linux で g++ を使用してプログラムをコンパイルする際の -I (大文字の i)、-L (大文字の l)、-l (小文字の l) の機能の詳細な説明

初心者の Linux ユーザーとして、私は単純なgcc/g++操作を何度も使用してきましたが、少し複...

Linux での MySQL 5.6.24 (バ​​イナリ) 自動インストール スクリプト

この記事では、Linux環境でのmysql5.6.24自動インストールスクリプトコードを参考までに共...

Vue3.0 は虫眼鏡効果のケーススタディを実装します

達成される効果は、固定ズームが 2 倍になり、マウスが左側の画像領域に入るとマスク レイヤーが表示さ...

node.js グローバル変数の具体的な使用法

グローバルオブジェクトすべてのモジュールは呼び出すことができますglobal: ブラウザの wind...

Navicat を仮想マシン MySQL に接続する際によくあるエラーと解決策

質問1 解決するサービスを開始します: service mysqld start; /sbin/ip...

CSS 3D からソースコードによる空間座標軸へ

かつて、サイコロを振るゲームについて話しました。その時は、steps 属性 + スプライト画像を使用...

要素動的ルーティングブレッドクラムの実装例

マスターするには: localStorage、コンポーネントのカプセル化えーと、GIF に変換したビ...

bash スクリプトで ssh/scp コマンドにパスワードを渡す方法の詳細な説明

SSHPASSをインストールする最新のオペレーティング システムでは、sshpass パッケージはデ...

10 種類のモダンなレイアウトを実現するための CSS コード

序文日曜日に自宅で web.dev の 2020 3 日間ライブを視聴したところ、興味深い点がたくさ...

Datagrip2020 が MySQL ドライバーのダウンロードに失敗する

「downloadlaod」を直接クリックしてもダウンロードできない場合は、ここからダウンロードす...

iframeを使用してページを呼び出すとページがキャッシュされるかどうかの簡単な分析

最近、毎日変更されるページを iframe を使用して呼び出す必要があるプロジェクトがあります。その...