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

Question

假设您有一个拥有一亿条记录的MySQL 5.0 MyISAM表格，并且在两个整数列中除主键以外还有一个索引。

从我对B树结构的理解来看，我认为较低基数意味着索引的存储效率更高，因为有较少的父节点。而较高基数意味着存储不太高效，但读取性能更快，因为它需要浏览的分支较少，以定位查询所需的数据并缩小查询范围。

(注意 - 通过“低”与“高”，我并不是指例如对于一张一亿行的表格，1百万和99百万之间的差异。我的意思更像是90百万和95百万之间的差异)

我的理解正确吗?

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

- Sean

---

我不确定你在这里所说的“基数”是什么意思。你是指B树（实际上可能是B+树）结构使用的块大小吗？ - jemfinch

基数，即唯一值的数量。基数越高，唯一值就越多。 - Sean

例如，我找到了一篇文章，说较高的基数将导致更好的读取性能。但是我在这方面找不到很多文章，而且这只是一篇随意的博客文章，所以我真的不确定。 http://www.databasedesign-resource.com/mysql-tuning.html - Sean

同样在那篇文章中，对于高基数列的索引建议使用1列索引。我的问题是关于多列索引，这可能会对幕后发生的事情产生不同的影响。 - Sean

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)) 步骤。

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

如果您只需要第一条记录：

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue
LIMIT 1

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

基数如何影响写入性能？

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

由于记录指针本质上是唯一的，因此每个索引键也是唯一的。具有相同键值的索引条目由记录指针排序。

这是为了使索引可维护：如果删除具有一百万个其他记录共享的索引列值的记录，则应该删除相应的索引记录。但是，并不会遍历整个百万级别的索引记录：而是使用记录指针作为附加的搜索条件。

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

因此，答案是：不，列的基数不影响索引写入性能。

- Quassnoi

---

非常感谢您提供如此详细的答案。我的问题与多列索引有关，但您的示例是针对单列索引的。这会改变什么吗？此外，存储效率对我也很重要。对于多列索引，我认为索引的第一列（左侧）具有较高的基数意味着更多的存储空间，而将基数较低的列放在左侧则相反。左侧的基数越高，意味着有更多的父节点，这是否会影响存储空间？再次感谢 :) - Sean

@Sean：这也适用于复合索引。如果启用了键压缩（在MyISAM中），低基数列甚至可以节省一些空间（但它们意味着在页面中进行线性搜索，因此这是一个权衡的问题）。父节点的数量完全取决于可以放入页面中的记录数。 - Quassnoi

@Quassnoi - 随着MyISAM的消失，“键压缩”点不再有效。在InnoDB中，考虑复合索引列的基数没有任何好的理由。 - Rick James