B树和B+树

B树(B-树),是一种平衡的树,一个节点可以拥有2个以上的子节点,该数据结构常被应用在数据库文件系统的实现上

我们知道,当树特别大时,就会存储在外部存储设备上,比如磁盘,每次查询需要先从磁盘读到内存,然后再判断,判断不是要继续向磁盘读入数据,由于磁盘读取速度很慢,所以必须要尽可能的减少读取次数(即减少树的高度)

B树就是来解决上述问题的,它相较于平衡二叉树,树的高度减少,变得"矮胖"

特点:

1.每个节点可以有多个子树,M 阶 B 树表示该树每个节点最多有 M 个子树

2.每个中间节点有 k-1 个关键字(可以理解为数据)和 k 个子树 (k 介于阶数 M 和 M/2 之间,M/2 向上取整)

3.所有叶子节点都在同一层,并且叶子节点只有关键字,指向孩子的指针为 null

4.若根结点不是终端结点,则至少有2棵子树


下面是数据分布


满足上面特性的,我们可以称该B树是平衡的,当我们对该树进行插入和删除操作时,可能会破坏平衡,这时候需要对树进行调整

调整这里略过,可以参考文末尾的参考链接



B+树是B树变形版,它比B树的查询性能更高


特点:

1.关键字数和子树相同

2.非叶子节点仅用作索引,它的关键字和子节点有重复元素

3.叶子节点用指针连在一起


优点:

1.B+树非叶节点不存储数据,同样大小的磁盘页可以容纳更多的节点,io次数会减少

2.B+树每次查询都要到叶节点,所以查询性能稳定

3.B+树由于所有数据都在叶子节点上,并且有序相连,范围查询非常友好


具体调整参考:

漫画:什么是B+树

wiki-B树

理解 B 树、B+ 树特点及使用场景

上一篇: 红黑树
下一篇: trie树
作者邮箱: 203328517@qq.com