我们主要学习InnoDB的B+tree索引结构

先了解二叉树，如下
一个5层的二叉树最多有31个节点。这是由于，二叉树的最大节点数量与其高度相关，而5层的二叉树高度为5，每一层最多有 2^(i-1) 个节点，其中i代表层数。因此，第一层有1个节点，第二层有2个节点，第三层有4个节点，第四层有8个节点，第五层有16个节点。则总节点数为 1+2+4+8+16=31 个
一个节点下面最多包含两个子节点，最顶端的节点叫根节点根节点左侧(包括所有子树)的节点比根节点小，根节点右侧(包括所有子树)的节点比根节点大

如何查找二叉树中第四层的某个数据

1、判断该数据比根节点大还是小，大的话走根节点的左侧到达第二层，小的话走根节点的右侧到达第二层

2、到达第二层后，判断该数据比第二层的交叉节点大还是小，大的话走交叉节点的左侧到达第三层，小的话走交叉节点的右侧到达第三层

3、到达第三层后，判断该数据比第三层的交叉节点大还是小，大的话走交叉节点的左侧到达第四层，小的话走交叉节点的右侧到达第四层

4、成功找到第四层的某个数据。共只要查找4次就可查找到数据

二叉树缺点

1、例如依次插入数据10、9、8、7、6、5、4、3、2。由于插入的下一个数据都比上一个数据小，所以插入的下一个数据都会在上一个数据的左侧，依次往下形成一个链表，而不能形成分叉的二叉树，当我们要查找2这个数据时，共需要查找9次，这样就效率低

2、二叉树的一个节点下面最多包含两个子节点，即理解为双线程处理数据(抽象表达)，当数据量大时，其实二个子节点并不能分担太多数据，层数会比较多(也就是层级深)，这样就还是会发生低效率，只是没有这么低，但是当数据量庞大时，就是一个彻彻底底的低效率总结: 顺序插入时，会形成一个链表，查询性能大大降低。大数据量情况下，层级较深，检索速度慢

解决二叉树的链表问题(也就是上面的第一个问题) 使用红黑树。红黑树是一个自平衡的二叉树，查询逻辑跟二叉树一样。红黑树会自己找出插入数据中的中间数据，从而绘制出一个效率最大化的二叉树，尽可能减少层级，间接提高查询效率。例如依次插入数据10、9、8、7、6、5、4、3、2，红黑树会把6作为根节点，并且自动找出最合适作为交叉节点的数，使每个交叉节点都会有两个分节点，当我们要查找2这个数据时，共需要查找4次即可

红黑树缺点红黑树本质上是二叉树，也存再相同问题，即大数据量情况下，层级较深，检索速度慢，只不过数据要非常大才会有这个问题

解决二叉树和红黑树的缺点 使用BTree树(全称是多路平衡查找树)，读作B树。多路的意思是一个节点下面可以有多个子节点

BTree 以一颗最大度数(max-degree)为5(5阶)的b-tree为例(每个节点最多存储4个key，5个指针)，先介绍一下什么是树的度数，指的是一个节点的子节点个数，即第一句话的意思是一个子节点允许最多有5个子节点，这种B树就叫5阶的B树，4个key对应的是5个指针。画出来的话，就是第一层有一个节点，该节点有4个数据(也就是4个key，这4个数据有5个指针)，(例如这4个数据为5、8、10、14，此时插入一个数据为3到第二层，3比5小就会在5的左边指针处分叉到第二层，如果是插入一个数据为7到第二层，7比5大但比8小就会在8的左边指针处分叉到第三层，举这2个例子目的就是理解指针的作用，指针是控制下一层数据从当前层的哪个地方分叉到下一层。)第二层有5个节点，每个节点有3个数据(这3个数据有4个指针)，以此类推第三层

总结:5阶表示每一个交叉点最多有4个数据，且该节点有5个指针。指针是控制下一层数据从当前层的哪个地方分叉到下一层

如何构建B树在一个5阶的B树中依次插入23，234，345，899，1200，1234，1500、1000、123、12、1567、1800、1980、2000、1888、2456 我们需要打开一个数据结构可视化的网站https://cs.usfca.edu/~galles/visualization/BTree.html 注: 2023年1月10日打不开该网站。该网站会以动画的形式演示各种数据结构。建议自己百度找一个可用的数据结构可视化的网站，把上上行的多个数据依次输入进入，每输入一个就观察B树的变化情况，B树的变化原则是:交叉节点的数据不超过阶数允许的个数，如将要超过，则中间大小的数据向上分裂，也就是会多出来一层。我们上4行的那几组数据画出来就是共三层，第一层只有1个交叉节点，里面有1个数据1200，第二层有两个交叉节点分别在左右边，左边交叉节点里面有数据123、345，右边交叉节点里面有数据1567、1980，第三层有6个两两数据的节点，左三是左边，右三是右边，左边的左三分别是12、23，234、245，899、1000右边的右三是1234、1500，1800、1888，2000、2456

B+Tree B+树是B树的变种。以一颗最大度数(max-degree)为4(4阶)的b+tree为例(每个节点最多存储3个key，4个指针)

B+树相对于B树的特点，即B+树的特点

1、所有交叉节点(包括根节点)的数据都会出现在最下面的叶子位置，可以理解为重复了交叉节点的数据，B+树的所有交叉节点的作用是作为索引的作用，最下面的叶子位置才是用来存放数据的

2、所有最下面的叶子(我们叫叶子节点)形成一个单向链表，即每个叶子节点通过指针指向下一个元素形成一个单向链表

3、B树的变化原则是:交叉节点的数据不超过阶数允许的个数，如将要超过，则中间大小的数据向上分裂，且把这个分裂的数据也额外增加进最底层的叶子节点

4、所有数据必然在叶子节点有

5、非叶子节点只是起到索引的作用，数据在最底部的叶子节点上

如何构建B+树在一个5阶的B树中依次插入1000，567，234，232，1234，2345 我们需要打开一个数据结构可视化的网站https://cs.usfca.edu/~galles/visualization/BTree.html 最终画出来的B+树的图是第一层:一个根节点，有2个数据，3个指针，第二层分三组，这三组分别是从上一层的三个指针处下来的，并且这三组从左到右有一个右箭头连接，形成一个单向链表，我们叫这三组为左边、中间、右边，那么左边为232、0234，中间为567、890，右边为1000、1234、2345

在MySQL中的B+树索引 MySQL索引数据结构对经典的B+Tree进行了优化。在原有B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能，即原来B+树最底部的叶子是单向的，而现在变成了最底部叶子跟叶子之间是双向的，就形成了带有顺序的B+树，就提高了区间访问性能，利于数据库数据的排序。注意交叉节点是不存储数据的，只是作为索引的作用，最底部的叶子(我们叫叶子节点)才是存储数据的。每一个交叉节点都是存放在数据块(也叫页)当中的，叶子节点也是存放在数据块中的

我们前面学的InnoDB存储引擎的存储结构分为:表空间、段、区、页、行。且页的大小在InnoDB中默认是16k