mysql索引结构与深分页优化

山行AI

发布于 2020-03-26 17:24:48

1.5K0

发布于 2020-03-26 17:24:48

文章被收录于专栏：山行AI

最近面试中总是会被问到mysql中的一些索引结构及一些sql优化的内容，这里针对自己看过的一些博客和关于mysql的书籍对mysql索引相关的内容进行一个总结。

B树索引结构

B- 树（即B树）

B-树,这里的 B 表示 balance( 平衡的意思)，B-树是一种多路自平衡的搜索树。它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。

看下它的特点：

每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;
所有键值分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
在关键字全集内做一次查找,性能逼近二分查找；

B+ 树

在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。它通过拆分叶子节点或进行旋转来维持树的平衡。

也是一种多路搜索树, 它与 B- 树的不同之处在于：

所有关键字存储在叶子节点出现，内部节点（非叶子节点）并不存储真正的 data。
为所有叶子结点增加了一个链指针。
B+树查询时间复杂度固定是logn，B-树查询复杂度最好是 O(1)。
B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
B+树更适合外部存储，也就是磁盘存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。
B-树每个节点即保存数据又保存索引，所以磁盘IO的次数很少，B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。

B树为什么更适合数据库索引

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。为什么不用Hash索引？因为hash索引要解决hash冲突的问题，它唯一匹配性能较高，但是范围查询无法处理。B树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。

由于磁盘的存取速度与内存之间效率差异比较大，为了提高效率，要尽量减少磁盘I/O，磁盘往往不是严格按需读取，而是每次都会预读，磁盘读取完需要的数据，会顺序向后读一定长度的数据放入内存。根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。当一个数据被用到时，其附近的数据也通常会马上被使用，程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此对于具有局部性的程序来说，预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

nosql

MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据，一般使用 XML 或 Json 格式来保存数据，归属于聚合型数据库(redis的key-value结构也是聚合型数据库)。MongoDB 是一种 nosql，也存储在磁盘上，被设计用在数据模型简单，性能要求高的场合，需要尽可能少地使用磁盘IO。B-树中key 和 data 域聚合在一起，查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

关系型数据库

MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。B+树可以很好的利用局部性原理，若我们访问上面B+树图中节点 key为 50，则 key 为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。B+树更适合外部存储。由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B+树单次磁盘IO的信息量大于B-树,I/O效率更高。对于关系型数据库，区间访问是常见的一种情况，B+树叶节点增加的链指针,加强了区间访问性，可使用在范围区间查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

mysql中按页存储

在操作系统的概念中，当我们往磁盘中取数据，假设要取出的数据的大小是1KB，但是操作系统并不会只取出这1kb的数据，而是会取出4KB的数据，因为操作系统的一个页表项的大小是4KB。那为什么我们只需要1KB的数据，但是操作系统要取出4KB的数据呢？这就涉及到上面的程序局部性的概念。MySQL(使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改).linux 默认页大小为4K。

可是在当一个页的数据量很大的时候，又要怎么快速查找数据呢？这就引入了目录页的概念，目录页的本质也是页，普通页中存的数据是项目数据，而目录页中存的数据是普通页的地址。对mysql数据页感兴趣的可以参考下：https://www.cnblogs.com/bdsir/p/8745553.html，这里不再过多分析。

mysql中的B+ 树索引

想要更好地理解mysql的索引结构，除了分析mysql源码和mysql社区的相关文档外，阅读mysql相关的书籍便成了首先。下面我针对<>和<<高性能mysql第四版>>中关于innodb索引的部分的分析进行如下总结。

索引类型

聚簇索引

聚簇索引，索引的叶子节点的数据就是用户所要查询的数据，所以对于有聚簇索引的列，排序查找和范围查找速度非常快（mysql的默认主键就是聚簇索引）。索引中的页通过双向链表链接，页按照主键的顺序排序，每个页中的记录也是通过双向链表进行维护的。

