大水怪

一只专注技术的水怪

0%

一个关于二级索引的优化思路

一个今年春招至今没解决的疑问(目前已经解决!感谢大佬们的解答和肯定!)

开端

以下讨论范围是以B+树为数据结构的索引

并且不考虑二级索引关于事务版本的的字段可见性问题

对于聚簇索引,非叶子节点的记录包括主键列,而叶子节点中的记录包括全部数据列(包括主键)

对于自己建立的二级索引(辅助索引),非叶子节点的记录包括索引列,而叶子节点中的记录包括主键以及索引列

接下来我们只考虑除主键列外的其他列

对比可以看出,聚簇索引的与叶子节点与非叶子节点记录明显是不对等的,叶子节点的记录包含比非叶子节点记录更多的列。

而二级索引非叶子节点包含的记录的列则与叶子节点中记录所包含的列一致。

不难看出,除了聚簇索引外建立的索引都只能属于后者。

那么考虑下面这种情况

有一个表 t_bl 有以下字段 (id,a,b)

1
select a,b from t_bl where a = "XXX";

这种情况下b字段并不作为检索的依据,但却需要在检索结果中出现。

那么有以下两种索引建立方案

  1. 建立 a 字段的索引

    优点:使得索引的每个节点都减少了存储 b 字段的空间开销。

    缺点:返回查询结果需要通过二级索引的主键 id 回表到聚簇索引上查询 b 字段的值,影响查询性能。

  2. 建立 a,b 字段的联合索引

    优点:可以用到覆盖索引,减少回表,提高查询效率。

    缺点:使得二级索引中的每个非节点都增加了存储 b 字段的不必要的空间开销(因为b字段并不是检索依据)。

    9.16补充:这种非叶子节点上的索引数据空间的额外开销还会导致扇出的降低

那么为什么不提供一种机制,使得用户能建立非叶子节点与叶子节点不对等的索引?

比如在本例中,用户更好的选择其实是建立一个非叶子节点存储 a 字段,而叶子节点存储 a,b 两个字段的索引

思考

innodb B+树索引页面大小默认是16kb,索引单位越小扇出越大。

一个三层,扇出为100的 B+ 树,按照页面为单位,第三层假设10000个页,那么第二层就是100个页,第一层为1个页。

因此实际上叶子节点才是索引结构的主要空间开销,导致这个优化的收益并不是很高。

大佬提供的思路

在此感谢公众号「一树一溪」大佬提供的思路

这位大佬专门写 MySQL 源码文章,感兴趣的朋友,可以微信搜索关注

  1. 代码实现复杂度更高,如果支持这种非对称索引,相当于 B+ 树多了另一种索引结构,需要兼容。
  2. 支持这种非对称结构并不会带来很大的好处,因为少量回表并不会对性能有太大影响,只要把回表次数控制在一定范围内就没问题。
  3. 如果为了减少回表建了很多这种非对称索引,在计算执行成本的时候,这些索引都要考虑进去的,在查询优化阶段反而会增加花费的时间。

根据 Bill Karwin(《SQL反模式》作者 )的回答

目前Microsoft SQL Server已经实现了这个功能

https://docs.microsoft.com/en-us/sql/relational-databases/indexes/create-indexes-with-included-columns?view=sql-server-ver16

而InnoDB 目前还没有实现这个可行的优化,猜想应该是因为优先级不高。

如果有其他思路,欢迎评论交流!