MySQL数据库原理学习（六）

2.2.3 B-Tree

B-Tree，B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。以一颗最大度数（max-degree）为5(5阶)的b-tree为例，那这个B树每个节点最多存储4个key，5个指针：

我们可以通过一个数据结构可视化的网站来简单演示一下。https://www.cs.usfca.edu/~galles/visualization/BTree.html

插入一组数据：100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88120 268 250 。然后观察一些数据插入过程中，节点的变化情况。

特点：

5阶的B树，每一个节点最多存储4个key，对应5个指针。

一旦节点存储的key数量到达5，就会裂变，中间元素向上分裂。

在B树中，非叶子节点和叶子节点都会存放数据。

2.2.4 B+Tree

B+Tree是B-Tree的变种，我们以一颗最大度数（max-degree）为4（4阶）的b+tree为例，来看一下其结构示意图：

我们可以看到，两部分：

绿色框框起来的部分，是索引部分，仅仅起到索引数据的作用，不存储数据。

红色框框起来的部分，是数据存储部分，在其叶子节点中要存储具体的数据。

我们可以通过一个数据结构可视化的网站来简单演示一下。https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

插入一组数据：100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88120 268 250 。然后观察一些数据插入过程中，节点的变化情况。

最终我们看到，B+Tree 与 B-Tree相比，主要有以下三点区别：

所有的数据都会出现在叶子节点。

叶子节点形成一个单向链表。

非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的。

上述我们所看到的结构是标准的B+Tree的数据结构，接下来，我们再来看看MySQL中优化之后的B+Tree。

MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能，利于排序。