一文带你深入理解Mysql索引底层数据结构与算法

理解索引的特性

• 索引是帮助Mysql高效获取数据排好序的数据结构
• 索引是存储在文件里面的

索引的各种存储结构及优缺点

首先看一下,在数据库没有加索引的情况下,SQL中的where语句是如何查找目标记录的,首先看到下图的Col2字段,如果我们要查找where col2 = 89的记录，我们在没有加索引的情况下,数据库默认会从上往下按顺序查找记录,那么将会查找5次才能查到数据,如果对Col2字段加上索引之后,假设使用最简单的二叉树作为索引存储，那么带条件查询的话,就只需要查询2次即可查到了,效率有明显的提升

二叉树

二叉树的特点

• 至少有一个节点(根节点)
• 每个节点最多有两颗子树，即每个节点的度小于3。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

优点: 二叉树是一种比顺序结构更加高效地查找目标元素的结构，它可以从第一个父节点开始跟目标元素值比较，如果相等则返回当前节点，如果目标元素值小于当前节点，则移动到左侧子节点进行比较，大于的情况则移动到右侧子节点进行比较，反复进行操作最终移动到目标元素节点位置。

缺点: 在大部分情况下，我们设计索引时都会在表中提供一个自增整形字段作为建立索引的列，在这种场景下使用二叉树的结构会导致我们的索引总是添加到右侧，在查找记录时跟没加索引的情况是一样的,如下图

红黑树

红黑树是一种自平衡二叉搜索树（BST），且红黑树节点遵循以下规则：

• 每个节点只能是红色或黑色
• 根节点肯定是黑色的
• 红色节点的父或子节点都必然是黑色的(两个红色的节点不会相连)
• 任一节点到其所有后代NULL节点的每条路径都具有相同数量的黑色节点
• 每个Null节点都是黑色的

