因此,大多数数据库专家表示,相对于表的大小,在具有非常少的唯一值的列上创建索引是无效的.
根据数据库内部的工作方式(我知道大多数数据库使用B树存储索引),为什么具有很少唯一值的B-Tree会使搜索效率低下？
rae*_*ae1 16
首先,您需要了解列上的索引是如何工作的.简单来说,它只不过是,
给定列中所有可能值的有序列表,指针返回数据库中的实际记录.
由于它是有序的,因此可以使用二进制搜索来代替它,而不是线性搜索,这可以提高大型数据集的性能.
想象一下,你的索引作为电话簿按列排序,说last name; 但是在具有类似记录的记录集中,记录last name没有共同的模式或有意义的顺序:它们是纯粹随机的.并说我们需要搜索此记录:
艾克史密斯4783随机大道 西雅图,WA 98117
由于电话簿是按顺序排序的last name,我们只需要去S,然后再去m,然后i等,直到找到Smith.并且(希望)只有几个记录,Smith所以我们很快找到了我们想要的那个.
现在,想象一下您订购的电话簿city而不是last name.在与给定匹配的记录中,city没有特定的顺序.所以我们再次尝试搜索.然而,一旦我们发现Seattle(使用极其复杂的二分搜索),我们就会留下接近620,778条记录,我们必须按顺序检查这些记录,因为它们完全随机排序.我们无法检查我们想要的记录的每一个条目.
当您使用非常常见的列作为索引的基础时会发生这种情况:二进制搜索返回一组非常大的可能记录,数据库无法在初始索引列值之外做出任何假设,因此需要在结果集中按顺序检查匹配记录.
如果电话簿是由zip code(一个不太常见的变量)排序,那么你可能会发现自己只搜索了18,623个记录98117.
此外,真正的电话簿通常类似于复合索引:而不是仅按单列排序(即last name),结果集中的值然后由另一列(比如说first name)排序,然后另一列(middle name？)排序,因此搜索可以在每一步都线性完成,直到找到所需的记录.它基本上是索引中的索引,即使第一列不常见,与第二列的组合提供了足够的特定条件,只需要线性搜索一小组记录.
当您的唯一值非常少时，许多条目的散列（如果您使用散列表）将是相同的，并且不会提供任何加速。对于 ab 树，范围内的许多条目将非常小。基本上，您遇到非唯一值时，您必须返回更多条目作为结果，或者使用更多条件来搜索数据库
由于主键保证具有所有唯一值，因此通常会对其进行索引
一个很好的例子是考虑最坏的情况在所有值都相同的情况下，在 b 树或哈希表中，通过对数据建立索引不会获得任何性能优势