在前面专题中讲的BST、AVL、RBT都是典型的二叉查找树结构，其查找的时间复杂度与树高相关。那么降低树高自然对查找效率是有所帮助的。另外还有一个比较实际的问题：就是大量数据存储中，实现查询这样一个实际背景下，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。那么如何减少树的深度（当然不能减少查询数据量），一个基本的想法就是：
1. 每个节点存储多个元素 （但元素数量不能无限多，否则查找就退化成了节点内部的线性查找了）。
2. 摒弃二叉树结构，采用多叉树 （由于节点内元素数量不能无限多，自然子树的数量也就不会无限多了）。
这样我们就提出来了一个新的查找树结构 —— 多路查找树。 根据AVL给我们的启发，一颗 平衡多路查找树 (B~树) 自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。
【2-4树】
(2,4)树是一棵典型的平衡多路查找树。性质如下：
1. 大小性质：每个结点最多4个子结点。
2. 深度性质：所有外部结点的深度相同。
(2,4)其实是一棵迷你型的B树，其主要应用并不是为了将大数据量存储在外存上，而是通过减少树高来降低二叉查找树的查找代价。在介绍下面的B~树/B+树之前，请大家首先了解一下《 外部存储器—磁盘 》。
【B~树】
B~树，又叫平衡多路查找树。一棵m阶的B~树 (m叉树)的特性如下：
1) 树中每个结点至多有m个孩子；
2) 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子；
3) 若根结点不是叶子结点，则至少有2个孩子；
4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
5) 每个非终端结点中包含有n个关键字信息： (n，A0，K1，A1，K2，A2，......，Kn，An)。其中，
a) Ki (i=1...n)为关键字，且关键字按顺序排序Ki < K(i-1)。
b) Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [m/2]-1 <= n <= m-1
例如：下面就是一棵3阶B~树
(为了简单，这里用少量数据构造一棵2-4树的形式，其实实际应用中的B树结点中关键字很多的)
B~树的建立
由于B~树结点中的关键字个数必须>=[m/2]-1。因此和平衡二叉树不同，每一次插入一个关键字并不是在树中添加一个结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成。否则，要产生结点的 "分裂" 。
关于B~树以及后面B+树的插入，删除操作，在《 数据结构算法与应用-搜索树 》中有详细讲解。
关于文件目录索引的B~树 磁盘 存储结构及其查询过程
既然我们说过B~树相比平衡二叉树的一个巨大的特点就是：海量数据存储时B~树利用磁盘存储的效率会高很多。那么我们现在就来简单的看看操作系统中文件目录的B~树结构是怎样的(这里只介绍简单的原理，至于想Windows,Linux的文件系统使用的是B+树结构，而且技术远远比这里介绍的复杂)。
首先，我们构造一个B树结点的信息：
class BTNode<E extends Comparable<E>>{
// 结点中文件个数
int filenum;
//子树的根结点指针向量
BTNode[] ptr=new BTNode(filenum+1);
//文件名向量
E[] filename=new E(filenum);
// 指向磁盘中文件存储地址向量
FileHardAddress[] recptr=new FileHardAddress(filenum);
}
上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件的内容在硬盘中的存储位置；p1表示指向17左子树的指针。
我们现在把整棵树构造在磁盘中，假如每个盘块可以正好存放一个B~树的结点（正好存放2个文件名）。那么一个BTNode结点就代表一个盘块，而子树指针就是存放另外一个 盘块 （详细见《 外部存储器—磁盘 》）的地址。
现在我们模拟查找文件29的过程：
(1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】
(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
(3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】
(4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
(5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】
(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
分析一下上面的过程， 我们发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于3次磁盘IO操作时影响整个B~树查找效率的决定因素。
当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘IO操作最少4次，最多5次。而且文件越多，B~树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。
【B+树】
B+树：是应文件系统所需而产生的一种B~树的变形树。 一棵m阶的B+树和m阶的B-树的差异在于：
1) 有n棵子树的结点中含有n个关键字；
(B~树是n棵子树有n+1个关键字)
2) 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
(B~树的叶子节点并没有包括全部需要查找的信息)
3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (B~树的非终节点也包含需要查找的有效信息)
例如：下面就是一棵3阶B+树。我们可以和B~树做一个明显的对比。
下面我们用另外一个图来看一下B+树叶子节点和非终节点的特点：
上面这个图有一个很重要的性质： B+树的叶子结点包含了所有待查询关键字，而非终节点只是作为叶子结点中最大(最小)关键字的索引。因此B+树的非终结点没有文件内容所在物理存储的地址，而B~树所有结点均有文件内容所在的磁盘物理地址（B~树结构图中结点内部的小红方块）。 这个特点是B+树的一个重要优势所在。这一点我们在下面谈及。
关于FOXPRO索引文件的B+树磁盘存储结构及其查询
B+树在数据库，文件系统的索引结构中是十分常用的。关于B+树的磁盘存储可以参见上面B~树的情况，其一个结点用一个磁盘块存储。在这里我们对FOXPRO索引文件做一个简单的介绍，让大家对B+树的磁盘存储有一个大致的了解。
FOXPRO的索引文件（后缀IDX）由索引文件头和索引文件体组成。
文件头占一个块,相对于索引文件的物理零块号,它描述索引文件的组织信息,包括索引树的根结点位置,索引关键字表达式及索引关键字长度.其有用字节的含义如下表：
|
字节
|
内容
|
|
0-3
|
标识根结点所在块号
|
|
4-7
|
保留
|
|
8-11
|
索引文件总块数
|
|
12
|
索引文件的关键字长度
|
|
16
|
索引关键字表达式(以ASCII码存放） |
索引文件体从索引文件的相对物理块号为1的块开始,文件体的每块也就是索引树的一个结点。其中重要的是索引项。索引项=关键字+指针域(4字节)。这就是我们上面常说的B+树结点中的两个重要的信息：待查询关键字和指向另一个结点的指针。文件体每块含义如下表：
| 字节 | 内容 |
| 0 | 块属性标记.00H:非叶结点和根结点.01H:根结点,02H:叶结点.03H:既是根结点又是叶结点. |
| 1 | 00H |
| 2,3 | 块内索引项总数 (多个索引项) |
| 4-7 | 同一层前继结点块号或4个FFFF值 |
| 8-11 | 同一层后继结点块号或4个FFFF值 |
| 12- | 非递减顺序存放的索引项内容 |
B+树的查找与B~树类似。但通常B+树有两个头指针，一个指向根结点。另一个指向关键字最小的叶子节点。此外，所有叶子结点也按照大小顺序链接。因此，B+树有两种查找算法：一种从根结点出发，一种从叶子结点出发的顺序查找。
B+树的优势所在
为什么说B+树比B~树更适合实际应用中操作系统的文件索引和数据库索引？
1、B+树的磁盘读写代价更低
我们都知道磁盘时可以块存储的，也就是同一个磁道上同一盘块中的所有数据都可以一次全部读取(详见 《 外部存储器—磁盘 》 )。 而B+树的内部结点并没有指向关键字具体信息的指针 (比如文件内容的具体地址 ， 比如说不包含B~树结点中的FileHardAddress[filenum]部分） 。因此其内部结点相对B~树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。这样，一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。 一棵9阶B~树(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B~树就比B+数多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2、B+树的查询效率更加稳定。
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
