MySQL 索引基数 - 性能与存储效率

Question

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

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

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

我的理解正确吗？

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

Answer 1

Whereas a higher cardinality means less efficient storage, but faster read performance, because it has to navigate through less branches to get to whatever data it is looking for to narrow down the rows for the query.

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

处理这样的查询:

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue

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

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

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

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

   该算法对于高基数列和低基数列的效率相同。在这些列表中找到第一个 3(而不是任何 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

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

How does cardinality affect write performance?

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

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

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

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

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