MySQL インタビューの質問 - ハッシュインデックスを設定する方法

MySQL では、B-Tree インデックスに加え、以下のインデックスを提供しています。

• ハッシュインデックス

メモリエンジンのみ対応、シンプルなシナリオ

• R-Treeインデックス作成

MyISAMの特殊なインデックスタイプで、主に地理空間データ型に使用される

• フルテキスト

MyISAMの特別なインデックスで、主にフルテキストインデックスに使用され、InnoDBはMySQL 5.6以降でフルテキストインデックスをサポートしています。

インデックス / ストレージエンジンMyISAMInnoDBMemoryB-Tree IndexesSupportSupportHASH IndexesNotSupportSupportR-Tree IndexesSupportNotSupportFull-text IndexesSupportSupportNotSupport

最もよく使われるインデックスはB-treeインデックスとHashインデックスで、MemoryとNDBの2つのエンジンのみがHashインデックスをサポートしています。HashインデックスはKey-Valueクエリに適しており、B-treeインデックスより高速です。しかし、Hashインデックスは、<><==,>==などの範囲検索をサポートしません。メモリは"="の条件下でのみハッシュ・インデックスを使用します。

MySQLは8.0で初めて関数インデックスをサポートしました。それ以前は、カラムの特定の部分、例えばtitleフィールドのインデックスを取るには、最初の10文字だけを取ることができました。このような機能はインデックスファイルのサイズを大幅に削減しますが、プレフィックスインデックスにはorder byやgroup by操作で失敗するという欠点もあります。

create index idx_title on film(title(10));

1 特徴

配列だけが存在し、ハッシュ関数を使用してキーを定義されたメモリ位置に変換し、配列のその位置に値を配置します。ハッシュを使用すると、当然ハッシュの衝突の可能性が出てきますが、MySQL はジッパーメソッドでこれを解決しています。

ハッシュインデックスはハッシュテーブルに基づいており、クエリ条件がハッシュインデックス内のカラムと完全に一致する場合にのみ使用することができます。ハッシュインデックス内のすべてのカラムについて、ストレージエンジンは各行のハッシュコードを計算し、それをハッシュインデックスに格納します。

• 例えば、ID番号と名前を保持し、ID番号から対応する名前を調べるようなテーブルでは、以下のようなハッシュインデックスを持つことになります。

例えば、ユーザー名に対応するID_card_n4をチェックしたい場合。

• ID_card_n4は、ハッシュ関数A
• User4を探すために繰り返し実行する。

4つのID_card_nの値は必ずしもインクリメントされないので、新しいUserが追加されたとしても、後で追加すればよいので高速である。もちろん欠点も明らかで、順序付けされていないため、ハッシュインデックスはインターバルクエリーを行うには遅いです。例えば、[ID_card_X, ID_card_Y]の区間にあるID番号を持つユーザーをすべて見つけたい場合、テーブル全体をスキャンする必要があるのです。

2 ハッシュインデックスの欠点

• 2回検索する必要がある
• 部分的なインデックス検索、範囲検索はサポートされていません。
• ハッシュコードにハッシュの衝突が発生することがあり、ハッシュアルゴリズムの設計が悪いと、衝突が多すぎて性能が低下することがある
• インデックスはハッシュ値を格納するため、< = >とINのみがサポートされている
• インデックスを格納する際にハッシュを計算するが、計算したハッシュ値と格納したハッシュ値は必ずしも等しくないので、操作してもソートできない
• メモリテーブルで非ユニークなハッシュインデックスがサポートされているため、フルテーブルスキャンを避けることができない。
• ハッシュテーブルは、キーワードを元にメモリの格納場所に直接アクセスするデータ構造なので、その原理を利用したハッシュインデックスも全てのデータファイルをメモリに追加する必要があり、非常にメモリを消費することになる
• すべてのクエリがイコールクエリである場合、ハッシュは確かに高速だが、実際にはより広範囲のルックアップデータを扱うことになる
• Key-value all-value matchのスマートな処理
• クエリHash関数がインデックスされたキーの大きさを決定する

InnoDBやMyISAMでハッシュインデックスをサポートさせるには、アダプティブハッシュインデックスと呼ばれる擬似ハッシュインデックスで対応することが可能です。

これは、ハッシュ値を格納するフィールドを追加し、ハッシュ値にインデックスを付け、挿入および更新時に計算されたハッシュを自動的にテーブルに追加するトリガーを作成することで実現できる。

ハッシュテーブルのような構造は、Memcachedのような等価値クエリしか利用できないシナリオに適している。

3つの事例

ユーザーログインのような非常に大きなテーブルがある場合、電子メールによってユーザーを検索する必要があります。emailカラムに直接インデックスを作成すると、インデックス間のマッチングに加えて、文字列のマッチングを行う必要があります。これは、emailが短い場合は問題ありませんが、クエリーが長い場合はよりコストが高くなります。emailにハッシュインデックスを構築し、intでクエリを実行すれば、文字列マッチングよりはるかに高速なパフォーマンスが得られます。

ハッシュアルゴリズム

ハッシュインデックスを構築するには、まずハッシュアルゴリズム（High Performance MySQL が言及している CRC32 アルゴリズム）を選択する必要があります。

INSERT UPDATE SELECT操作

テーブルにハッシュ値でフィールドを追加する。

ALTER TABLE `User` ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

次のステップは、UPDATEとINSERT時にemail_hashフィールドを自動的に更新することで、これはトリガで行われます。

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
END; |
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|END;
DELIMITER ;

となるので、SELECTリクエストは

SELECT `email`, `email_hash` FROM `User` WHERE 
	email_hash = CRC32("[email protected]") 
			AND `email`= "[email protected]";

+----------------------------+------------+
| 電子メール｜電子メールアドレス｜電子メールアドレスハッシュ
+----------------------------+------------+
| [email protected]｜2765311122｜。
+----------------------------+------------+

AND email = "[email protected]"は、ハッシュが衝突した場合に不正確なデータにならないようにするためです。

この記事は、ハッシュインデックスの設定方法に関する MySQL インタビューの質問に関するものです。MySQLのハッシュインデックス設定については、スクリプトハウスの過去記事を検索していただくか、引き続き以下の関連記事をご覧ください。