MySQL btree インデックスとハッシュ インデックスの違い

MySQL では、ほとんどのインデックス (PRIMARY KEY、UNIQUE、INDEX、FULLTEXT など) は BTREE に格納されますが、メモリ エンジンを使用する場合は、BTREE インデックスまたは HASH インデックスを選択できます。2 つの異なるタイプのインデックスには、使用範囲が異なります。

• B ツリー インデックスには、範囲検索とプレフィックス検索を実行する機能があります。N 個のノードを持つ B ツリーの場合、レコードを取得する複雑さは O(LogN) です。バイナリ検索と同等です。
• ハッシュインデックスは等価検索にのみ使用できますが、ハッシュテーブルがどれだけ大きくても、検索の複雑さは O(1) です。
  

明らかに、値が大きく異なり、主な検索が等しい値（=、<、>、in）である場合、ハッシュインデックスは検索の複雑さが O(1) であるため、より効率的な選択肢となります。
値間の差が比較的小さく、範囲検索が主な焦点である場合は、範囲検索をサポートしている B ツリーの方が適しています。

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

保存アドレスはハッシュ関数を使用して計算されるため、取得時にBtreeのようにルートノードからトラバースしてレベルごとに検索する必要はありません。

ハッシュ インデックスの特殊な構造により、検索効率が非常に高くなります。ルート ノードからブランチ ノード、そして最終的にページ ノードまで複数の IO アクセスを必要とする B ツリー インデックスとは異なり、インデックス検索は 1 回で済みます。そのため、ハッシュ インデックスのクエリ効率は B ツリー インデックスよりもはるかに高くなります。

多くの人が再び疑問に思うかもしれません。ハッシュ インデックスの効率は B-Tree よりもはるかに高いのに、なぜ B-Tree インデックスの代わりにハッシュ インデックスを使用しないのでしょうか。すべての物事には2つの側面があり、ハッシュ インデックスでも同じことが言えます。ハッシュ インデックスは非常に効率的ですが、その特殊性により多くの制限や欠点もあります。主なものは次のとおりです。

（1）ハッシュインデックスは「=」、「IN」、「<=>」クエリのみを満たすことができ、範囲クエリには使用できません（範囲クエリは低速です）。

ハッシュインデックスはハッシュ演算後のハッシュ値を比較するため、対応するハッシュアルゴリズムによって処理された後のハッシュ値の大小関係がハッシュ演算前と全く同じであることを保証できないため、等値フィルタリングにのみ使用でき、範囲ベースのフィルタリングには使用できません。

（２）ハッシュインデックスはデータのソート操作を回避するために使用することはできません。

ハッシュ インデックスにはハッシュ計算後のハッシュ値が格納され、ハッシュ値のサイズ関係はハッシュ操作前のキー値と必ずしも正確に同じではないため、データベースはインデックス データを使用してソート操作を回避することはできません。

（３）ハッシュインデックスは部分インデックスキーを使用してクエリすることはできません。

複合インデックスの場合、ハッシュ インデックスはハッシュ値を個別に計算するのではなく、複合インデックス キーを結合してハッシュ値を計算します。したがって、複合インデックスの最初の 1 つまたは複数のインデックス キーをクエリする場合、ハッシュ インデックスは使用できません。

（4）ハッシュインデックスは、いつでもテーブルスキャンを回避することはできません。

ご存知のように、ハッシュ インデックスは、インデックス キーをハッシュした後、ハッシュ操作の結果のハッシュ値と対応する行ポインタ情報を格納するテーブルです。異なるインデックス キーは同じハッシュ値を持つため、特定のハッシュ キー値を満たすレコードの数を取得しても、ハッシュ インデックスから直接クエリを完了することはできません。テーブル内の実際のデータにアクセスして対応する比較を実行し、対応する結果を取得する必要があります。

（５）ハッシュ値が多数等しい場合、ハッシュインデックスのパフォーマンスは必ずしもBツリーインデックスのパフォーマンスよりも高いとは限りません。

