B树，B-树，B+树和B*树

B树和B-树（平衡多路查找树）
规则：
1、排序方法：所有结点关键字按递增次序，并遵循左小右大的原则。
2、子结点数：非叶子结点的子结点数>1且<=M且M>=2，空树除外（M阶代表一个树的结点最多有M路查找路径）
3、关键字数：中间结点关键字数量大于等于ceil（M/2）-1且小于等于M-1个
4、所有叶子结点均在同一层，叶子结点除了包含了关键字和关键字记录的指针外，也有指向其叶子结点的指针，只不过指针地址都是NULL.
特点：B树相对于平衡二叉树不同是每个结点包含的关键字增多了，特别是这B树应用到数据库中的时候，充分的利用了磁盘块的原理（磁盘块数据存储是采用块的形式存储的，每次IO读取时，同一磁盘的数据可以一次读出）把结点大小限制和充分使用在磁盘块的大小范围内，把树的结点关键字增多后，树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

B+树
B+树是B树的一个升级版，相对于B树来说，B+树更充分利用了结点的空间，让查询速度稳定，其速度完全接近于二分查找。
规则：
1、B+树和B树不同，B+树的非叶子结点不保存关键字记录指针，只进行数据索引，这样使得B+树每个结点可以保存的关键字大大增加
2、 B+树的叶子结点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子结点才能获取到，所以每次查询的次数都是一致的
3、B+树叶子结点的关键字从小到大有序排列，左边结尾数据都会保存右边结点开始数据的指针
4、非叶子结点的子结点数=关键字数（根据多种资料，这里有两种算法的实现方法，另一种为非叶子结点的关键字数=子结点数-1）
特点：
1、B+树的层级更少，相较于B树，B+树每个非叶子结点存储的关键字数更多，树的层级更少，所以查询数据速度更快
2、B+树查询速度更稳定，B+树所有关键字数据都存在叶子结点上，所以每次查找速度比B树更加稳定

B*树
B*树是B+树的变种
规则：
1、关键字个数限制，B+树初始化个数为cei（m/2）B*树初始化个数为cei(2/3)
2、B+树结点满了时候就会分裂，而B*树会检查兄弟结点是否为满（因为每个结点都有指向兄弟的指针），如果兄弟未满则向兄弟转移关键字，如果兄弟已满，则从当前节点和兄弟结点各拿出1/3数据来创建一个新的结点
特点：
在B+树的基础上因初始化容量变大，使得结点空间利用率变高，而又存有兄弟结点转移关键字的特性，使得B*树的分解次数变少。
3、B+树天然具备排序功能，B+树的叶子结点构成了一个有序的链表，在查询大小区间的数据时候更方便，数据紧密性更高，缓存命中率也很高。
4、B+树全结点遍历更快，B+树遍历整棵树只要遍历所有叶子结点就可以了，不需要像B树一样需要遍历每一层，有利于数据库做全表扫描

巴特西

B树，B-树，B+树和B*树

最新文章

热门文章