mysql インデックスは通常どのようなデータ構造を使用しますか?

MyISAM は、MySQL 5.5 より前のバージョンのデフォルトのストレージ エンジンです。5.5 以降は、InnoDB が MySQL のデフォルトのストレージ エンジンになり始めます。

MyISAM は、B ツリーを使用して主キー インデックス、一意のインデックス、および非主キー インデックスを実装します。

InnoDB の非主キー インデックスは B-Tree データ構造を使用しますが、主キー インデックスは B-Tree を使用します。

B ツリー

B ツリー (バイナリではなく多方向検索ツリー) は、一般的なデータ構造です。 B ツリー構造を使用すると、レコードを検索する際の中間プロセスが大幅に削減され、アクセスが高速化されます。翻訳によれば、B は通常、Balance の略語であると考えられています。このデータ構造は通常、データベースのインデックス作成に使用され、全体的な効率が高くなります。

パフォーマンス(推奨学習: MySQL ビデオ チュートリアル)

B ツリーには次の特徴があります:

1. キーワードコレクションはツリー全体に分散されます;

2. すべてのキーワードが表示され、1 つのノードにのみ表示されます;

3. 検索は非リーフ ノードで終了する場合があります;

4. キーワードの完全なセットにおける二分検索と同等の検索パフォーマンス;

5. 自動階層制御;

B Tree

# #異なるストレージ エンジンはストレージに異なるデータ構造を使用する可能性があります。InnoDB は B ツリーを使用します;

それでは、B ツリーとは何ですか?
B ツリーは、ファイル システムに必要な B ツリーのバリアントです。m 次の B ツリーと m 次の B ツリーの違いは次のとおりです:

B と B - (つまり B) は、各ノードのキーワードが異なるためです。もう 1 つ、1 つ減ります。

B-tree の場合、ノード構造は B-tree と同じですが、各ノードのキーワードと持つことができる子ノードの数が異なります。たとえば、m 次の B ツリーでは、各ノードは最大 m 個の子ノードを持つことができます。非ルートノードには少なくとも [m/2] 個の子ノードがあり、キーワードの数は B ツリーより 1 つ多く、[m/2] ～ m です。

インデックスを処理するためのこれら 2 つのデータ構造の違い:

1.同じキー値が B ツリーに複数回出現することはなく、リーフ ノードまたは非リーフ ノードに出現する可能性があります。 B ツリーのキーは必ずリーフ ノードに表示されますが、B ツリーのバランスを維持するために非リーフ ノードにも繰り返し表示される場合があります。

2. B ツリー キーの位置は不確実であり、ツリー構造全体で 1 回しか出現しないため、記憶域を節約できますが、挿入および削除操作は大幅に複雑になります。それに比べて、B ツリーはより良い妥協案です。

3. B ツリーのクエリ効率はツリー内のキーの位置に関係します。最大時間計算量は B ツリー (葉ノードにある場合) と同じで、最小時間計算量は 1 (ルートノードにある場合)。 B ツリーの時間計算量は、構築された特定のツリーに対して固定されます。

MySQL 関連の技術記事の詳細については、MySQL データベース グラフィック チュートリアル 列にアクセスして学習してください。

以上がmysql インデックスは通常どのようなデータ構造を使用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。