删除操作比B树简单一些,因为叶子节点有指针的存在,向兄弟节点借元素时,不需要通过父节点了,而是可以直接通过兄弟节移动即可(前提是兄弟节点的元素大于m/2),然后更新父节点的索引;如果兄弟节点的元素不大于m/2(兄弟节点也没有多余的元素),则将当前节点和兄弟节点合并,并且删除父节点中的key,
下面来看一个具体的实例:
B+树的初始状态
删除10,删除后,不满足要求,发现左边兄弟节点有多余的元素,所以去借元素,最后,修改父节点索引
删除元素5,发现不满足要求,并且发现左右兄弟节点都没有多余的元素,所以,可以选择和兄弟节点合并,最后修改父节点索引
发现父节点索引也不满足条件,所以,需要做跟上面一步一样的操作
B+树相比较B树有一些优点:
B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快
B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定
B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高
B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描
这里不再给出B树和B+树代码实现,代码实现可见参考【26】
上一篇:重学数据结构(五、串)
本博客为学习笔记,参考资料如下!
水平有限,难免错漏,欢迎指正!
参考:
【1】:邓俊辉 编著. 《数据结构与算法》
【2】:王世民 等编著 . 《数据结构与算法分析》
【3】: Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】:严蔚敏、吴伟民 编著 . 《数据结构》
【5】:程杰 编著 . 《大话数据结构》
【6】:[Data Structure] 数据结构中各种树
【7】:Tree
【8】:Binary Tree
【9】:Java数据结构与算法——二叉树及操作(包括二叉树遍历)
【10】:Java数据结构和算法(十)——二叉树
【11】:阿粉带你玩转二叉查找树
【12】:JAVA递归实现线索化二叉树
【13】:二叉查找树(三)之 Java的实现
【14】:一步一步写平衡二叉树(AVL树)
【15】:什么是平衡二叉树(AVL)
【16】:什么是平衡二叉树(AVL)
【17】:动画 | 什么是AVL树?
【18】:详解什么是平衡二叉树(AVL)(修订补充版)
【19】:红黑树深入剖析及Java实现
【20】:平衡查找树之红黑树
【21】:漫画:什么是红黑树?
【22】:面试官问你B树和B+树,就把这篇文章丢给他
【23】:平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
【24】:B树和B+树的插入、删除图文详解
【25】:B树Java代码实现以及测试
【26】:Introduction of B-Tree
【27】:B+树详解