为什么InnoDB只有一个聚簇索引，而不将所有索引都使用聚簇索引？因为聚簇索引是将索引和数据都存放在叶子节点中，如果所有的索引都用聚簇索引，则每一个索引都将保存一份数据，会造成数据的冗余，在数据量很大的情况下，这种数据冗余是很消耗资源的。

辅助索引（非聚簇索引）

辅助索引的叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签(bookmark)。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

每张表上可以有多个辅助索引。当通过辅助索引来查找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。举例来说，如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的一个数据页。

覆盖索引

覆盖索引是非常有用的工具，查询时只需要扫描索引而无须回表。

关于覆盖索引有一个延迟关联的概念(见高性能mysql的172页)：

现在有一个仓库表tstore，它有一个多列索引(storeid,item_id)，如果mysql只需要访问这两列，就可以使用这个索引做覆盖索引。如果走了覆盖索引，那么在EXPLAIN的Extra列可以看到"Using index"的信息，这里不要和type列的"index"搞混，type列和覆盖索引毫无关系，它只是表示这个查询访问数据的方式，或者说是mysql查找行的方式或者连接方式(join type)。

那么我们看下这条查询：

select * from t_store where user_name='zs' and item_name like '%apple%';

这里索引无法覆盖该查询，有以下两个原因：

没有任何索引能覆盖这个查询。因为查询时从表中选择了所有的列，而没有任何索引覆盖了所有的列。
mysql只能在索引中做最左前缀匹配的like比较，因为它可以转换为简单的比较操作。但是如果是通配符开头的like查询，存储引擎就无法做比较匹配。这种情况下，mysql服务器只能提取数据行的值而不是索引值来做比较。

解决办法：

重写查询并巧妙地设计索引。先扩展索引至(storeid，username，item_name)，然后按如下方式查询：

select * from t_store join(select store_id from t_store where user_name='zs' and item_name like '%apple%') as t1 on(t1.store_id = t_store.store_id);

这种就是延迟关联(deferred join)，因为延迟了对列的访问。在查询的第一阶段mysql可以使用覆盖索引，在from子句的子查询中找到匹配的storeid，然后根据storeid的值在外层查询匹配获取需要的所有列值。虽然无法使用索引覆盖整个查询，总比完全无法利用索引覆盖要好。

比如说有下面三个数据集：

用户A入库了30000个商品，其中商品名称包含apple的有20000个。
用户A入库了30000个商品，其中40个商品名称包含apple的。
用户A入库了50个商品，其中10个商品包含apple。

在涉及到有索引的查询时还需要考虑索引优化器的作用，查询优化器一条SQL语句的查询，可以有不同的执行方案，至于最终选择哪种方案，需要通过优化器进行选择，选择执行成本最低的方案。

mysql大数据量分页查询优化

问题

看一下这条分页sql的执行：

select * from t_store where user_name='zs' limit 300000 10;

它的查询过程为：查询到索引叶子节点数据。根据叶子节点上的主键值去聚簇索引上查询需要的全部字段值。需要查询300010次索引节点，查询300010次聚簇索引的数据，最后再将结果过滤掉前300000条，取出最后5条。MySQL耗费了大量随机I/O在查询聚簇索引的数据上，而有300000次随机I/O查询到的数据是不会出现在结果集当中的。

证实它扫描了300010个索引节点和300010个聚簇索引的数据节点的方法见：https://mp.weixin.qq.com/s/Hb5bEi-TAfZD5goNsZT1eQ

优化

sql 语句优化：

select * from t_store where store_id >= (select store_id from t_store limit 300000,1) limit 10;

它的另一种写法：

select * from t_store a join (select store_id as id from t_store limit 300000,10) b on a.id=b.id

这样处理的作用也是用延迟初始化从而利用表的覆盖索引。

除了延迟关联，还有很多其他方式来处理这种问题。比如前端加缓存、搜索，减少落到库的查询操作，使用瀑布流的方式展现数据；利用id或业务查询的实际场景比如时间列等来做个书签，最终也是使用瀑布流的方式来处理，查下一页时传入该页的起始id(索引要保证有序性)

mysql与mongodb

MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据。MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。Mysql作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。