B树B+树

1、B&＃43;树的层级更少&＃xff1a;相较于B树B&＃43;每个非叶子节点存储的关键字数更多&＃xff0c;树的层级更少所以查询数据更快&＃xff1b;

2、B&＃43;树查询速度更稳定&＃xff1a;B&＃43;所有关键字数据地址都存在叶子节点上&＃xff0c;所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B&＃43;树天然具备排序功能&＃xff1a;B&＃43;树所有的叶子节点数据构成了一个有序链表&＃xff0c;在查询大小区间的数据时候更方便&＃xff0c;数据紧密性很高&＃xff0c;缓存的命中率也会比B树高。

4、B&＃43;树全节点遍历更快&＃xff1a;B&＃43;树遍历整棵树只需要遍历所有的叶子节点即可&＃xff0c;&＃xff0c;而不需要像B树一样需要对每一层进行遍历&＃xff0c;这有利于数据库做全表扫描。

B树相对于B&＃43;树的优点是&＃xff0c;如果经常访问的数据离根节点很近&＃xff0c;而B树的非叶子节点本身存有关键字其数据的地址&＃xff0c;所以这种数据检索的时候会要比B&＃43;树快。

B树(B-树)

m阶B树定义

m阶B树是一棵平衡的m路搜索树&＃xff0c;或者是空树&＃xff0c;或者是满足以下条件&＃xff1a;

1 树中的每个节点最多有m个孩子

2 除了根节点和叶子结点外&＃xff0c;其他节点最少含有 (m&＃43;1)/2 个孩子

3 如果根节点不是叶子结点&＃xff0c;则根节点最少2个孩子

4 所有叶子节点都在同一层&＃xff0c;并不带任何信息

5 除了叶子结点&＃xff0c;节点含有关键字属性&＃xff0c;数目范围是 [M/2 - 1&＃xff0c;M-1]&＃xff0c;即关键字个数 &＃61; 孩子个数 - 1。

时间复杂度&＃xff1a;O(nlogn)。

优点

B树相对于B&＃43;树的优点是&＃xff0c;如果经常访问的数据离根节点很近&＃xff0c;而B树的非叶子节点存储关键字数据的地址&＃xff0c;所以这种数据检索的时候会要比B&＃43;树快。

B&＃43;树

m阶B&＃43;树定义

B&＃43;树是B树的一种变形形式&＃xff0c;m阶B&＃43;树满足以下条件&＃xff1a;

(1) 每个结点至多有m个孩子。

(2) 除根节点和叶结点外&＃xff0c;每个结点至少有&＃xff08;m&＃43;1&＃xff09;/2个孩子。

(3) 如果根节点不为空&＃xff0c;根结点至少有两个孩子。

(4) 所有叶子结点增加一个链指针&＃xff0c;所有关键字都在叶子结点出现。

(5) 除了叶节点&＃xff0c;结点的孩子数目等于关键字数目。 注意&＃xff0c;B&＃43;树中非叶子结点存储的不是关键字数据的地址&＃xff0c;而是指向叶子结点中关键字的索引。&＃xff08;所以任何关键字的查找必须走一条从根结点到叶子结点的路&＃xff09;

优点

B&＃43;树的层级更少&＃xff1a;相较于B树B&＃43;每个非叶子节点存储的关键字数更多&＃xff0c;树的层级更少所以查询数据更快&＃xff1b;

B&＃43;树查询速度更稳定&＃xff1a;B&＃43;所有关键字数据地址都存在叶子节点上&＃xff0c;所以每次查找的次数都相同所以查询速度要比B树更稳定;

B&＃43;树天然具备排序功能&＃xff1a;B&＃43;树所有的叶子节点数据构成了一个有序链表&＃xff0c;在查询大小区间的数据时候更方便&＃xff0c;数据紧密性很高&＃xff0c;缓存的命中率也会比B树高。

B&＃43;树全节点遍历更快&＃xff1a;B&＃43;树遍历整棵树只需要遍历所有的叶子节点即可&＃xff0c;而不需要像B树一样需要对每一层进行遍历&＃xff0c;这有利于数据库做全表扫描。

适应场景

通常用于数据库和操作系统的文件系统中。

优点

够保持数据稳定有序&＃xff0c;其插入与修改拥有较稳定的对数时间复杂度