B 树

一棵m阶的B+树和m阶的B-树的差异在于：
1）有n棵子树的结点中含有n个关键字 每个关键字不保存数据 只用来索引 所有数据都保存在叶子节点
2）所有的叶子结点中包含了全部关键字的信息 及指向含这些关键字记录的指针
且叶子结点本身依关键字的大小自小而大顺序链接
3）所有的非终端结点可以看成是索引部分 结点中仅含其子树(根结点)中的最大(或最小)关键字
通常在B+树上有两个头指针 一个指向根结点 一个指向关键字最小的叶子结点

对B+树可以进行两种查找运算：
1）从最小关键字起顺序查找
2）从根结点开始 进行随机查找

为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引?
1）B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针 因此其内部结点相对B 树更小
如果把所有同一内部结点的关键字存放在同一盘块中 那么盘块所能容纳的关键字数量也越多
一次性读入内存中的需要查找的关键字也就越多 相对来说IO读写次数也就降低了
2）B+树查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点 而只是叶子结点中关键字的索引
所以任何关键字的查找必须走一条从根结点到叶子结点的路
所有关键字查询的路径长度相同 导致每一个数据的查询效率相当
3）B+树全节点遍历更快
B+树遍历整棵树只需要遍历所有的叶子节点即可 而不需要像B树一样需要对每一层进行遍历 这有利于数据库做全表扫描