一、认识二叉树

首先，在了解 mysql 中的 B+ 树之前，我们需要搞懂什么是二叉树。二叉树是一种常见的非线形数据结构，数据是以一对多的形态组织起来的，我画了一张图来帮助你理解：

在二叉树中，有一种比较特殊的，也是最常用的二叉树，那就是二叉搜索树，也叫做二叉查找树。它最大的特点是：对于树中的任意一个节点，假如节点值为 x，其左子树节点的值必须小于 x，其右子树节点的值必须大于 x，就像下图的这几种数据排列结构：

那为什么需要使用二叉搜索树这种结构呢，它有什么好处吗？我们知道，常见的线性表结构，例如链表，要查找一个数据，必须从头开始遍历链表，在最坏的情况下，需要遍历整个链表才能够找到需要的数据。

而使用二叉搜索树这种结构，在树结构趋于平衡的情况下，借助二分的思想，每次查找数据的时候，都会舍弃掉另一个子树，所以在平均情况下，我们只需要在 O(logn)（也就是树的高度）的时间复杂度内就可以查找到数据。

二、为什么会选择 B+ 树

在了解了二叉搜索树之后，我们就为学习 B+ 树打下了坚实的基础。只不过先别着急，我们再来明确一个问题，为什么 mysql 会选择 B+ 树做为其索引模型呢？其他的数据结构不行吗？

要搞懂这个问题，我们先想想，mysql 中最常见的操作是什么？既然是数据库，最常见的操作当然是数据查询了，好的，我以最常见的两条 sql 查询语句为例：

select * from T where id = 1;
select * from T where id > 10 and id < 20;

一个是等值查询，一个是范围查询。

支持快速查询的常见数据结构有哈希表、平衡二叉查找树、跳表，我们依次来看看这几种结构能否做为 B+ 树的索引模型。

如果使用哈希表，虽然等值查询非常高效，但是数据的排列是无序的，所以并不支持范围查询。

如果使用平衡二叉查找树，例如红黑树、AVL 树等，可以在接近 O(logn) 的时间内找到数据，但是对于树结构来说，范围查询仍然是很低效的，因为只能中序遍历一棵树得到一个有序的数据集，然后再依次查找。

如果使用跳表，等值查询的效率和平衡二叉查找树差不多，并且也支持范围查询，例如下图中，我们查找节点 7（红色粗线为查找路径），如果需要范围查询的话，可以顺着原始链表依次遍历下去，因为链表节点之间是有序的。

这样来说的话，跳表也是可以做为索引模型的，但 mysql 还是选择了 B+ 树，实际上 B+ 树和跳表的设计思想有一些类似的地方，我们现在来看看 B+ 树是什么样子的。

三、B+ 树模型

1. B+ 树的优点

对数据构建索引，我们可以使用平衡二叉查找树，并且稍微做一下改造，把树的叶子节点使用链表串联，并且是从小到达顺序排列的，那么这种结构就能够支持等值查询和范围查询了，如下图：

当查找到一个节点之后，我们继续向后遍历，就能够实现高效的范围查询了。值得一提的是，这里串联叶子节点的链表，应该使用双向链表，方便在数据查询后进行升序或者降序操作。

这种结构虽然高效，但存在一个致命的问题，那就是太消耗内存空间了。

假如我们给 1000 万条数据建立索引，每个节点假设大约占用 16 字节的空间，那么构建一个索引大概就需要 150MB 内存，实际上我们还会给很多张表的很多字段建立索引，这样的话内存空间消耗还是太大了。

所以我们可以根据空间换时间的思想，使用磁盘来代替内存，磁盘是一种慢速的存储设备，造价也比内存低廉很多，因此我们可以将数据存储到磁盘上，只不过这样数据查询的速度就会慢一些了。

针对这种数据存储的方式，如果我们还是用上述的那种二叉树结构的话，每访问一层节点就对应着一次磁盘 IO，那这样的查询速度还是太慢了。因此我们可以改造一下上图中的这个结构，将二叉变成 n 叉，这样每一层节点存储的数据变多了，树的高度也降低了，访问磁盘的次数变少了，相应的查询性能就能够得到提升。

比如存储 30 个数据，构建二叉树的高度是 5，而 5 叉树的高度仅为 3：

如果数据量再大一点，就更能看出差别了，比如我们构建的是 100 叉树，那么存储 1 亿个数据，树的高度也只是 5 ，这样的话磁盘 IO 的操作次数就被大大的降低了。

那么在实际的应用中，到底应该构建多少叉树呢？是不是树的节点越多，即 n 越大越好？

我们知道，操作系统对磁盘的访问是以页为单位读取的，每页的大小通常是 4KB，也就是说我们只需要将 n 叉树的每个节点存储为一页大小左右，这样每次访问都能够整页读取，不会进行多余的磁盘 IO 操作。

假如每页的大小可以存储 3 个数据，那么最终的 B+ 树结构就是这个样子：

2. B+ 树的缺点

这样来看的话，似乎 B+ 树已经比较完美的解决了数据索引的问题，但是，天下没有免费的午餐，B+ 树对查询操作有了很大的提升，但同时也降低了数据插入和删除的效率。

这个问题似乎不难理解，当我们不断插入数据的时候，B+ 树中的节点肯定会越来越多，直到大于了页大小，这时，为了维护查询的效率，不产生多余的 IO 操作，我们不得不进行节点的重构。

假如叶子节点的数量是 m，当节点数量大于 m 的时候，该节点就会分裂，从叶子节点的最中间的那个节点，让其成为父节点，节点左右的值，分别成为新的左右子节点；如果上一层又超过了限制，则继续向上进行分裂，直到影响到根节点，参照下面的图就很容易理解了：

删除也是类似的道理，当叶子节点过少，例如少于 m / 2 的时候，就可以将节点合并至旁边的兄弟节点。你可以自己参照插入的思路，想想删除是怎么进行节点重构的。

好了，这篇文章讲述了 mysql 的索引模型 B+ 树，首先需要了解一下二叉树，这是学习 B+ 树的前提，然后我以两个最常见的查询 sql，向你描述了为什么其他的常见数据结构不适合用来做索引，然后由此引出了 B+ 树。

根据数据查询和存储的特点，对平衡二叉树逐步改造成了 B+ 树，B+ 树对数据查询起到了很好的作用，但是它也带有副作用，那就是对插入删除操作有影响，于是需要进行节点的重构。

原文链接： https://www.jianshu.com/p/e966112dbf8c

文源网络，仅供学习之用，如有侵权请联系删除。

我将面试题和答案都整理成了PDF文档，还有一套学习资料，涵盖Java虚拟机、spring框架、Java线程、数据结构、设计模式等等，但不仅限于此。

关注公众号【java圈子】获取资料，还有优质文章每日送达。