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

Question

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

从我对B树结构的不太了解,我认为较低的基数意味着索引的存储效率更好,因为父节点较少.而更高的基数意味着存储效率更低,但读取性能更快,因为它必须通过较少的分支导航才能获得所需的任何数据,以缩小查询的行数.

(注意 - "低"对"高",我并不是说例如100万对比99万对于1亿行表.我的意思是更像是9000万对比9500万)

我的理解是否正确？

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

Answer 1

而更高的基数意味着存储效率更低,但读取性能更快,因为它必须通过较少的分支导航才能获得所需的任何数据,以缩小查询的行数.

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

要处理这样的查询:

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

,列基数不会影响读取性能.

基数如何影响写入性能？

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

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

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

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

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