BTree结构

BTree

二叉搜索树：

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

如下图：

B树的搜索，从跟节点开始，如果查询的关键字与节点的关键字相等，那么命中；否则，如果查询关键字比节点关键字小，就进入左分支；如果比节点关键字大，就 进入右分支；如果左分支或者右分支的指针为空，则报告找不到对应的关键字。

如果B树的所有非叶子节点的左右子树的节点数目均保持差不多(平衡)，那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构 (插入与删除节点)不需要移动大段的内存数据，甚至通常是常数开销。

如：

但B树在经过多次插入与删除后，可能导致不同的结构：

右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让其保持平衡结构。

实际使用的B树都是在原B树的基础上加上平衡算法，即"平衡二叉树"；如何保持B树节点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和 删除节点的策略。

B-Tree

是一种多路搜索树(并不是二叉)：

1. 定义任意非叶子节点最多只有M个子几点，且M>2；
2. 根节点的子节点数为[2, M]；
3. 除根节点以外的非叶子节点的子节点数为[M/2, M]；
4. 每个节点存放至少(M/2 - 1)(取上整)和至多(M - 1)个关键字；(至少2个关键字)
5. 非叶子节点的关键字个数=指向子节点的指针个数 - 1；
6. 非叶子节点的关键字：K[1]，K[2]，...，K[M-1]，且K[i] < K[i+1]；
7. 非叶子节点的指针：P[1]，P[2]，...，P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于 (K[i-1], K[i])的子树；
8. 所有叶子节点位于同一层。

如：(M=3)

B-Tree的搜索，从根节点开始，对节点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点，重复，直到所对应的子节点 指针为空，或已经是叶子节点。

B-Tree的特性：

1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个节点中；
3. 搜索有可能在非叶子节点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制；

由于限制了除根节点以外的非叶子节点，至少含有M/2个子节点，确保了子节点的至少利用率，其最低搜索性能为：

其中，M为设定的非叶子节点最多子树个数，N为关键字总数；所以B-Tree的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题；由于M/2的限制， 在插入节点时，如果节点已满，需要将节点分裂为两个各占M/2的节点；删除节点时，需将两个不足M/2的兄弟节点合并。

B+Tree

B+Tree是B-Tree的变体，也是一种多路搜索树，其定义基本与B-Tree相同，除了：

1. 非叶子节点的子树指针与关键字个数相同；
2. 非叶子节点的子树指针P[i]，指向关键字属于[K[i], K[i+1])的子树(B-Tree是开区间)；
3. 为所有叶子节点增加一个链指针；
4. 所有关键字都在叶子节点出现；

如：(M=3)

B+Tree的搜索基本与B-Tree相同，区别是B+Tree只有达到叶子节点才命中(B-Tree可以在非叶子节点命中)，其性能也等价于在关键字全集做一次二分查找。

B+Tree的特性：

1. 所有关键字都出现叶子节点的链表中(稠密索引)，且链表中的关键字恰好是有序的；
2. 不可能在非叶子节点命中；
3. 非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储(关键字)数据的数据层；
4. 更适合文件索引系统。

B*Tree

是B+Tree的变体，在B+Tree的非根和非叶子节点再增加指向兄弟的指针。

B*Tree定义了非叶子节点关键字个数至少为(2/3)*M，即块的最低使用率为2/3(代替B+Tree的1/2)。

B+Tree的分裂：当一个节点满时，分配一个新的节点，并将原节点中1/2的数据复制到新节点，最后在父节点中增加新节点的指针；B+树的分裂只影响原节点和父 节点，而不会影响兄弟节点，所以不需要指向兄弟节点的指针。

BTree的分裂：当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键 字(因为兄弟节点的关键字范围改变了)；如果兄弟节点也满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的 指针，所以，BTree分配新节点的概率比B+Tree要低，空间利用率要高。

总结

BTree：二叉树，每个节点只存储一个关键字，等于则命中，小于走左节点，大于走右节点；

B-Tree：多路搜索树，每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点；所有关键字在整颗树中出现，且只出现一次，非叶子节点可以 命中；

B+Tree：在B-Tree的基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；B+Tree总是到叶子节点才命中；

B*Tree：在B+Tree的基础上，为非叶子节点也增加链表指针，将节点的空间利用率从1/2提高到2/3。