mysql - MySQL 中的哈希索引算法

Question

我在看一篇关于哈希索引的文章，它似乎类似于 PHP 的 md5 函数，因为它们都接受一个字符串值并返回一个表示该字符串的整数，并且这种表示是一致的。这种相似性真的存在吗，还是我遗漏了什么？另外，有人了解 MySQL 用于基于散列的索引结构的散列算法吗？

Answer 1

我并不想假装对 MySQL 算法进行完整的描述，但有一些事情是可以猜到的。

首先，Hash table wiki是必读的。然后我们收到来自 MySQL documentation 的通知:

• They are used only for equality comparisons that use the = or <=> operators (but are very fast). They are not used for comparison
  operators such as < that find a range of values. Systems that rely on this type of single-value lookup are known as “key-value stores”; to
  use MySQL for such applications, use hash indexes wherever possible.
• The optimizer cannot use a hash index to speed up ORDER BY operations. (This type of index cannot be used to search for the next entry in order.)
• MySQL cannot determine approximately how many rows there are between two values (this is used by the range optimizer to decide which index to use). This may affect some queries if you change a MyISAM table to a hash-indexed MEMORY table.
• Only whole keys can be used to search for a row. (With a B-tree index, any leftmost prefix of the key can be used to find rows.)

这指向以下(相当常见的)属性:

1. MySQL 哈希函数对固定长度的“全键”记录进行操作(它 但是，这是一个问题，如何处理 varchars，例如它们可能会用零填充到最大长度)

2. 有一个 max_heap_table_size 全局值和一个 MAX_ROWS 参数，引擎在猜测哈希函数的上行计数时可能会使用该参数。

3. MySQL allows非唯一键，但会警告按比例减速。至少这可能表明没有第二个哈希函数，而只是一个用于冲突解决的链表。

至于实际使用的功能，我觉得也没什么好讲的。 MySQL 甚至可以根据一些关键的启发式方法使用不同的函数(例如，一个用于大多数顺序数据，例如 ID，另一个用于 CHAR)，当然它的输出会根据估计的行数而改变。但是，只有当 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逐字节处理。