谈谈mysql索引实现-B+ Tree | 并发笔记

本文记录学习mysql索引时，了解到一系列知识点。先从二叉树，到平衡二叉树，再到多路平衡树(B-Tree)，最后到加强版多路平衡查找树(B+Tree)，也就是Mysql默认使用的索引结构。分别解析各自的优缺点。以及最后为什么Mysql选择B+Tree。最后总结对日常开发的影响。

树，这种数据结构诞生的原因，想必都说腻了。也就是，当你在一堆数据中要查询某个值的时候，你是不是得去遍历所有数据，找到你要的那一个，对不对。当你数据量很大的时候，遍历的成本是非常高。假如你要从一百万个数值中查找你要的值，你有可能就得比较一百万次。那么这个时候树的结构就诞生了。它按照一定规则存储数据，当你查询的时候，按照一定的规则查找数据。它的时间复杂度比你直接遍历要降低数倍。

二叉查找树(Binary Search Tree)

二叉查找树，它将比当前节点小的值全部放在它的左边，当作左子树。将比当前节点大的值放在它的右边，当作右子树。那么它具有以下特性

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
左、右子树也分别为二叉排序树；

以下为一个标准的二叉查找树。
binary_search_tree
当你要查询某个节点时，二叉查找树的优势就显示出来了。比如你要查询节点14.那么查询的步骤如下：

跟根节点10比较，14>10，那么向10的右子树查询
跟节点16比较，14<16，那么向16的左子树查询
跟节点13比较，14>13，那么向13的右子树查询
跟节点14比较，14=14，查得结果

你以二叉查找树存储数据，查询节点14时，你只需比较4次，而你要是以链表的形式存储，那么你要比较总共进行10比较才可以查询到。当数据量大的时候，这种优势体现的淋漓尽致。但是二叉查找树也有它的缺点。比如当大部分数据都大于或者小于当前节点时，二叉树就夭折了。如下
binary_search_tree
那么这种情况来看，就跟遍历所有数据没有什么区别了，放在数据中，就跟全表遍历没有任何区别。

平衡二叉查找树(AVL Tree)

    上面小节讲到二叉查找树的诞生和致命的缺点，那么本小节介绍的另一种数据结构就是专门解决二叉查找树的缺点的。
    平衡二叉查找树，是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。通常都会讲到AVL树、红黑树。它们在增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
AVL Tree
    当该平衡二叉查找树，增加节点0007的时候，会进行以下步骤

从根节点查询，找到7应该插入的位置。也就是当作6的右子树
根据旋转规则，这里以5为中心，6进行左旋。重新恢复平衡。

这个时候，我们可以大大的松一口气，我们解决了二叉树致命的缺点，也减少了检索的时间复杂度，那么为什么mysql不使用这种数据结构呢？因为使用AVL树作为索引的数据结构还存在两个问题

搜索时磁盘IO次数过多
节点中存放的数据太少

第一个问题，是因为数据库中的数据，包括索引一定是存放在硬盘上的，因为数据库中数据少则几个G，多则几个T，这么大的数据不可能存放在内存中，所以存在硬盘中。那么问题就出来了，比较的操作，不可能在硬盘上进行，只能在内存中计算，那么当你要找到节点0003的时候，是不是最少要进行三次IO读取。当总共7个节点的时候，就需要3次的IO读写。当你的数据达到700W的时候，IO次数就很恐怖，而IO读取的效率是非常低效的。
第二问题，怎么理解。先要普及另一个知识点，当你的操作系统去读取数据时候，一定是以页为单位去读取的。它不可能根据你要读多少就读多少。一页的大小是4K，当然你可以一次读取4页就是16K的数据。那么回到正题，你觉得每个节点存放了两个子树的地址、自己本身的值、以及其他列的数据所在的地址。足以填满4K的大小吗？肯定是不行的。那么我辛辛苦苦加载一页的数据到内存中，只得到了几十byte的数据。特别是在mysql中，页大小定义是16K。那么肯定是不合适的。

多路平衡查找树(Balanced Tree、B Tree)

    B树是一种绝对平衡的树，它从当前节点，到它所有的叶子节点，深度都是相等的。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树这种数据结构非常适合用来描述外部存储。
    先感受以下的多路平衡查找树
