专为磁盘存储设计的数据结构——B树

---

前言

---

一、B树简介

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树与红黑树一样都是BST的变种。但它们在降低磁盘I/O操作数方面要更好一些。许多数据库系统使用B树或者B树的变种来存储信息。

下面是一颗B树示例：

计算机系统利用各种技术来提供存储能力。一个计算机系统的主存（primarymemory或mainmemory)通常由硅存储芯片组成。这种技术每位的存储代价一般要比磁存储技术(如磁带或磁盘)高不止一个数量级。许多计算机系统还有基于磁盘的辅存（secondarystorage)；这种辅存的容量通常要比主存的容量高出至少两个数量级。

尽管磁盘比主存便宜并且具有更多的容量，但是它们比主存慢很多，因为它们有机械运动的部分。磁盘有两个机械运动的部分：盘片旋转和磁臂移动。

在一个B树算法的应用中，处理的数据量异常庞大，无法一次性读入主存，比然要产生多次的I/O操作，因此I/O操作成为了此时的主要性能瓶颈。对于只检测数据的操作，需要一次磁盘读取操作，而对于更新操作，需要磁盘读取加写回两次耗时操作。为了减少I/O次数，便需要让每次I/O尽可能多的处理数据。

B树的节点大小通常与磁盘页大小相当，它在每个时刻仅在主存中保留有限数量的页数（节点数），并且磁盘页的大小限制了一个B树结点可以含有的孩子个数。

二、B树定义

B树将关键字连同其卫星数据存放在一起，由于每个节点大小固定，因此每个节点所能存放的关键字个数也不尽相同，这取决于对象的实际大小。与之相对的，B+树的内部节点只存储对象的关键字信息及其指向实际数据的指针，因此它的每个节点能够存储更多的key，因此最大化了内部节点的分支因子，树高也比B树更低一些。

有如下的定理：

三、B树上的基本操作

搜索一棵B树和搜索一棵二叉搜索树很相似，只是在每个结点所做的不是二叉或者“两路”分支选择，而是根据结点的孩子数做多路分支选择。更严格地说，对每个内部结点，做的是一个$(x.n+1)$路的分支选择。

搜索过程伪代码如下：

它以一个节点作为输入，若key在当前节点则返回，否则找到对应的孩子节点递归的搜索，因为B树中每个节点不再仅保留一个key，因此返回结果不再只是key对应的节点，而是一个有序对（key所在节点，key对应下标）

创建树可在常量时间完成：

在B树中，我们仍然按照BST的方式寻找要插入的节点，与BST不同的是，B树中，不是为新插入key分配新节点，而是插入一个已存在的节点，因为节点有最大度数限制（二倍扩容），插入操作可能引起节点分裂，它会将节点中的中间节点进行升元，提升到上一层节点中（如果没有上一层节点则创建），所以B树的生长是自下而上的，升元操作必须保证上一层节点非满，因此在搜索过程中我们就将所有遇到的满节点进行分裂，以确保之后可能的升元操作能够完成，这有点类似并查集的路径压缩。

分裂操作伪代码如下：

根节点是特殊的边界情况，我们需要对根节点进行特殊处理：

在根插满时对其进行分裂。

沿着树根找到要插入的叶节点，沿路将满节点进行分裂。

下图说明了一些插入过程可能遇到的情况：

四、B树删除

同插入操作一样，我们可以在向下搜索节点的过程中，将所有沿路遇到的key个数为$t-1$（只有根节点可以小于这个值）的节点key个数变多，确保最终找到的节点删除操作可以执行成功。办法就是通过借元（向父亲借，向兄弟借），或者合并（降元）操作。

降元操作与升元操作是相反的操作，它通过从上层节点降下一元，来粘合该key左右的两个孩子节点。

删除操作分为以下几种情况：

第二种情况对内部节点的删除处理类似BST对内部节点的删除，它通过交换元素将删除操作实际要删的节点层层向下传递直到某个叶子节点。

第三种情况就是沿途将遇到的刚刚半满的节点进行“补元”。情况a对应向兄弟借元，这种情况即将可能发生删除操作的节点元素会多一个，情况b对应向父亲借元，此时就是降元操作，会把待删节点与兄弟进行合并。

下面是上述几种情况对应的示例图：