sql-server - SQL Server 哈希索引

Question

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

Answer 1

好的，2分。
SQL CHECKSUM 函数不产生哈希值。它实际上计算了一个 CRC 值。基于哈希检查不是一个很好的候选，因为会有相对大量的冲突。如果你想要一个散列函数，你应该检查 hash_bytes 函数。
其次，您实际上并没有创建哈希索引。您正在对哈希值创建一个普通的 b-tree，因此查找时间将与在类似大小的数据类型上的任何其他 b-tree 索引完全相同。
通过使用长 varchar 值的 CRC 或散列来允许比较较少的字节数，您有可能获得一点性能，但字符串比较只检查它需要的字节数，即第一个不匹配的字符，如果你在哈希值上匹配，那么无论如何你都需要仔细检查实际值。因此，除非您有很多非常相似的字符串，否则您最终可能会使用散列（或 CRC）比较更多字节。

简而言之，我认为这不是一个明智的计划，但与所有优化一样，您应该在特定情况下对其进行测试，然后再决定。如果您愿意发布结果，我很想看看您的结果。而且我不相信有比使用聚集索引更快地在 SQL Server 中定位行的方法。

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

Answer 2

我不认为 SQL 服务器本身具有基于哈希表的索引。BOL 文档正在讨论在计算值上构建标准（树）索引。这与线性哈希表不同，线性哈希表是某些 DBMS 平台上可用的索引结构，但不是 SQL Server (AFAIK)。

使用此博客文章中描述的技术对较大的字符串值（例如 URL）进行哈希处理以加快查找速度，您可能会获得一些好处。但是，底层索引仍然是一个树结构，并且是 O(Log N)。

Answer 3

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

一般来说，除非您对潜在的大字符串或二进制 blob 进行精确匹配（如 pipTheGeek 所述），否则我不会创建人工哈希列。我只是想补充一点，有时这是必要的，因为字符串可能太大而无法放入索引键中。我认为 SQL Server 的索引键大小是 2k 的。

当然，在您的联接中，您需要包含散列列和源列，以解决散列导致的任何歧义。

Answer 4

如果 ID 字段是 int，则在 ID 字段上的聚集索引上搜索索引 CHECKSUM 没有任何优势，因为两者都会进行聚集索引查找。此外，int 列的 CHECKSUM 始终返回与该列相同的值（即 CHECKSUM(535) = 535）。但是，如果 ID 是长字符列，则 CHECKSUM 查找通常会执行得更好。