InnnDB为什么用B+树简单介绍（六）

程序员潇然

因为InnoDB底层文件存储是用到了相关知识点，此处介绍下B+树

从头慢慢说，都是一步一步演变过来的~

部分知识点，没有什么需要解释的，贴出来相关概念

树相关概念

①节点：包含一个数据元素及若干指向子树分支的信息 。 ②节点的度：一个节点拥有子树的数目称为节点的度 。 ③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点 。 ④分支节点：也称为非终端节点，度不为零的节点称为非终端节点 。 ⑤树的度：树中所有节点的度的最大值 。 ⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。 ⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度 。 ⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树 。 ⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树 。 ⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成 。

二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树的递归定义为：

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；

左子树和右子树又同样都是二叉树；

形态

1、空二叉树 (a) 2、只有一个根节点的二叉树(b) 3、只有左子树——(c) 4、只有右子树——((d) 5、完全二叉树——(e)

特殊的二叉树

1、满二叉树：

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。

很好理解，要么没有子树，有就有2个

2、完全二叉树：

深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 。 完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 。

二叉树遍历

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

二叉查找树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

是数据结构中的一类。

在一般情况下，查询效率比链表结构要高。

递归定义：

一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树

之所以称之为查找树，是因为他查找效率高，为什么效率高？

因为本身他就有一些要求，也就是他的递归定义。

只需要中序排序，也就是左根右，递归即可，比如上图 8 ，有左子树，所以找他的左，是3，3还有子树找他的左，也就是1，没有孩子节点，下一个就是根，3，下一个是右，他有孩子，找他的左，是4 ，没有孩子节点，所以就是4，然后是根 6，接着是右 7，没有孩子节点，所以就是7，

8的左子树都遍历结束，所以到根 也就是8 ，接着右，右子树10 有孩子，所以找他的左子树，是9，没有孩子节点，所以就是9，接着是根 10，然后找右子树，是15，他有孩子节点，找左子树，是13，没有孩子节点，就是13，接着到根，是15，接下来到右，没有右子树，结束

所以结果就是：1 3 4 6 7 8 9 10 13 15

数据查询

假设，想要找到 6 的节点。

1. 和根节点比较，确定6比根节点小，所以在左子树；
2. 找到左子树之后，6 又大于 左子树的根3，所以在根3的右子树上；
3. 找到右子树之后，接着6等于根3的右子树节点，成功找到了6；

很显然，二叉查找树次数，等于所在节点的层数，这个例子中查找6，在第三层，我们查询判断了三次。

这个二叉查找树，从查询的逻辑步骤看，就是二分查找法。

查找的时间复杂度是O（logN）

特殊的二叉查找树

如上图所示，也是一个二叉查找树，完全符合定义，已经退化成了一个链表。

当想要找到6的时候，总共四层，需要比较四次，总共树的节点就是4，也就是复杂度达到了O(N）

这就得到一个结论，二叉查找树的高度决定了二叉查找树的查找效率。

所以如何能够降低树的高度？？？

图上可以直观的看到，就是树歪了，网一边偏了， 能不能让他平衡一下？不要这么偏呢？

平衡二叉树

平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

也就是在二叉查找树的基础上，增加了一个条件，叶节点高度差的绝对值不超过1，也就是控制了树的高度，不会往一边倾斜太多。

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。

查找、插入和删除在平均和最坏情况下的时间复杂度都是O（logN）。

增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。

带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。

平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

判断「平衡二叉树」的 2 个条件：

• 1. 是「二叉排序树」
• 2. 任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

2 种「旋转」方式：

左旋

• 旧根节点为新根节点的左子树
• 新根节点的左子树（如果存在）为旧根节点的右子树

右旋：

• 旧根节点为新根节点的右子树
• 新根节点的右子树（如果存在）为旧根节点的左子树

4 种「旋转」纠正类型：

1. LL 型：插入左孩子的左子树，右旋
2. RR 型：插入右孩子的右子树，左旋
3. LR 型：插入左孩子的右子树，先左旋，再右旋
4. RL 型：插入右孩子的左子树，先右旋，再左旋

本文主要是介绍一些树的相关知识点，方便后续聊B+树，不深入细节

一些在线算法网站，可以更好地学习

[Data Structure Visualization (usfca.edu)]([url=https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]

https://www.bigocheatsheet.com/

https://yangez.github.io/btree-js/

[Binary Search Tree, AVL Tree - VisuAlgo](https://visualgo.net/en/bst)

[Branch and Bound - Binary Search Tree (algorithm-visualizer.org)](https://algorithm-visualizer.org/branch-and-bound/binary-search-tree)

http://btv.melezinek.cz/binary-search-tree.html

平衡二叉树已经解决了二叉查找树左右子树倾斜严重的问题，查找、插入、删除的复杂度已经是O(logN)了，看起来效率已经很不错了

一次查找最大也就是树的高度，对于内存来说，性能已经很高了。

但是如果是磁盘文件呢？

众所周知，磁盘IO与内存IO完全不是一个数量级，那么还能否在减少一些查询次数呢？

查找的次数，最多等于树高，是不是还可以继续降低树的高度？

外查找

插入一个外查找的知识点。

在计算机中，存储器的层次结构一般分为：CPU寄存器、主存、辅存。

外部查找是指在辅助设备空间进行数据查找。

如在计算机中内存的大小是有限的， 如果要查找的数据量太大，无法全部加载到内存中，必须借助辅助存储设备的空间再进行查找。

B树的启发来源于二叉查找树，二叉查找树的特点是每个非叶子节点都只有两个孩子节点。

这种结构会造成当数据量非常大时，二叉查找树的高度非常大，搜索算法从根节点向下搜索时，需要访问的节点数会变多，如果这些节点信息存储在外存储器（磁盘）中，每访问一个节点，就相当于进行了一次I/O操作，而频繁的I/O操作会降低查询的效率。

B树是为了实现高效的磁盘存取而设计的多叉平衡搜索树，多用于数据库中。

B树（B-树）

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）B是Balance的意思。

B树的阶：

节点的最多子节点个数，也就是B树中所有节点的孩子节点数中的最大值称为B树的阶，记为M 在B树上，关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束。

一棵M阶B树(balanced tree of order M)是一棵平衡的M路搜索树。

记住这个M，下面一直在用这个值。

它或者是空树，或者是满足下列性质的树： 1、根结点至少有两个子女； 2、每个非根节点所包含的关键字个数 j 满足：ceil（m/2） - 1 <= j <= m - 1；（ceil 大于等于的最小整数） 3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：ceil （m/2） <= k <= m ； 4、所有的叶子结点都位于同一层。

在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn） 其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

如图所示，所有节点中，子节点最多的是 9 12他们的孩子节点数为3，所以是3阶，M为3。

每个非根节点所包含的关键字个数 j 满足：ceil（m/2） - 1 <= j <= m - 1；

3/2=1.5 向上取整，2是大于等于1.5的最小整数。

所以每个非根节点所包含的关键字个数，必然 2 - 1 <= j <= 3 - 1；也就是 1 <= j <= 2；

除了根节点6，其他所有节点（不包括叶子），子树个数是 2 <= j <= 3；

2个孩子有1个分割点，3个孩子有2个分割点；

简单理解就是 a,b使用一个 ,隔开；a,b,c 使用两个 , 隔开；

,(分隔符)的个数总是会比 数据(孩子)的个数少一个,也就是所谓的 k-1 个关键字 是 k个孩子的分割点;

上图中叶子结点有 5个，除了叶子结点这一层，上面两层总共有 6 2 9 12 4个关键字，5=4+1；

（n,P0,K1,P1,K2,P2,…,Kn,Pn）

又如何解释呢？一张图就说清楚了，需要记住n 表示的是关键字的个数。

不纠缠于算法细节，对比下B树与二叉树，主要差别就是 叉变多了。

叉变多了，那么这个树必然就变矮了~

因为节点个数n是固定的，转换为B树之后，一个节点不在只是一个包含关键字，另外孩子节点也可以超过2。

比如上面的那个树，看下平衡二叉树，直接生成，如下图所示，树高少了一层

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

以我们的这个例子来说少了一层，看似没有多大区别，但是还是要掌握重点，那就是对于磁盘来说，IO性能开销很大，这一层也会有很大的作用，更何况对于N更大时，查出来的层次完全不止一层。

磁盘IO与预读

磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，大概需要几ms。

这个成本是访问内存的十万倍左右；

正是由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化：预读；

每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。

因为局部预读原理说明：

当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。

一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

特点

对于B树来说，所有键值分布在整颗树中（索引值和具体data都在每个节点里）；

任何一个关键字出现且只出现在一个结点中；

搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；

前面磁盘IO提到，局部性原理，一次加载一页数据，B树的键值和数据存放在每一个节点，那么必然索引的数据不足够多，为什么不能除了叶子节点外，每层只是存放索引（关键字）数据呢？

这样势必一次可以加在进来更多的索引，因为空间是固定的，单个节点数据量少，数据个数就多，磁盘 IO 次数就可以继续减少。

而且，因为索引和数据分布在所有的节点中，对于范围查询也变的很困难。

基于种种原因，出现了优化了的B树，也就是B+树。

B+树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下: (1)每个结点至多有m个子女； (2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女； (3)有k个子女的结点必有k个关键字。 B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。

与B树对比

看一组对比图

ps：同样的数据，生成的图有区别很正常，因为与插入顺序也有关系的。

B+树非叶子结点不存储数据，所有 data 存储在叶结点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。（数据这一点图上体现不出来，记住即可）B+树相对B树可以减少磁盘IO，上图只是以3度示例，实际上这个度可以很大，那么B+树因为磁盘IO的机制，可以加载更多的关键字用来索引

B+树每次查询访问的结点数一样，查询更加稳定，因为每次都要到叶子。

B+树中的索引列值允许有冗余，即多个结点保存相同的索引值，而B树的索引值出现且只出现在一个结点中。

B+树 叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B树每个节点 key 和 data 在一起，区间查找困难。而且如果想要获取全表数据，B+树只需要遍历叶子结点即可。而且因为顺序串联起来，对排序也支持的很好。

顺序

因为B+树是顺序的，所以如果大量无序的插入主键和主键自增他们的效率是否一样？

• 数据顺序（或逆序）插入： B+ 树索引的维护代价非常小，叶子节点都是从左往右进行插入，比较典型的是自增 ID 的插入、时间的插入（若在自增 ID 上创建索引，时间列上创建索引，则 B+ 树插入通常是比较快的）。
• 数据无序插入： B+ 树为了维护排序，需要对页进行分裂、旋转等开销较大的操作，另外，即便对于固态硬盘，随机写的性能也不如顺序写，所以磁盘性能也会收到较大影响。

所以了解到这一点，也可以了解到为什么即使是那些各种主键生成器，也都会保障有顺序性，为什么不推荐Java中的UUID.randomUUID()

聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体细节依赖于其实现方式。

聚簇索引也叫簇类索引，是一种对磁盘上实际数据重新组织以按指定的一个或多个列的值排序。

由于聚簇索引的索引页面指针指向数据页面，所以使用聚簇索引查找数据几乎总是比使用非聚簇索引快。

每张表只能建一个聚簇索引，并且建聚簇索引需要至少相当该表120%的附加空间，以存放该表的副本和索引中间页。

聚簇索引就是按照每张表的主键构造一颗B+树(这里是想说InnoDB中是这样,不是说聚簇索引就是B+树)，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。

这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。

Innodb通过主键聚集数据，如果没有定义主键，innodb会选择非空的唯一索引代替。如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。

聚簇索引的优缺点

　　优点：

　　　　1.数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快

　　　　2.聚簇索引对于主键的排序查找和范围查找速度非常快 　　缺点：

　　　　1.插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键 　　　　2.更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。 　　　　3.二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

总结

简单说InnoDB就是会自动的以主键为关键字，将表中所有的数据文件，组织成一颗B+树。

数据的组织形式是页，也就是一个表的所有的页，构造了一颗B+树。

转载务必注明出处：程序员潇然，疯狂的字节X，https://crazybytex.com/thread-234-1-1.html