23

假设您有一个包含 1 亿行的 MySQL 5.0 MyISAM 表，在两个整数列上有一个索引（主键除外）。

从我对B树结构的理解来看，我认为较低的基数意味着索引的存储效率更好，因为父节点较少。而更高的基数意味着存储效率更低，但读取性能更快，因为它必须通过更少的分支导航以获取它正在寻找的任何数据以缩小查询的行数。

（注意 - “低”与“高”，我并不是指例如 100 万与 9900 万对于 1 亿行表。我的意思是更像 9000 万与 9500 万）

我的理解正确吗？

相关问题 - 基数如何影响写入性能？

4

1 回答 1

34

而更高的基数意味着存储效率更低，但读取性能更快，因为它必须通过更少的分支导航以获取它正在寻找的任何数据以缩小查询的行数。

更高的基数意味着更好的读取性能，因为根据定义，要读取的记录更少。

要处理这样的查询：

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue

，引擎应该执行以下步骤：

  1. 找到满足条件的第一个条目。

    这是B-Tree从根条目开始遍历 , 完成的。

    在整个页面中，通过以下B-Tree链接进行搜索；在一个页面中，搜索是使用二分搜索执行的（除非您的键被压缩，在这种情况下它是线性搜索）。

    该算法对于高基数列和低基数列的效率相同。在这些列表中找到第一个3（而不是 any ）：3

    1  2  3  4  5  6  7  8  9  10

3  3  3  3  3  3  3  3  4  4

    需要相同O(log(n))的步骤。

  2. 遍历索引直到键值改变。当然，这需要线性时间：您拥有的记录越多，您需要遍历的越多。

如果只需要第一条记录：

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue
LIMIT 1

，列基数不影响读取性能。

基数如何影响写入性能？

每个索引键都有一个隐藏的附加值：一个记录指针。这就是索引的全部意义：您需要知道它指向哪条记录。

由于根据定义，记录指针是唯一的，因此每个索引键也是唯一的。共享相同键值的索引条目按记录指针排序。

这是为了使索引可维护：如果您删除一条记录，其索引列的值由一百万条其他记录共享，则相应的索引记录也应该被删除。但是整百万条索引记录并没有被查看：相反，记录指针被用作附加的搜索条件。

每个索引键实际上都是唯一的（即使您没有将索引定义为唯一的），因此具有可能的最大基数。

所以你的问题的答案是：不，列基数不会影响索引写入性能。

于 2010-04-08T10:15:30.580 回答