B Tree文件系统设计方案

郝爱语

摘 要：在基于地理位置的搜索中，对海量文档某些属性值的范围进行查询是比较迫切的需求，B Tree是解决这类问题的一个主要办法，文章给出了B Tree文件系统的设计方案，阐述了B树结构及其相应操作，并提出由B树提升至B*树的设想。

关键词：B树 B*树 磁盘节点

一、提出问题

根据搜索系统的实际需要，查询操作的基本需求明细见表1所示。

表1 查询操作需求明细

二、B树概述

1. B树定义

B树，即二叉搜索树，是一种平衡树，其定义是：所有非叶子结点至多拥有两个儿子（Left和Right）；所有结点存储一个关键字；非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树，如图1所示。

B树满足基本的平衡树的时间和空间复杂度，最初的B树会在节点上面保存实际数据，改进后的B+树只在叶子节点保存实际数据（或者指针），B树满足下面的一些基本特性。

1） 节点用指针连接

2） 有头节点、中间节点和叶子节点之分

3） 每个叶子节点的深度都是一样的

4） 只有叶子节点存放数据（或者数据指针）

5） 每个节点的孩子个数最大为N，最小为N/2

6） 头节点的孩子个数可以少于N/2

7） 查找的时候，根据key值往下遍历

图1 B树及其节点结构这里需要注意：在叶子节点上面，每个key都对应一个value，这个value的值是值得考虑的，正常来说，这个value都是一个指针，指向具体数据的位置，但是当value的size不大的时候，可以把value变成任何值。

2. B树节点结构

一般的说，B树有3种类型的节点，即：头节点、中间节点和叶子节点，其中，头节点和中间节点的差异很小，可以放到一起考虑。首先，所有的节点都包含了如下的数据元素：

1） 节点ID

2） 节点包含的Key值数组

3） 节点的层次

4） 节点的类型

中间节点还包含了如下的数据：节点的孩子ID数组

叶子节点还包含了如下的数据：节点Key数组对应的实际数值数组

内存中的叶子节点还包含了dirty属性，标明节点是否被修改了，而缓冲中的节点还会有对应的权重。

3. B树基本信息

B树基本信息保存了有关B树的所有配置信息和每个节点的物理位置，B树的配置信息包含有：

1） 中间节点的最大孩子数

2） 中间节点的最小孩子数（或许这里会用分裂规则替代，或者直接使用1-2分裂，忽略第一个参数）

3） Key值类型；这个参数是否需要还需要考虑

4） 每个节点的物理位置，每个节点的物理位置是一个3元组，即：

4. B树的一般原则

B树在结构上没有对其每个节点包含的元素个数以及树的高度进行任何限制，实际应用中，一般应该满足如下原则：

1） 每个节点包含的Key值最大个数 >= 200

2） B树的高度 <= 4

5. B树的搜索

B树的搜索，要从根结点开始，如果查询的关键字与结点的关键字相等，则搜索成果；否则，如果查询关键字比结点关键字小，就进入左孩子结点；如果比结点关键字大，就进入右孩子结点；如果左孩子或右孩子结点的指针为空，则显示提示消息：“找不到相应的关键字”；

如果B树的所有非叶子结点的左右子树的结点数目均保持平衡，那么B树的搜索性能逼近二分查找。相比连续内存空间的二分查找，B树的优点是：改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销，如图2和图3所示。

图2 插入结点结构（1）

图3 插入节点结构（2）但是B树在经过多次插入与删除后，有可能导致不同的结构：

图4 插入或删除操作前结构图5所示的结构也是一个B树，但它的搜索性能已经是线性的了，同样的关键字集合有可能导致不同的树结构索引。所以在使用B樹的时候，还需要考虑尽可能让B树保持图4的结构，而避免图5的结构，也就是所谓的“平衡”问题。实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”，如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键，这里不再详述。

三、解决方案

1.内存B树结构

图5 多次插入或删除操作后结构

这里使用缓冲来达到加快B树的查询和减少内存占用的目的，B树的基本结构见图6所示。

内存中的B树只包含了部分节点，主要是包含了前面的一级或者多级节点。当在树上行走的时候，如果遇到节点不在树上时，就到缓冲或者磁盘去寻找。B树并不把获得的节点挂到自己上面。内存节点集合（即缓冲）是一个简单的缓冲结构，它通过某种策略来决定哪些节点需要被淘汰。磁盘节点集合是把节点保存到磁盘的集合，它提供了读取磁盘节点的接口。

图6 B树的基本结构2.内存节点集合

在内存节点集合中，每个节点由一个id进行标示，这个id是唯一的（或许它表示这个节点在磁盘中的位置）。每个节点同时还有一个dirty标志，用来标示这个节点是否被改变了，被改变的节点由外部控制以某个策略（未定）刷新到磁盘节点集合。一般的说，当节点被淘汰出缓冲的时候，需要检测一下其dirty标志，决定是否需要刷新到磁盘上。

内存B树新构建的节点除了保存到磁盘节点集合以外，可能还会保存到内存节点集合。

3.磁盘节点集合

磁盘节点集合同样通过id来标示一个节点。磁盘节点集合的结构比较复杂，目前暂时把磁盘节点集合映射到单一文件上，将来可能会把磁盘节点结合映射到多个文件上面，比如，把B树的基本信息和节点数据集分离），这个文件的结构见图7所示。

图7 磁盘节点映射文件结构磁盘节点集合支持几种基本的操作，具体操作介绍如下。

3.1加入新的节点

加入新的节点到磁盘节点集合的时候，直接把节点数据加入到文件的最后面，同时把基本信息写入到B树基本信息里面。

3.2修改节点

当某个节点被修改的时候，情况比增加一个节点要复杂一点。在某个节点被修改的时候，通过读取B树基本信息，获得这个节点的原始占用长度，如果这个长度比新的长度大，那么，直接在原始位置覆盖新数据上去；否则，删除原始节点，加入新的节点进去，同时刷新B树基本信息。

3.3删除节点

删除一个节点的时候，直接把节点信息从B树基本信息里面删除即可。

四、 提升到B*树

所谓的B*树是指B树的2-3分裂规则。普通的B树是1-2分裂规则，即保证节点（除了头）至少有50%的空间占用。而2-3分裂规则是保证节点有67%的空间占用。考虑到B*树实现的复杂性，本方案暂时不处理空间占用的问题。如果将来有必要，再做这个方面的考虑。同理，对于号称难度超高的3-4分裂规则，更不在考虑之列。

五、小结

文中介绍了B Tree文件系统的设计问题，给出了B树的基本信息，并讨论了B树的整个操作过程，得出了提高数据查询效率的主要思想，解决了海量文档的查询办法。

参考文献：

[1]杨利，昌月楼著.并行数据库技术.长沙：国防科技大学出版社，2000[2]张华，顾红飞，刘涛.基于B+ 树的文本信息检索技术[J].皖西学院学报，2010.

基金项目：苏州工业职业技术学院院级课题《云计算环境下基于智能终端的计算机软件开发技术分析》 项目编号：SGKB201411。