選択性の低いインデックス キーの場合、ハッシュ インデックスを作成すると、大量のレコード ポインター情報が同じハッシュ値に格納され、それに関連付けられます。これにより、特定のレコードを見つけるのが非常に面倒になり、複数のテーブル データ アクセスが無駄になり、全体的なパフォーマンスが低下します。

2. B+ツリー

• b+ツリーの探索プロセス
  

図に示すように、データ項目 29 を検索する場合、最初にディスク ブロック 1 がディスクからメモリにロードされます。このとき、IO が発生します。メモリ内でバイナリ検索を使用して、29 が 17 と 35 の間にあることを判別します。ディスク ブロック 1 の P2 ポインターはロックされています。メモリ時間は非常に短いため (ディスク IO と比較して) 無視できます。ディスク ブロック 3 は、ディスク ブロック 1 の P2 ポインターのディスク アドレスを介してディスクからメモリにロードされます。2 番目の IO が発生します。29 は 26 と 30 の間にあります。ディスク ブロック 3 の P2 ポインターはロックされています。ディスク ブロック 8 は、ポインターを介してメモリにロードされます。3 番目の IO が発生します。同時に、メモリ内でバイナリ検索を実行して 29 を見つけ、クエリが終了します。合計 3 つの IO が実行されます。実際には、3 層の B+ ツリーは数百万のデータを表すことができます。数百万のデータの検索に 3 つの IO しか必要ない場合、パフォーマンスは大幅に向上します。インデックスがない場合、各データ項目に IO が必要になり、合計で数百万の IO が必要になりますが、これは明らかに非常にコストがかかります。

• B+ツリーのプロパティ
  

1. インデックス フィールドはできるだけ小さくする必要があります。

以上の分析から、IO回数はb+numberの高さhに依存することがわかります。現在のデータテーブルのデータがNで、各ディスクブロックのデータ項目数がmであると仮定すると、h=㏒(m+1)Nとなります。データ量Nが一定の場合、mが大きいほどhは小さくなり、m = ディスクブロックサイズ/データ項目サイズとなります。ディスクブロックサイズはデータページのサイズで、固定されています。データ項目が占めるスペースが小さく、データ項目数が多いほど、ツリーの高さは低くなります。このため、各データ項目、つまりインデックス フィールドは、できるだけ小さくする必要があります。たとえば、int は 4 バイトを占めますが、これは bigint の 8 バイトの半分です。このため、b+ ツリーでは、実際のデータを内部ノードではなくリーフ ノードに配置する必要があります。内部ノードに配置すると、ディスク ブロックのデータ項目が大幅に減少し、ツリーの高さが増加します。データ項目が 1 に等しい場合、線形リストに退化します。

2. インデックスの最も左のマッチング機能（つまり、左から右へのマッチング）:

b+ツリーのデータ項目が（名前、年齢、性別）などの複合データ構造である場合、b+ツリーは左から右の順に検索ツリーを構築します。たとえば、（張三、20、F）などのデータが取得されると、b+ツリーは最初に名前を比較して次の検索方向を決定します。名前が同じ場合は、年齢と性別が順番に比較され、最終的に取得されたデータを取得します。ただし、（20、F）などの名前のないデータが来ると、b+ツリーは次にどのノードをチェックすればよいかわかりません。これは、名前が検索ツリーを構築するときの最初の比較要素であり、次にどこを照会するかを知るために最初に名前に基づいて検索する必要があるためです。たとえば、(Zhang San, F) のようなデータを取得する場合、b+ ツリーは名前を使用して検索方向を指定できますが、次のフィールド age が欠落しているため、名前が Zhang San と同じデータのみを検索し、その後、性別が F のデータと一致させます。これは非常に重要なプロパティであり、インデックスの最も左の一致機能です。

上記は、MySQL btree インデックスとハッシュ インデックスの違いに関する詳細な内容です。MySQL btree インデックスとハッシュ インデックスの詳細については、123WORDPRESS.COM の他の関連記事に注目してください。