SQL Server哈希索引

Question

当使用CHECKSUM列类型人为地创建哈希索引时，查找实际上是O(1)，还是仍然是O(lg n)，就像对聚集索引一样？我有一个表，我将根据它的ID列进行选择，并且我需要尽可能快的查找，那么聚集索引是可能的最快选项吗？我正在寻找的东西，将提供O(1)的性能。

Answer 1

好的，2分。

SQL校验和函数不生成哈希值。它实际上计算CRC值。这不是一个非常好的候选散列检查的基础上，因为将会有相对大量的冲突。如果你需要一个散列函数，你应该检查hash_bytes函数。

其次，您实际上并没有创建散列索引。您将在散列值上创建一个普通的b-tree，因此查找时间将与在类似大小的数据类型上的任何其他b-tree索引完全相同。

通过使用CRC或长varchar值的散列来允许比较较少的字节数，您可能会获得一些性能，但是字符串比较只检查所需的字节数，即不匹配的第一个字符，如果您确实匹配散列值，则无论如何都需要再次检查实际值。因此，除非您有很多非常相似的字符串，否则很可能会使用散列(或CRC)来比较更多的字节。

简而言之，我不认为这是一个明智的计划，但与所有优化一样，您应该在您的特定情况下测试它，然后再做出决定。如果你愿意发布你的结果，我会很感兴趣。而且我不认为在SQL server中有比使用聚集索引更快的查找行的方法。

如果您关心，Ingres (由CA)可以创建哈希索引，然后实现O(1)。可能还有其他的RDBM也支持真正的散列索引。

Answer 2

我不认为SQL server本身就有基于哈希表的索引。BOL documentation正在讨论在一个计算值上建立一个标准(树)索引。这与Linear Hash Table不是一回事，后者是一些数据库管理系统平台上可用的索引结构，但不是SQL Server (AFAIK)。

使用this blog post中描述的技术来散列大型字符串值(例如URL)以加快查找速度，您可能会从中受益。但是，底层索引仍然是树结构，并且是O(Log N)。

Answer 3

您可以尝试设置为使用散列连接，您可以查看执行计划以验证是否实际使用了散列连接。使用哈希联接时，SQL Server仍将首先生成哈希表，作为执行单个查询的一部分。我相信索引永远不会以哈希的形式存储，只会以树的形式存储。

通常，我不会创建人工哈希列，除非您正在对可能很大的字符串或二进制blobs进行精确匹配(正如pipTheGeek提到的)。我只想补充说，有时这是必要的，因为字符串可能太大，无法放入索引键。对于SQL Server，索引键的大小有一个限制，我认为是2k。

当然，在您的联接中，您需要包括散列和源列，以解决由散列引起的任何多义性。