1

我在看一篇关于hash indexing的文章，好像md5和php的函数很像，都是取一个字符串值，返回一个表示该字符串的整数，而且这个表示是一致的。这种相似性真的存在吗，还是我错过了什么？另外，有人对 MySQL 用于基于哈希的索引结构的哈希算法有所了解吗？

4

1 回答 1

2

我不是假装对 MySQL 算法给出完整的描述，但有一些事情可能会被猜到。

首先，Hash table wiki是必读的。然后我们从MySQL 文档中得到一个通知：

  • 它们仅用于使用 = 或 <=> 运算符的相等比较（但速度非常快）。它们不用于
    查找值范围的比较运算符，例如 <。依赖这种类型的单值查找的系统被称为“键值存储”；要将
    MySQL 用于此类应用程序，请尽可能使用哈希索引。
  • 优化器不能使用哈希索引来加速 ORDER BY 操作。（这种类型的索引不能用于按顺序搜索下一个条目。）
  • MySQL 无法确定两个值之间大约有多少行（范围优化器使用它来决定使用哪个索引）。如果您将 MyISAM 表更改为哈希索引的 MEMORY 表，这可能会影响某些查询。
  • 只能使用整个键来搜索行。（使用 B 树索引，键的任何最左边的前缀都可用于查找行。）

这指向以下（相当常见的）属性：

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

  2. 在猜测散列函数的上限行数时，引擎可能会使用一个max_heap_table_size全局值和一个参数。MAX_ROWS

  3. MySQL允许非唯一键，但会警告按比例减速。至少这可以说明没有第二个散列函数，而只是在冲突解决中使用的链表。

至于实际使用的功能，我认为没什么好说的。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.

于 2012-08-28T12:10:14.580 回答