Question

尽管前面我们已经讲了B树的诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行。

可是在B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问，如图8-8-18所示，我们希望遍历这棵B树，假设每个结点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面2→页面1→页面3→页面1→页面4→页面1→页面5。而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢？

图8-8-18

为了说明这个解决的办法，我举个例子。一个优秀的企业尽管可能有非常成熟的树状组织结构，但是这并不意味着员工也很满意，恰恰相反，由于企业管理更多考虑的是企业的利益，这就容易忽略员工的各种诉求，造成了管理者与员工之间的矛盾。正因为此，工会就产生了，工会原意是指基于共同利益而自发组织的社会团体。这个共同利益团体诸如为同一雇主工作的员工，在某一产业领域的个人。工会组织成立的主要作用，可以与雇主谈判工资薪水、工作时限和工作条件等。这样，其实在整个企业的运转过程中，除了正规的层级管理外，还有一个代表员工的团队在发挥另外的作用。

同样的，为了能够解决所有元素遍历等基本问题，我们在原有的B树结构基础上，加上了新的元素组织方式，这就是B+树。

B+树是应文件系统所需而出的一种B树的变形树，注意严格意义上讲，它其实已经不是第六章定义的树了。在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。

例如图8-8-19所示，就是一棵B+树的示意，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。

图8-8-19

一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的结点中包含有n个关键字；
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字。

这样的数据结构最大的好处就在于，如果是要随机查找，我们就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。

如果我们是需要从最小关键字进行从小到大的顺序查找，我们就可以从最左侧的叶子结点出发，不经过分支结点，而是延着指向下一叶子的指针就可遍历所有的关键字。

B+树的结构特别适合带有范围的查找。比如查找我们学校18～22岁的学生人数，我们可以通过从根结点出发找到第一个18岁的学生，然后再在叶子结点按顺序查找到符合范围的所有记录。

B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已。