概述

  B树 （Bayer & McCreight 1972） (order为5) （Knuth 1998）.

在B树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被连结或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如，在一个2-3 B树（通常简称2-3树），每一个内部节点只能有2或3个子节点。

B树中每一个内部节点会包含一定数量的键值。通常，键值的数量被选定在 d {\displaystyle d} 和 2 d {\displaystyle 2d} 之间。在实际中，键值占用了节点中大部分的空间。因数2将保证节点可以被拆分或组合。如果一个内部节点有 2 d {\displaystyle 2d} 个键值，那么添加一个键值给此节点的过程，将会拆分 2 d {\displaystyle 2d} 键值为2个 d {\displaystyle d} 键值的节点，并把此键值添加给父节点。每一个拆分的节点需要最小数目的键值。相似地，如果一个内部节点和他的邻居两者都有 d {\displaystyle d} 个键值，那么将通过它与邻居的合并来删除一个键值。删除此键值将导致此节点拥有 d − − --> 1 {\displaystyle d-1} 个键值;与邻居的合并则加上 d {\displaystyle d} 个键值，再加上从邻居节点的父节点移来的一个键值。结果为完全填充的 2 d {\displaystyle 2d} 个键值。

一个节点的分支（或子节点）的数量会比存储在节点内部键值的数量大1。在2-3 B树中，内部节点将会存储1个键值（带有2个子节点）或2个键值（带有3个子节点）。一个B树有时会被描述为 ( d + 1 ) − − --> ( 2 d + 1 ) {\displaystyle (d+1)-(2d+1)} 或简单地使用最高分支 ( 2 d + 1 ) {\displaystyle (2d+1)} 。

一个Ｂ树通过约束所有叶子节点在相同深度来保持平衡。深度在元素添加至树的过程中缓慢增长，而整体深度极少地增长，并导致所有叶子节点与根节点距离加1。

在存取节点数据所耗时间远超过处理节点数据所耗时间的情况下，Ｂ树在可选的实现中拥有很多优势，因为存取节点的开销被分摊到里层节点的多次操作上。这通常出现在当节点存储在二级存储器如硬盘存储器上。通过最大化内部里层节点的子节点的数量，树的高度减小，存取节点的开销被缩减。另外，重新平衡树的动作也更少出现。子节点的最大数量取决于，每个子节点必需存储的信息量，和完整磁盘块的大小或者二次存储器中类似的容量。虽然2-3 树更易于解释，实际运用中，Ｂ树使用二级存储器，需要要大量数目的子节点来提升效率。

变体

术语Ｂ树可以指一个特定的方案，也可以指大体上一类方案。狭义上，一个Ｂ树在它内部节点中存储键值，但不需在叶子节点上存储这些键值的记录。大体上的一类包含一些变体，如B+树和Ｂ*树。

在Ｂ+树，这些键值的拷贝被存储在内部节点；键值和记录存储在叶子节点；另外，一个叶子节点可以包含一个指针，指向另一个叶子节点以加速顺序存取。

B*树分支出更多的内部邻居节点以保持内部节点更密集地填充。此变体要求非根节点至少2/3填充，而不是1/2。为了维持这样的结构，当一个节点填满之后将不会再立即分割节点，而是将它的键值与下一个节点共享。当两个节点都填满之后，分割成3个节点。

计数B树存储，每一树都带有一个指针和其指向子树的节点数目。这就允许了以键值为序快速查找第N笔记录，或是统计2笔记录之间的记录数目，还有其他很多相关的操作。

名字取义

Rudolf Bayer 和 Ed McCreight 于1972年，在Boeing Research Labs 工作时发明了B 树，但是他们没有解释B 代表什么意义（如果有的话）。Douglas Comer 解释说: 两位作者从来都没解释过B树的原始意义。正如我们所见，“balanced”， “broad” 或 “bushy” 可能适合。其他人建议字母“B”代表 Boeing。源自于他的赞助，不过，看起来把B树当作“Bayer”树更合适些

Donald Knuth 在他1980年5月发表的题为“CS144C classroom lecture about disk storage and B-trees”的论文中推测了B树的名字取义，提出“B”可能意味Boeing 或者Bayer 的名字。

数据库的问题

已排序文件的查找时间

通常，排序和查找算法会被通过大O符号，刻画为比较级别的数值。对一个有N笔记录的已排序表进行二叉查找，打个比方说，可以在O（log 2 N）比较级完成。如果表有1,000,000笔记录,那么定位其中一笔记录，将在20 个比较级内完成。 log 2 1,000,000 = 19.931...

