为什么B-Tree mysql中基数越高越好？

Question

我研究了一些地方。他们说：更高的基数可以减少搜索深度。为什么？

我很好奇如果有许多相同的值，B 树会是什么样子？

我期待有关如何创建高基数和低基数的 b 树的详细信息

Answer 1

让我们以这个拥有一百万行的

customers

表为例。它有以下列：

customer_id -- Primary Key 
age     -- has index idx_age(age,name)
gender  -- has index idx_gender(gender,name)
name    -- has no index

如果我们必须使用前三列之一的索引来验证特定名称是否存在，哪个更快？

customer_id： 当然，customer_id 是基数最高的 PK，加上搜索条件

where customer_id=112233 and name='terry'

就能立即得到想要的结果，因为 MySQL 只需要检查一行，就可以轻松地在 100 万行中定位到由于顺序有序，PK 已排好队。

年龄： 对于一个有 100 万行的表，假设年龄范围从 16 到 85 并且均匀分布，那么使用索引 idx_age 的搜索条件

where age=33 and name='terry'

理论上将有机会检查（1/70*1000000），即14286 行。

性别： 如果前面的 1/70*1000000 还不够糟糕的话，基数低得多的性别肯定会破坏性能。更糟糕的是，如果 99% 的顾客是男性，那么使用索引 idx_gender 的搜索条件

where gender='male' and name='terry'

将准备检查 (99%*1000000) 行，这将是最后一根稻草。

结论，对于给定的索引，较高的基数使搜索更容易。有时，如果索引的基数太低，即使该索引覆盖了搜索条件，系统也可能会执行表扫描。