Balanced Tree
    多路平衡查找树，怎么理解这个路字。回到上一小节把平衡二叉查找树的叉字换成路字，就可以很明了的理解多路平衡查找树了。
    多路平衡查找树，它的每个节点都存储多个关键字。它每两个相邻的关键字表示的是一个区间，最末端的两个关键字，表示到无穷的区间。那么可以推测，当前节点的路数=它的关键字+1.
    在以上多路平衡查找树中，当需要查找id为9对应的数据，它的查询步骤则是

将根节点加载到内存中并比较，9比8大，则向8的右边查找
将节点10加载到内存中并比较，9比10小，则向左边查找
这时找到节点9，找到节点9对应数据区。完成查询。

    那么关键字的个数怎么确定，在mysql中，有一个参数去设置它的页大小的。假如你就设置的是16K，那么一起计算以下，id为int类型（4byte）+关键字对应的子节点引用（假设4byte）+对应存放的数据区（假设8byte）。那么一个关键字是不是就占用16byte的位置，从理论上来说16K就可以存储1000个关键字，这其中不包括磁盘碎片，乱七八糟的因素。这里又引发另一个思考，也就是说为什么定义字段长度的时候，应该定义它合适的长度就行了。不要过大。当你定义过大的长度，也就是以上公式的除数变大，那么树的深度就变高。
    回看平衡二叉查找树的两个缺点是不是都得到了解决。磁盘IO次数过多，是否因为树的深度变矮使得次数降低。每个节点存储的数据太少，是不是通过多关键字得到了解决，每加载一页数据，我都能到我理想的一个数据。所以数据库级别都使用它来作为索引数据结构，它对磁盘的索引是有天然的优势的。
    回过头来看，我们有说它是一个绝对平衡的树，那么它是怎么保证的呢？以以下树来举例（路数最多为3），插入节点13
Balanced Tree

它会找到13可以插入的位置，也就是12的右边
但是此时，它违背了上面说的约定，最后的节点它的路数会有4条，这时他会分裂，将12分裂到父节点。完成插入。

    从上面步骤来，当分裂到父节点，使得父节点也不满足的时候，就会再往上分裂，那么在你插入时候就会使索引结构发生巨大的变化，这也就是为什么有的架构师会对你说，某些经常修改的字段、不常使用的字段不建议使用索引。
    重新思考一下，上面的结构update怎么操作。update是分解成delete+insert操作。
    多路平衡查找树，我们已经讲清楚了，那么mysql还不使用它，还要自己搞一个B+ Tree呢？

加强版多路平衡查找树(B+ Tree)

B+ Tree属于B Tree的一个变种结构，它拥有以下特征

节点关键字搜索采用闭合区间，关键字=路数
非叶子节点，不保存数据相关信息，只保存关键字和子节点的引用
关键字对应的数据保存在叶子节点中
叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系。形成一个天然有序的链表

感受一下它的结构
Balanced+ Tree
当他查询数据1时，执行的步骤是

加载根节点，匹配到1，此时它不会停留
继续加载下一节点，匹配到1，也不会停留
一直到叶子节点，因为它的数据保存在叶子节点

那么为什么要这样设计呢？它会带来什么好处呢？

B+ Tree是B Tree的变种，它拥有B Tree的优势
B+ Tree的扫库、扫表的能力更强
B+ Tree的磁盘读写能力更强
B+ Tree排序能力更强
B+ Tree查询效率更稳定

    第一点，就是都能解决磁盘IO次数过多，存储的数据太少。
    第二点，那B Tree来说，当你要基于索引的全表查询，是不是得遍历整棵树，因为数据区散落在各个节点。而B+ Tree，只需要遍历叶子节点。
    第三点，怎么理解，之前算B Tree每一个节点能保存多少个关键字的时候。算到每一节点都要保存8byte的数据区。而B+ Tree的节点不用保存数据区，是不是每个节点能保存的关键字也就却多。
    第四点，是因为叶子节点形成了一个天然的有序链表
    第五点，每次查询都会查询叶子节点，所以它的搜索时间复杂度是一样的。但是有人说，这样的话，那么B Tree的查询效率应该要比B+ Tree快，因为B Tree在第一个节点搜索到了就直接返回了。查询效率这就要看各位的理解了，上面的说法没错，但是B+ Tree不用保存数据区，IO的次数减少了，也会节省效率。

mysql的B+ Tree 具体落地