大数据库一直以来被存储在磁盘。从磁盘上读取一笔记录，与之后的比较键值操作相比，在花费的运行时间上前者处于支配地位。从磁盘读取记录的时间涉及到一个 寻道时间 和 旋转延迟。寻道时间可能是从0到20或者更多毫秒，旋转延迟平均下来约是旋转周期的一半。对于一个7200 转每分钟的磁盘，旋转周期大约是8.33毫秒。像希捷ST3500320NS这样的磁盘,磁道至磁道的寻道时间为 0.8毫秒，平均读取寻道时间为8.5毫秒。为了简化，假设从磁盘读取花费10毫秒。

乐观来说，如此，在一百万中定位一笔记录将会话花费20次磁盘读取乘上10毫秒每次读取时间，总共是0.2秒。

时间花费没有那么糟糕的原因是，独立的记录被成组地记录在磁盘块上。一个磁盘块可能为16 千字节。如果每笔记录大小为160 字节，那么一个块可以存储100 笔记录。上面假设的磁盘读取时间确切地说是读取一个完整块的时间。一旦磁头到达位置，一个或者更多的磁盘块可以以较小的延迟来完成读取。对于100笔记录每块，最后差不多6个比较级是不需要任何磁盘读取的————都在上次读取操作中完成了。

为进一步加速查找，开始的13或14个比较级（每个需要一次磁盘访问）必须要提速。

提升查找的索引

较大程度上的提升是通过索引来做到的。在上面的例子中，初始磁盘读取从2个因素限制了查找范围。这基本上可以通过创建一个辅助索引来改善，这个索引包含每块磁盘块上的首笔记录（有时称为稀疏索引）。这个辅助索引可能只有原始数据库的1%大小，但是它可以更快速地被检索。在辅助索引中查找入口可以告诉我们在主数据库中要读去哪一块;查找辅助索引之后，我们只需要读取主数据库中的特定的某一个磁盘分块————通过一次磁盘读取开销。索引可以提供10,000入口，所以，这样最多需要14个比较级。就像主数据库，辅助索引中最后6个左右的比较级可能在相同的磁盘分块上。索引可以在大约8次磁盘读取中完成查找，目标记录会在9次磁盘读取后获得。

创建辅助索引的窍门是可以重复地给辅助索引创建辅助索引。那样可以实现一个只拥有100 入口，能填满一整个磁盘块的辅助-辅助索引。

要找到想要的记录，我们只需要读取3次磁盘分块，而不是14次。读取和查找辅助-辅助索引中第一个（而且是唯一的）块，标记了相应的辅助索引中的分块。读取和查找辅助索引的分块，标记了主数据库中相应的分块。我们只需要30毫秒，而不是150毫秒就能获取记录。

辅助的索引，使得查找问题从约为log2N 磁盘读取开销的二分查找，变成logbN 磁盘读取开销的查找，其中b为分块因素（每分块的入口数目：b = 100 入口每分块;logb1,000,000 = 3 次读取）。

在实际中，如果主数据库被频繁查找，辅助-辅助索引和大部分的辅助索引可能会存储在磁盘缓存中，所以它们不会产生磁盘读取。

插入和删除带来的麻烦

如果数据库不会改变，那么编制索引就很简单，而且索引永远不需要改变。如果他们会改变，那么管理数据库及其索引就变得非常麻烦。

从数据库中删除记录不会引起太大问题。索引可以保持不变，记录只需要标记为已删除。数据库仍然保持有序状态。如果会有很多删除，之后查找和存储就不再那么高效了。

在一个有序文件中进行插入将是个灾难，因为需要给插入的记录制造空间。在文件中第一笔记录后插入记录需要把所有记录向后偏移一个位置。如此的操作在实际中实在太过昂贵。

一种做法是预留一些空间给插入操作。磁盘块有一些空闲空间允许后来的插入，而不是高密度地填充。这些记录可以被标记为像是已删除的记录。

现在，只要块中存在空间，插入和删除都可以很快速。如果一个插入操作在一个块上找不到合适的空间，就在临近的块中寻找，且要调整辅助索引。期望是临近存在足够的空间，以免重新调整大量的块。作为可选方案，可以使用一些非排序的块。

B树运用的理念

B树使用了以上所有的想法。特别是：

保持键值有序，以顺序遍历

使用层次化的索引来最小化磁盘读取

使用不完全填充的块来加速插入和删除

通过优雅的遍历算法来保持索引平衡

另外，B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。

B树的弊端

除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

（其他关联数组的实现，例如三元搜索树或者开散列哈希表，可以动态适应任意长度的键值）。

相关条目

B+树

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。