MySQLでインデックスを高速化する - CRCまたはMD5？

Question

私は8 300 000行のようなもので巨大なテーブルを持っています（編集も削除もされません）。

私の最初の列は何かのように見えるP300-4312B_X16_Sエントリは一意ではないので、このフィールドには通常のINDEXを使用します。

しかし、MySQLは、varcharの代わりにバイナリフィールドを使用する方が高速です。したがって、BINARY(16)を使用してデータを格納するMD5でINDEXをエンコードします。

今朝、私はCRC32をはじめて使用し始めました。CRC32は8文字を使って16進文字列として出力できることがわかりました。

私の質問：MD5の代わりにCRC32を使用すると高速になります。しかし、CRC32が2 000 000のユニークな値を言うとすると、結果は一意になるか、まれに2つの異なる文字列に対して同じ文字列を2回持つことになりますか？結果はMD5のように32（128b）ではなく8文字（32b）にすぎないため、私はそれを尋ねます。

ありがとうございました。

Answer 1

予想される衝突の数は、可能なチェック値の数に対するペアの数です。したがって、200万の値に対して（2000000 * 1999999）/ 2のペアがあり、約2x10 です。 32ビットCRCの場合、予想される衝突数は2以上である（、つまり466）。その場合、本質的に衝突が発生することが保証されます。

128ビットMD5チェック値の場合、予想される衝突数は約6x10 ^-27です。予想される数の小さな値については、それは1回の衝突の確率でもあります。

非常に低い確率で衝突する可能性がある場合は、CRC-32以外のものを選択する必要があります。

暗号強度がアプリケーションにとって重要でないMD5のオーバーヘッドは必要ありません。あなたが悪意のある人が別のエントリと同じチェック値を持つエントリを作成する方法を見つけることができるかどうかは本当に気にしません。したがって、その目的のために設計された64ビットの暗号化されていないハッシュを使用すると、はるかに高速に実行され、200万の値の場合に10 ^-7の確率で衝突する可能性があります。または、128ビットの非暗号化ハッシュを使用して、MD5と同じ確率を得ることができますが、はるかに高速です。ハッシュアルゴリズムのCityHash familyを見てください。

ただし、すべての場合において、衝突の確率はゼロではないことに注意してください。あなたのコードとの衝突の結果を考慮する必要があります。