面试问题之数据结构与算法：B树、B+树、B*树

一、B树

　　B树是一种多叉平衡查找树，由于是多叉结构，对于元素数量非常多的情况下，树的深度不会像二叉结构那么大，可以保证查询效率。

二、B+树

　　B+是是B树的一种变形，

　　1、特点：

　　（1）、所有叶子结点包含全部关键字信息，及指向含有这些关键字记录的指针，且叶子节点中关键字进行有序链接。

　　（2）、非叶子结点相当于是叶子节点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层。

　　2、B+树比B树更适合操作系统的文件索引和数据库索引：

　　（1）B+树的磁盘读写代价更低，B+树的内部结点没有指向关键字具体信息的指针，因此内部结点相对B树更小。如果把所有同一内部结点的关键字放在同一块磁盘中，盘块所能容纳的关键字数量也就越多，一次性读入内存中的需要查找的关键字也就越多，相对IO读写次数降低。

　　（2）B+树的查询效率更加稳定，由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每个数据的查询效率相当。

　　此外B+树只要遍历叶子结点就可以实现整棵树的遍历，支持基于范围的查询。

三、B*树

　　B*是是B+树的变体，在B+树的非根和非叶子结点在增加指向兄弟的指针；

　　1、特点：

　　当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，将结点的最低利用率从1/2提高到2/3。

巴特西