优点: 红黑树也叫平衡二叉树，它不仅继承了二叉树的优点，而且解决了上面二叉树遇到的自增整形索引的问题，从下面的动态图中可以看出红黑树会走动对结构进行调整，始终保证`左子节点数 < 父节点数 < 右子节点数的规则。

缺点: 在数据量大的时候，深度也很大。从图中可以看出每个父节点只能存在两个子节点，如果我们有很多数据，那么树的深度依然会很大，可能就会超过十几二十层以上，对我们的磁盘寻址不利，依然会花费很多时间查找。

Hash

优点： 对数据进行Hash（散列）运算，主流的Hash算法有MD5、SHA256等等，然后将哈希结果作为文件指针可以从索引文件中获得数据的文件指针，再到数据文件中获取到数据，按照这样的设计，我们在查找where Col2 = 22的记录时只需要对22做哈希运算得到该索引所对应那行数据的文件指针，从而在MySQL的数据文件中定位到目标记录，查询效率非常高。很多时候Hash索引要比B+树索引更高效,但是仅能满足 "=" 或 "IN" 不支持范围查询(因为Hash冲突问题)

缺点： 无法解决范围查询（Range）的场景，比如 select count(id) from sus_user where id >10；因此Hash这种索引结构只能针对字段名=目标值的场景使用。 不适合模糊查询（like）的场景。

B-Tree

既然红黑树存在缺点，那么我们可以在红黑树的基础上构思一种新的储存结构。解决的思路也很简单，既然觉得树的深度太长，就只需要适当地增加每个树节点能存储的数据个数即可，但是数据个数也必须要设定一个合理的阈值，不然一个节点数据个数过多会产生多余的消耗。 按照这样的思路，我们先来了解下关于B-Tree的一些知识点：

• 度(Degree)-节点的数据存储个数，每个树节点中数据个数大于 15/16*Degree（未验证） 时会自动分裂，调整结构
• 叶节点具有相同的深度，左子树跟右子树的深度一致
• 叶节点的指针为空
• 节点中的数据key从左到右递增排列

树节点结构： 在这里需要说明下的是，BTree的结构里每个节点包含了索引值和表记录的信息，我们可以按照Map集合这样理解：key=索引，value=表记录，如下图所示：

优点： BTree的结构可以弥补红黑树的缺点，解决数据量过大时整棵树的深度过长的问题。相同数量的数据只需要更少的层，相同深度的树可以存储更多的数据，查找的效率自然会更高。

缺点： 从上面得知，在查询单条数据是非常快的。但如果范围查的话，BTree结构每次都要从根节点查询一遍，效率会有所降低，因此在实际应用中采用的是另一种BTree的变种B+Tree（B+树）。

B+Tree

• 非叶子节点不存储data值,只存储冗余索引，可以放更多索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接、提高区间访问的性能

运行原理:假如我要查找id为30的数据

1.首先会再根目录进行查找,将该数据页加载到内存通过二分查找等其他合适的算法,发现30是在15-56之间,则进入第二数据页 2.进入之后,又会将该数据页加载到内存比较 3.最后到了叶子节点,加载到内存查找到了30,直接返回

如果要查询id>30的数据

1.会先定位30的数据 2.因为叶子节点的指针链路是排好序的,所以会直接根据30的索引值,往右的所有值查询出来

为什么mysql使用b+树而不使用b树

影响树的查询效率是根据树高度决定的,树越高查询越慢 树的每个节点的大小大概为16kb 1.b+树非叶子节点,只存索引key,而这个key一般只会占用8个字节,那么就意味着,千万级别的数据,我存冗余索引key,也就可以越多,且高度并不会高 2.b树,非叶子节点和叶子节点,都会存储key和data值,这样的话,每个非叶子节点能够存储的容量就非常少,树的节点就会层层叠高,效率也就很慢 总结: 1.b+树,只有叶子节点存储数据,非叶子节点就意味能够存储更多的key,树的高度就越低,查询的效率就越高 2.b树,叶子和非叶子节点都存储数据,非叶子节点能够存储的数据就越少,树的高度就越高,查询的效率就越低 当节点存满之后,就会对该节点进行分裂,然后增加到下一级节点存储

B+Tree通过把data不放在非叶子节点来增加度（小节点），一般会一百个以上使得深度是3~5，从而减少查询次数。并且，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找，而不再从上面节点往下一个个找。

结论：B+Tree 既减少查询次数又提供了很好的范围查询

InnoDB和MyISAM的区别

MyISAM引擎

mylsam索引文件和数据文件是分离的(非聚集索引:索引和data值是分开的),并且主键索引和辅助索引（二级索引）的存储方式是一样的

.frm文件是存储:该表的数据表结构相关信息 .MYD文件是存储:该表的数据内容 .MYI文件是存储:该表的索引数据

引擎原理:

1.col1(15值)存储的数据,会以b+树的格式进行存储myd里面 2.当查询某条数据,会到叶子节点找到相应索引值(15的索引值为0x07) 其实就是在myi里面找 3.在myi文件中找到索引值后,MyISAM引擎会根据索引值,到myd文件里面找到相应位置的值

主键索引

联合索引

InnoDB引擎

• 数据文件本身就是索引文件
• 表数据文件本身就是按B+Tree组织的一个索引结构文件
• 聚集索引-叶节点包含了完整的数据记录

Innodb索引文件(聚集索引:索引和data值是在一起的),并且主键索引和二级索引储存方式有所不同，如图所示，二级索引的叶子节点不储存数据，仅储存主键ID。

.frm文件是存储:该表的数据表结构相关信息 .ibd文件是存储:该表的索引和数据是存在一起的

为什么建议InnoDB表必须建主键,并且推荐使用整形的自增主键

1.首先，为了满足MySQL的索引数据结构B+树的特性，必须要有索引作为主键，可以有效提高查询效率，因此InnoDB必须要有主键。如果不手动指定主键，InnoDB会从插入的数据中找出不重复的一列作为主键索引，如果没找到不重复的一列，这时候InnoDB会选择内置的ROWID作为主键，写入顺序和ROWID增长顺序一致；其次，索引的数据类型是整型，一方面整型占有的磁盘空间或内存空间相比字符串更少，另一方面整型比较比字符串比较更快速，字符串比较是先转换为ASCII码，然后再进行比较的。 最后，B+树本质是多路多叉树，如果主键索引不是自增的，那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡，影响数据插入的效率，如果是自增主键，只用在尾节点做增加就可以。

2.为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间) 主键索引和非主键索引维护各自的B+树结构，当插入的数据的时候，由于数据只有一份，通过非主键索引获取到主键值，然后再去主键索引的B+树数据结构中找到对应的行数据，节省了内存空间； 如果非主键索引的叶子节点也存储一份数据，如果通过非主键索引插入数据，那么要向主键索引对应的行数据进行同步，那么会带来数据一致性问题。可以通过事务的方式解决，我们都知道使用事务后，就会对性能有所消耗。

联合索引底层存储结构

定义联合索引(员工级别，员工姓名，员工出生年月)，将联合索引按照索引顺序放入节点中，新插入节点时，先按照联合索引中的员工级别比较，如果相同会按照是员工姓名比较，如果员工级别和员工姓名都相同 最后是员工的出生年月比较。可以从图中从上到下，从左到右看，第一个B+树的节点 是通过联合索引的员工级别比较的，第二个节点是 员工级别相同，会按照员工姓名比较，第三个节点是 员工级别和员工姓名都相同，会按照员工出生年月比较。

例如:

联合索引:设置的顺序是:emp_no,title,from_date这个三个字段

explain SELECT * from employee where emp_no = '10001' and title = 'xxx' and from_date = '2018-10-01 11:29:51'   ====会执行联合索引
explain SELECT * from employee where title = 'sss'           ====不会执行联合索引
explain SELECT * from employee where emp_no > '10003' and title = 'eeee'   ====不会执行联合索引

从上面的例子中可以知道,只会第一条才会执行联合索引,那是为什么呢 这就回到本文第一句话,索引是获取数据排好序的数据结构,所以我们再做查询的时候,肯定会先根据emp_no排序,再title排序,最后再from_date排序

例如:SELECT * from employee where title = 'sss' 底层都还没有对emp_no排序呢,就直接查title了，是肯定不行的啦,因为并未排好序呢,所以不会走索引

由此即可得出最左前缀原理

使用联合索引时,联合索引定义的顺序将会影响到最终查询索引的使用情况和结果,例如定义了联合索引(a,b,c) ,mysql会先从左边的列优先匹配,如果最左边定义的列都没有被使用到,在未使用覆盖索引的情况下,mysql就会默认执行全表扫描。

联合索引底层数据结构思考? mysql会优先以联合索引的第一列开始匹配,此后才会匹配下一列,如果不指定第一列匹配的值,那么也就无法知道下一步要查询那个节点（可以联想B+树的数据结构,第一列匹配到值后,会进行一次数据结构的排序筛选,得出排好序的数据结构,在进行匹配下一列,得出最终结果,那么如果直接跳过第一列,匹配第二列,b+树会无法找到排好序的数据结构结果,就会进行全表扫描） 另外一种情况,如果遇到 ">"、"<"、"between"等这样的范围查询,那么b+树也就无法对下一列进行等值匹配了（可以联想到,就算建立了索引,因为是范围查询,mysql会认为走索引会导致回表查询过多,导致效率并不会比全表扫描快,最终mysql就会走全表扫描）