1

md5ハッシュインデックスに関する記事を読んでいましたが、文字列値を取り、その文字列を表す整数を返すという点でPHPの関数に似ているようで、この表現は一貫しています。この類似性は本当にそこにありますか、それとも私は何かが欠けていますか？さらに、MySQLがハッシュベースのインデックス構造に採用しているハッシュアルゴリズムについて誰かが知っていますか？

4

1 に答える 1

2

MySQLアルゴリズムについて完全に説明するつもりはありませんが、推測できることがいくつかあります。

まず第一に、ハッシュテーブルウィキは必読です。次に、 MySQLドキュメントからの通知があります。

  • これらは、=または<=>演算子を使用する等式比較にのみ使用されます（ただし、非常に高速です）。
    これらは、値の範囲を見つける<などの比較演算子には使用されません。このタイプの単一値ルックアップに依存するシステムは、「Key-Valueストア」と呼ばれます。このようなアプリケーションにMySQLを
    使用するには、可能な限りハッシュインデックスを使用してください。
  • オプティマイザーは、ハッシュ索引を使用してORDERBY操作を高速化することはできません。（このタイプのインデックスを使用して、次のエントリを順番に検索することはできません。）
  • MySQLは、2つの値の間にあるおおよその行数を判別できません（これは、使用するインデックスを決定するために範囲オプティマイザーによって使用されます）。MyISAMテーブルをハッシュインデックス付きMEMORYテーブルに変更すると、一部のクエリに影響する可能性があります。
  • 行の検索に使用できるのはキー全体のみです。（Bツリーインデックスを使用すると、キーの左端のプレフィックスを使用して行を検索できます。）

これは、次の（かなり一般的な）プロパティを示しています。

  1. MySQLハッシュ関数は、固定長の「フルキー」レコードで動作します（ただし、varcharがどのように処理されるかは問題です。たとえば、最大長までゼロが埋め込まれる場合があります）。

  2. ハッシュ関数の上位行数を推測するときにエンジンが使用する可能性が高いmax_heap_table_sizeグローバル値とパラメーターがあります。MAX_ROWS

  3. MySQLは非一意キーを許可しますが、比例的な速度低下について警告します。少なくともこれは、2番目のハッシュ関数がないことを示している可能性がありますが、衝突解決で使用される単なるリンクリストです。

実際に使っている機能については、あまりわかりません。MySQLは、いくつかの主要なヒューリスティックに従って異なる関数を使用する場合もあります（たとえば、IDなどのほとんどのシーケンシャルデータ用に1つ、CHAR用に別の関数）。もちろん、その出力は推定行数に応じて変更されます。ただし、ハッシュインデックスを検討する必要があるのは、BTREEで十分なパフォーマンスが得られない場合、またはBTREEの利点をまったく使用しない場合のみです。これは、まれなケースです。

アップデート

ソースについて少し説明します/storage/heap/hp_hash.c。ハッシュ関数の実装がいくつか含まれています。少なくとも、TEXTとVARCHARに関しては、タイプごとに異なる手法を使用しているというのは正しい仮定でした。

/*
 * Fowler/Noll/Vo hash
 *
 * The basis of the hash algorithm was taken from an idea sent by email to the
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 * later improved on their algorithm.
 *
 * The magic is in the interesting relationship between the special prime
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 *
 * This hash produces the fewest collisions of any function that we've seen so
 * far, and works well on both numbers and strings.
 */

簡単に説明しようと思います。

ulong nr= 1, nr2= 4;
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)

化合物キーのすべての部分は個別に処理され、結果はに蓄積されnrます。

if (seg->null_bit)
{
  if (rec[seg->null_pos] & seg->null_bit)
  {
    nr^= (nr << 1) | 1;
    continue;
  }
}

NULL値は個別に扱われます。

if (seg->type == HA_KEYTYPE_TEXT)
{
  uint char_length= seg->length; /* TODO: fix to use my_charpos() */
  seg->charset->coll->hash_sort(seg->charset, pos, char_length,
                                &nr, &nr2);
}
else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
{
  uint pack_length= seg->bit_start;
  uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
  seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
                                length, &nr, &nr2);
}

TEXTとVARCHARもそうです。hash_sortおそらく、照合を考慮に入れる他の関数です。VARCHARには、接頭辞1または2バイトの長さがあります。

else
{
  uchar *end= pos+seg->length;
  for ( ; pos < end ; pos++)
  {
nr *=16777619; 
nr ^=(uint) *pos;
  }
}

そして、他のすべてのタイプは、多重化と。でバイトごとに扱われますxor。

于 2012-08-28T12:10:14.580 に答える