很多人都知道，MySQL 数据库索引所用到的数据结构叫做 B+ 树，但却不知道，B+ 树虽然叫做“树”，它的结构却更像是跳表。不过，它确实是通过二叉查找树演化过来的，而非跳表。B+ 树发明于 1972 年，而跳表则是 1989 年发明的。跳表之所以为大众印象深刻，归其原因在于其实现更加简单。
那么，如何将一颗二叉树改造成一颗 B+ 树呢？主要有两点：
- 树中的节点并不存储数据本身，而是只是作为索引。
- 每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。
经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？
改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。
你或许也意识到了，这其实是一个空间换时间的方式，如果我们将所有数据都存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的空间会非常多。
假设，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？
我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。
这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。那么，有没有提高数据查询效率的方案呢？这时，我们来思考，其实，读取中最耗时的部分是磁盘 IO 操作，只要我们能够减少磁盘 IO 操作的次数，查询效率自然就会提高，那怎样减少磁盘 IO 操作的次数？答案是，降低树的高度。
我们来看下，如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他节点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。
二叉树
五叉树
那是不是 m 越大越好呢？其实并不是，不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小接近于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。
现在，我们知道索引存储的规则，那么，你有没有遇到过这样的情况，在写入一个数据的时候，写入的过程明显增长了，你知道这是什么原因吗？这其实就是遇到了数据写入过程中，索引的更新。
对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。我们该如何解决这个问题呢？
实际上，处理思路并不复杂。我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解（图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点）。
正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢。这是为什么呢？
我们在删除某个数据的时候，也要对应地更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些节点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。
解决办法是，设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于 m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后节点的子节点个数有可能会超过 m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。
文字描述不是很直观，我举了一个删除操作的例子，你可以对比着看下（图中的 B+ 树是一个五叉树。我们限定叶子节点中，数据的个数少于 2 个就合并节点；非叶子节点中，子节点的个数少于 3 个就合并节点。）。
MySQL 数据库的实现，大体上就是如此，最后，我们做一下总结，首先，我们可以把 B+ 树理解为 m 叉树和跳表的结合，其次，除了根节点外，每个节点中子节点的个数不能超过 m，但也不能小于 m/2，然后，我们需要知道，m 叉树只存储索引，并不真正存储数据（类似于跳表），再然后，数据通过链表将叶子节点串联在一起，这样，在查找数据时，可以很方便的按区间查找，最后，一般情况，根节点会被存储在内存中，其他节点则会存储在磁盘中。
网友评论