查找--多路查找树（B树）

之前谈论的树，一个结点只能存储一个元素，当元素非常多的时候，数据度或者高度非常大，使得内存与外存的存取次数非常多，时间效率低，这时需要引入多路查找树的概念。
多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。主要有4中特殊形式。
1.B树
（B-树）是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。节点最大的孩子数组称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树。


B树减少了内存与外存的数据交换次数。其原理为：
我们的外存，如硬盘，是将所有信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，当要处理的数据量很大，数据无法一次全部装入内存，这时，调整B树，使阶数与磁盘存储页面的大小匹配，高度为2，只要先读取根节点，并只保存根节点在内存中。此时，寻找关键词的时候至多需要两次硬盘读取即可。与二叉树不同的是，减少了必须访问结点和数据块的数量。
2.B+树
但是B树遍历的时候，假设每个节点都属于硬盘的不同页面，我们为了中序遍历所有的元素，页面2-页面1-页面3-页面1-页面4-页面1-页面5.而且我们每经过节点遍历时，都会对节点中的元素进行一次遍历，有没有可能让遍历时每个元素只访问一次呢？

为了解决遍历问题，在B树的基础上，加上了新的元素组织方式，就是B+树。
B+树是应文件系统所需而出的一种B树的变形树，在B树中，每一个元素树中只出现一次，而B+树中，出现在分支节点中的元素会被当做他们在该分支节点位置的中序后继者（叶子节点）中再次列出。另外，每一个叶子节点都会保存一个指向后一叶子节点的指针。

B+树的优点：
1.随机查找时，从根节点出发，与B树不同的是在分支结点找到待查关键字，它只是用来索引，不能提供实际记录的访问，要去对应的叶子结点查找关键字。
2.从小到大顺序查找时，从最左侧的叶子结点出发，不用经过分支结点就能完成遍历。
3.特别适合范围查找（a,b），从根节点出发找到a,再在叶子结点上按顺序查找对应范围的记录。