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

Question

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

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

Answer 1

首先，您需要了解列索引的工作原理。简单来说就是，

an ordered list of all possible values in the given column with a pointer back to the actual record in the database.

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

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

Ike Smith 4783 Random Ave. Seattle, WA 98117

由于电话簿是由 last name 订购的，我们只需要转到 S , 然后是 m , 然后是 i等，直到我们找到 Smith .并且(希望如此)在 Smith 下只有几条记录。所以我们很快就能找到我们想要的那个。

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

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

如果电话簿是由 zip code 订购的(一个不太常见的变量)，那么您可能会发现自己只搜索驻留在 98117 上的 18,623 条记录.

此外，真正的电话簿通常类似于复合索引:不是仅按单个列排序(即 last name )，结果集中的值然后按另一列排序(例如 first name )，并且然后是另一个(middle name？)，这样搜索就可以在每一步都以亚线性方式完成，直到找到所需的记录。它基本上是索引中的索引，即使第一列不是那么常见，与第二列的组合提供了足够具体的标准，只需要线性搜索一小部分记录。