登陆mysql服务，查询数据保存位置

mysql> show variables like 'datadir';

+---------------+-----------------------------------------+
| Variable_name | Value                                   |
+---------------+-----------------------------------------+
| datadir       | D:\Program Files (x86)\MySQL\Data\Data\ |
+---------------+-----------------------------------------+
1 row in set, 1 warning (0.37 sec)

在这个目录下，以你的数据名字命名的文件夹。进去看到有以表名字开头文件。

innodb，以frm或ibd结尾的文件，frm保存表的结构，每一个字段结构等信息。idb保存是数据和索引文件
myisam，以frm、MYI、MYD，frm保存表的结构，MYI保存索引，MYD保存数据。

    在myisam引擎中，当这个表有多个索引，比如id列和name列都有索引，那么它就是维护了同级别的两颗B+树，每个树的叶子节点的数据区都保存磁盘地址指向MYD中的记录。
    而在innodb中，由于索引和数据保存在一个文件，所以我们猜测它的数据和索引放在一起。那么多个索引结构的时候，它到底怎么把数据和索引放在一起呢？这是引入一个新概念，innodb是以主键索引来组织数据的存储。，如下图所示
mysq balanced+ Tree
    此时我再建一个name字段的索引，这个name字段的叶子节点中保存的是对应的主键的值。也就是说在innodb中，分主索引和辅助索引，主索引组织数据存储，辅助索引引用主索引。也就是我们常说的聚集索引，数据库表行中数据的物理顺序与逻辑（索引）顺序相同。
    innodb这样设计有什么好处？为什么不直接保存数据的地址？因为保存主键，在主键索引发生结构变化（分裂、合并）时，他的值是不变，但是它的磁盘地址是会变的，如果保存地址的话，那么还得去维护辅助索引的引用地址。

索引的几大原则

在百度上，或者是一些大佬总结的经验，他们有的是对的，有的是不那么准确的，那么本节我们希望可以在原理上得到验证。

列的离散型

    离散型计算公式：count(distinct col)/count(col)，就是某一列去重后的数量除以它的总数，就是离散型，这个值越大，离散性越好，选择性就越好。
    举个例子，用性别这一列作为索引，这一列离散型差，1表示男，2表示女。有以下树结构
mysq balanced+ Tree
    在查询数据1时，和根节点比较，往左查询，到了第二节点的时候，懵逼了，它是不是得把所有得路数都得遍历一次。所以说它选择性差。而且在以前得老师有说过，当列的离散型小于0.15，就会强制全表扫描。

最左匹配原则

对索引的关键字做比较时，一定是从左往右进行比较的，且不可跳过。比如果当前节点为’abc’，要比较的字符为’adc’，当匹配到第二个字符时，d大于b，那么走右边。

联合索引

联合索引就是由多个列组成的索引，把单列索引理解成特殊的联合索引。相当于说，联合索引的树的每个节点的关键字，是由两个列拼接在一起的。比如果name和phone组成联合索引，那么它存储的关键字就是，jack,13838387438

基于最左匹配原则和联合索引原理，我们有得出一个结论，区别度大的列要放在联合索引前面，是不是都听过这样一句话，那么现在是不是可以理解了。

覆盖索引

如果查询的列，通过索引项的信息就可以直接返回，那么该索引称为该查询sql的覆盖索引。
为什么会有这个概念，是因为它如果在索引的结构树上就有你要查询的列，那么它就不需要去数据区扫描，大大的减少查询效率。这就是老程序员为什么跟你念，尽量不要使用select *。

练习

where条件中，like ‘abc%’、like ‘%9999%’、like ‘%999’ 三种都用不到索引？

1 2	第一中可以，后面两种用不到，归根结底是最左匹配原则。但是第一种如果离散性太低，也不会使用索引。

where条件中，not in 和<>无法使用索引，对吗？
select * from user where concat(name, ‘1’) = ‘far1’
1
函数的结果无法预料，则不会使用索引

考虑一下下面情况，是否属于正确操作？

# 经常查询的sql
select * from user where name = ?;
select * from user where name = ? and phone = ?;

# 那么建以下索引
create index IDX_NAME_IN_USER on user(name);
create index IDX_NAME_PHONE_IN_USER on user(name, phone);

基于最左匹配原则，第一条索引属于冗余索引，如果用其他的扫描工具也会给你报出警告的。