B xx 树

B 树

即二叉搜索树：

1. 所有非叶子节点至多拥有两个子节点
2. 所有结点存储一个关键字
3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树

B树查找顺序：从根结点开始，如果查询的关键字与结点的关键字相等，命中；如果比结点关键字小，进入左子结点继续查找，如果比结点关键字大，进入右子结点继续查找；

B- 树

是一种多路搜索树（并不是二叉的）
1. 定义任意非叶子结点最多只有M个子结点，且M>2
2. 根结点的儿子数为[2,M]
3. 除根结点以外的非叶子结点儿子数为[M/2,M]
4. 每个结点存放至少M/2-1和至多M-1个关键字，（至少2个关键字）
5. 非叶子结点的关键字个数 = 指向儿子的指针个数-1
6. 非叶子结点的关键字：K[1]

此坑待续~~~~

B+ 树

   B+树是B-树的变体，也是一种多路搜索树：

   1.其定义基本与B-树同，除了：

   2.非叶子结点的子树指针与关键字个数相同；

   3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树

   5.为所有叶子结点增加一个链指针；

   6.所有关键字都在叶子结点出现；

   如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在

非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

   B+的特性：

   1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

   2.不可能在非叶子结点命中；

   3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

   4.更适合文件索引系统；

参考资料 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html