第十五章 B树、B+树和B*树

一、B树

1.引入

为什么数据库索引要使用树结构存储？

常用数据结构与算法。树的查询效率高，而且可以保持有序

为什么没有使用二叉查找树来实现？

二叉查找树查询的时间复杂度是 O(logN)，性能已经足够高了，从算法逻辑上来讲，二叉查找树的查找速度和比较次数都是最小的，但是数据库需要考虑一个现实问题：磁盘 IO。数据库索引是存储在磁盘上的，当数据量比较大的时候，索引可能有几个 G 甚至更多。当我们利用索引查询的时候，显然不能把整个索引全部加载到内存，我们能做的只有逐一加载每一个磁盘页，这里的磁盘页对应着索引树的结点

如果我们利用二叉查找树作为索引结构，那么我们每判断一次就要进行一次磁盘 IO，最坏的情况是我们要查找的数据在叶子结点，也就是说磁盘 IO 的次数是由树的高度决定的。既然如此，我们就需要降低树结构的高度，从而减少磁盘 IO 次数，把原本“瘦高”的树结构变得“矮胖”，这就是 B 树的特征之一

2.介绍

二叉树广度优先遍历和深度优先遍历？B 树（Balance Tree）是一种多路平衡查找树，它的每一个结点最多包含 k 个孩子，k 被称为 B 树的阶。k 的大小取决于磁盘页的大小

一个 m 阶的 B 树具有如下几个特征：

1. 根结点至少有两个子结点
2. 每个中间结点都包含 k - 1 个元素和 k 个子结点，其中 m/2 <= k <= m
3. 每一个叶子结点都包含 k - 1 个元素，其中 m/2 <= k <= m
4. 所有的叶子结点都位于同一层
5. 每个结点中的元素从小到大排列，结点当中 k - 1 个元素正好是 k 个子结点包含的元素的值域分划

B 树在查询中的比较次数其实不比二叉查找树少，尤其当单一结点中的元素数量很多时，可是相比磁盘 IO 的速度，内存中的比较耗时几乎可以忽略。所以只要树的高度足够低，IO 次数足够少，就可以提升查找性能。因此，结点内部元素多一些也没有关系，仅仅是多了几次内存交互，只要不超过磁盘页的大小即可，这就是 B 树的优势之一

一个包含n个节点的四叉树，B 树的插入

B 树的插入是如何实现的，限于博主的能力和插入过程的复杂性，这里不做解释

也正是因为 B 树插入过程的复杂，让 B 树能始终维持多路平衡，这也是 B 树的一大优势：自平衡

B 树的删除

每个节点，B 树的删除也是同上，对于 B 树最关键的是理解 B 树的核心思想

实际应用

B 树主要应用于文件系统以及部分数据库索引，比如著名的非关系型数据库 MongoDB

而大部分关系型数据库，比如 Mysql，则使用 B+ 树作为索引

二、B+树

1.引入

数据结构b树、B+ 树是基于 B 树的一种变体，有着比 B 树更高的查询性能

在单行查询的时候，B+ 树会自顶向下逐层查找结点，最终找到匹配的叶子结点。这看起来和 B 树差不多，但其实有两点不同。首先，B+ 树的中间结点没有卫星数据，所以同样大小的磁盘页可以容纳更多的结点元素，这就意味着，数据量相同的情况下，B+ 树的结构比 B 树更加“矮胖”，因此查询时 IO 次数也更少。其次，B+ 树的查询必须最终查找到叶子结点，而 B 树只要找到匹配元素即可，无论匹配元素处于中间结点还是叶子结点。因此，B 树的查找性能并不稳定（最好情况是只查根结点，最坏情况是查到叶子结点）。而 B+ 树的每一次查找都是稳定的

我们再来看看范围查询。B 树做范围查询只能依靠繁琐的中序遍历，而 B+ 树只需要在链表上做遍历即可：先自顶向下找到范围的下限，在通过链表指针遍历到目标元素

2.介绍

一个 m 阶的 B+ 树具有如下几个特征：

1. 有 k 个子树的中间结点包含有 k 个元素（B 树中是 k - 1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子结点
2. 所有的叶子结点中包含了全部元素的信息，以及指向含有这些元素记录的指针，且叶子结点本身依据关键字的大小自小而大顺序链接
3. 所有的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素

数据结构与算法java语言描述，

B+ 树还具有一个特点，这个特点是在索引之外，却是至关重要的特点，那就是卫星数据（Satellite Information）的位置。所谓卫星数据，指的是索引元素所指向的数据记录，比如数据库中的某一行。在 B 树中，无论中间结点还是叶子结点都带有卫星数据，而在 B+ 树中，只有叶子结点带有卫星数据，其余中间结点仅仅是索引，没有任何数据关联

B 树中的卫星数据

数据结构树。B+ 树中的卫星数据

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子结点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子结点带有指向卫星数据的指针

综上，B+ 树相比 B 树的优势：

1. IO 次数更少
2. 查询性能稳定
3. 范围查询简便

数据结构与算法 pdf，B+ 树的插入和删除，过程与 B 树大同小异

三、B*树

1.介绍

B* 树是 B+ 树的变体，在 B+ 树的非根和非叶子结点再增加指向兄弟的指针。B* 树定义了非叶子节点关键字个数至少为（2/3）*M，即块的最低使用率为 2/3，而 B+ 树为 1/2

B+ 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据复制到新结点，最后在父结点中增加新结点的指针。B+ 树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针

数据结构java语言版，B* 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟结点也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针

所以，B* 树分配新结点的概率比 B+ 树要低，空间使用率更高