mysql索引的数据结构,为什么用B+树不用B树 mysqlb+树索引 _生活百科

点击上方蓝色“石杉的架构笔记”，选择“设为星标”
回复“PDF”获取独家整理的学习资料！

文章插图

文章插图
分享概要

本次分享儒猿专栏《从零开始带你成为MySQL实战优化高手》中Mysql索引的内容。本次会先从一个数据页中如何存储和查询数据开始，拓展到多个数据页中查询数据，分析无索引查询时的低效率问题，然后通过页分裂过渡到主键目录以及索引页相关内容，见证一颗索引树是如何一步步生长起来的。

最后站在更高的角度看下常见的一些索引名词、索引的优缺点以及如何才能设计出更好的索引来，开始分析前我们先来思考下如下的一些面试题：

1.InnoDB的索引数据结构是什么？为什么用这种数据结构？
【mysql索引的数据结构,为什么用B+树不用B树 mysqlb+树索引】2.聚簇索引和普通索引的区别是什么？
3.什么是回表操作？它对索引有什么影响吗？
Mysql索引的B+树的生长流程如下图所示：

文章插图
2.B+索引树是如何生长的2.1 无索引时的数据查询
数据页是Mysql中数据管理的最小单元，既然我们要研究索引是如何高效查询数据的，首先我们肯定要搞清楚数据是如何存放的，数据页的结构通过上篇文章我们了解到大概是这样的：

文章插图
而数据表中的每行数据就存放在数据区中，数据区中每行数据以单向链表的方式，通过指针连接起来，如下图所示：

文章插图
同时每个数据页之间再通过双向链表的方式组织连接起来，如下图所示：

文章插图
（1）无索引时的数据查询

通过以上对数据页以及数据页内部数据结构初步的分析，现在我们就可以看下，如果说要查询某张表的某行数据会经过什么样的流程。
数据页一开始当然是存放在磁盘中的，一张表对一般会应着多个数据页，查询数据时从磁盘中依次加载数据页到InnoDB的缓冲池中，然后对缓冲池中缓存页的每行数据，通过数据页的单向链表一个一个去遍历查找，如果没有找到，那么就会顺着数据页的双向链表数据结构，依次遍历加载磁盘中的其他数据页到缓冲池中遍历查询。
大家可以看到，像上面这样的查询方式就有点傻了，因为如果恰好你要查的数据行在这张表最后一个数据页的最后一行，那岂不是所有的数据页都要被扫描一遍，然后每个数据页中也是遍历链表，整体的效果就是以O(n)的时间复杂度在遍历链表了,这样查询的性能肯定是不行的。

（2）优化数据页内查询效率-槽位
我们先把目光转移到单个数据页内的数据查询，假如说我们现在已经锁定数据就在某个数据页中了，但是我们该怎样快速的从这个数据页中找到我们想要的那行数据呢？
通过之前的分析我们可以知道，最傻的一种方式就是遍历数据页中的单向链表查询，一个节点一个节点去扫描，相对应的查询效率是肉眼可见的低。但是如果说可以像翻书一样，根据目录来减小我们查询的范围，相对应的查询效率不就上来了吗，根据这种想法，InnoDB存储引擎设计了槽位这种方式来组织数据页中的多个数据行，槽位信息存放在数据页中的数据页目录中。
槽位简单来说就是将数据页中的多个数据行分组划分，每个数据行组都找这个组中的主键值最大的那个数据行的地址作为槽位的信息，这样数据页目录中的一个个槽位不就是像是一个个目录了吗，标记好了多个数据行分组的位置信息，如下图所示：

文章插图
这下有了数据页目录中的槽位信息，此时要查询数据页中的某行数据不就很简答了，比如我们要查询主键为4的那行数据，直接通过二分法以O(logn)的时间复杂度锁定数据页目录中的槽位2，因为槽位之间都是紧密连接的，可以通过槽位2找到槽位1，从槽位1末尾开始，对分组2中的数据开始遍历，因为每个分组中的数据量都很少，此时在这么小的范围内简单遍历下就可以快速找到主键为4的那行数据，时间复杂度从之前的O(n)降低到O(logn)效率还是挺可观的。