database - 为什么具有很少唯一值的列上的索引无效？

Question

因此，大多数数据库专家表示，相对于表的大小，在唯一值很少的列上创建索引是无效的。

基于数据库内部的工作方式（我知道大多数数据库使用 B-tree 存储索引），为什么唯一值很少的 B-Tree 会使搜索效率低下？

Answer 1

首先，您需要了解列上的索引是如何工作的。简而言之，它不过是，

给定列中所有可能值的有序列表，并带有指向数据库中实际记录的指针。

由于它是有序的，因此可以对它使用二进制搜索，而不是线性搜索，这可以提高大型数据集的性能。

想象一下，您的索引是按列排序的电话簿，比如说last name；但是在具有相似 的记录集中，记录last name没有共同的模式或有意义的顺序：它们纯粹是随机排序的。并说我们需要搜索这条记录：

艾克·史密斯 4783 Random Ave. Seattle, WA 98117

既然电话簿是按顺序排列的last name，我们只需要依次去 the S、the m、thei等，直到找到Smith。而且（希望）下面只有几条记录，Smith所以我们很快就能找到我们想要的记录。

现在，假设您有一个电话簿，city而不是last name. 在匹配给定的记录中，city没有特定的顺序。所以我们再次尝试搜索。然而，一旦我们找到Seattle（使用极其复杂的二分搜索），我们就剩下接近 620,778 条记录，我们必须按顺序检查它们，因为它们是完全随机排列的。我们一直在检查每一个条目是否有我们想要的记录。

当您使用一个非常常见的列作为索引的基础时会发生这种情况：二进制搜索返回一个非常大的可能记录集，数据库无法对这些记录做出超出初始索引列值的任何假设，因此它需要在结果集中按顺序检查匹配记录。

如果电话簿是按zip code（一个不太常见的变量）排序的，那么您可能会发现自己只搜索位于98117.

last name此外，真正的电话簿通常类似于复合索引：不只是按单列排序（first name即middle name在每一步都以线性方式完成，直到找到所需的记录。它基本上是索引中的索引，即使第一列不常见，与第二列的组合也提供了足够具体的标准，只需要线性搜索一小组记录。

Answer 2

在 b 树中，索引与数据分开存储（至少在磁盘上）。对 b-tree 的搜索需要O(log n)查找，另一个需要查找O(1)表本身。

在不使用索引进行搜索时，通过扫描表会遇到很大的查找时间，即O(n). 但是，当匹配结果存储在整个表中时，通过执行表扫描，对索引的查找超过（就资源而言）查找。

当您有许多可以匹配查询的值时，您可以O(log n)查找索引并查找表数据本身。然后，您几乎会进行表扫描（因为对大部分表的顺序查找都接近扫描），因此索引对表扫描的少量减少小于搜索索引本身的浪费。

更多细节：每次匹配时，必须重新定位磁头的树查找和查找延迟（在硬盘上）发生一次（使用简单的索引查找方法），而表扫描只发生一次。即使数据在索引中聚集，也必须进行计算和扫描，并且查询优化器会选择表扫描。

_{请原谅这篇文章组织得不好，我是因为睡眠不足而工作的}

Answer 3

一般来说，索引的目标是通过避免扫描表中的大部分数据来提供比线性搜索更快的速度（参见http://en.wikipedia.org/wiki/Database_index）。如果许多可能的索引值是相同的，那么即使在成功的索引查找之后，数据库也必须扫描表的重要部分。

因此，具有很少唯一值的索引将提供很少的性能优势，而与它的实现无关。

Answer 4

当您只有很少的唯一值时，哈希（如果您使用哈希表）对于许多条目将是相同的并且不会提供任何加速。使用 ab 树，该范围内的许多条目将非常小。基本上，您遇到非唯一值时，您必须返回更多条目作为结果或使用更多条件来搜索数据库
由于保证主键具有所有唯一值，因此通常会对其进行索引
一个很好的例子是考虑最坏的情况在所有值都相同的情况下，在 b 树或哈希表中，通过索引数据不会获得性能优势