浅谈B+树

前言

**B+树（B Plus Tree）**是 MySQL 数据库索引的底层数据结构，B+树也是一种平衡树和 AVL 树以及红黑树有着同样的性能，不用你说，我知道你肯定又个疑问，为什么数据库要使用 B+树作为数据库索引而不是其他平衡树呢？为什么需要使用 B+树呢？或许看完这篇文章你应该就懂了。

其他结构的问题

数据库索引作为数据库中的重要组成部分，同时也是数据库性能的重要指标，数据库是索引必须拥有较好的性能，这包括执行效率（时间）和内存消耗（空间），在执行效率方面，我们希望通过索引，查询数据的效率尽可能的高；在存储空间方面，我们希望索引不要消耗太多的内存空间。

在以上的需求下，支持快速增删改查的数据结构除了 B/B+树大概还有以下几种：

• 哈希表（Hash Table）
• 跳表（Skip List）
• 二叉搜索树（Binary Search Tree）
• 红黑树（Red-Black Tree）
• 平衡二叉树（AVL Tree）

首先看下哈希表，哈希表拥有 O(1)的增删改查的性能，乍一看似乎是最适合作为数据库索引的数据结构。但是，数据库索引不止能等值索引还需要支持范围索引，而哈希表并不能提供范围索引的功能，所以哈希表不能胜任。

接着是跳表，跳表之前的文章介绍过了，这里就直接说它的理由吧，跳表的空间复杂度是 O(nlogn)相比其他平衡结构差，而数据库需要应对的是大量的数据，需要大量的内存和磁盘空间，所以一般不采用跳表作为数据库索引的数据结构。

二叉搜索树在极端条件下会退化成链表，造成数据库性能不稳定的情况，而其他平衡树拥有更稳定的性能，所以不会使用二叉搜索树。

AVL 树都是一种极为成熟的平衡树结构，维护 AVL 树的平衡是非常耗时的，AVL 树适合用于插入删除次数比较少，但查找多的情况。而数据库有可能进行频繁的插入删除操作，所以不适合。

红黑树似乎是和 B/B+树一样适合作为数据库索引的，但是为什么 MySQL 不使用红黑树而是采用 B+树呢？首先红黑树并不太适合范围查找，还有其他的就在下面说明吧。

B+树

B+树是什么样子的呢？

首先为了支持范围查找，二叉树需要进行一些小改造：把数据都移到叶节点中，上层树结构只存储下层的索引。思路类似于跳表，但是上层索引使用的是树结构而不是链表结构。

除了执行效率和内存消耗的考虑，数据库索引还需要考虑其他一些东西：在海量的数据中索引应该存在哪？有些同学可能会说内存啊，但是内存真的能存下海量的数据索引吗？假如我们要存储 10 亿个字段，每个索引 12B 则叶节点大概需要 11G，整个索引树内存占用不大于 20G。20G 对于一台服务器已经是不小的压力了，所以，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。而磁盘 IO 操作又极为耗时，所以为了减少磁盘 IO 操作则二叉树需要进行改造，将层高减少，即使用 N 叉树。

这样的结构就可以减少对磁盘 IO 的操作次数，同时又保留了高效的增删改查效率，而这种结构就是 B+树，数据由叶节点的指向，索引中在保留 key，节省内存。

这时有人就会问这个 N 要设置为多少为才是最好的？我们知道磁盘是按一定大小读取数据块的，这个大小是一个固定值，通常是 4KB，装系统中常说的 4K 对齐其实就是设置数据块的大小，为了防止读取一个 B+树节点的时候多次操作磁盘，同时最大化的利用每个数据块，B+树的每个节点应尽量充满整个数据块，通过计算就可以得出 N 的大小。

B+树是如何维持平衡的呢？

说了这么多，那 B+树作为一种平衡结构肯定有一种方式来维持平衡，在跳表中是随机高度，在平衡树中一般是采用左右旋的方式维持平衡，那么 B+树又是如何呢？

当数据量庞大的时候势必会造成某个节点的大小超过数据块的大小，如何很好的解决这种问题？没错就是分裂，将一个节点分成两份，这样每一份就都小于数据块的大小了，就能保证每次读取一个节点只需要一次磁盘操作了。

那分裂又是如何进行的呢？我们知道叶节点才是存储数据的节点，其他上层节点只存储了 key，但叶节点过大的时候节点进行分裂，分裂后数据的位置就不同了，所以还需要更新上层索引，当上层索引过大的时候就需要同叶节点一样分裂，直到分裂到根节点。

删除的时候就和分裂相反，当某个数据删除后节点中的数据数量少于某个特定的阈值的时候（通常是 N/2）就需要与兄弟节点进行合并，合并后同样需要更新上层索引，若合并后节点过大的时候就应该同插入一样进行分裂，直到两个节点的大小处于合理的范围之中。

总算更完这篇文章了，溜了溜了。插图看看吧，有空再画 （逃