大家好,这里是IT技术百货,专注于有价值的IT技术知识分享;
今天跟大家分享数据库中的关键数据结构,B树与B+树
B树是一个满足以下条件的多叉树,一棵m阶B树满足如下条件:
以上限定规则略显复杂,读起来可能也比较绕口,简言之就是限制每个节点的子结点个数,保证有序性以及每一个叶节点深度相同的三个特性;
3阶b树怎么建立?B树是一种有序的数据结构,可以在log时间复杂度下完成插入、查找、删除操作;
插入操作:
自底部插入,如果满足节点个数的限制,则直接插入;如果不满足,那么一定是超出了节点个数限制,则进行调整;
调整的方式是将中间的元素插入到父节点,本身的节点分裂成两个节点(如果父节点个数也超出了继续按照这个规则调整);
举例:如下图,插入“39”这个节点,那么第二层最左边的节点个数超出了,因此将中间的节点升为父节点,本身分裂为两个节点,最终变为第二个图的样子。
n个关键字的m阶b树,删除操作
删除操作略微复杂,但不同情形下都是有成熟的规则的,只要按照规则来就可以;(类似于拧魔方)
B+树是对B树的升级,主要改动如下:
page=3的页中只存在索引,而数据存在其他页中;
采用双向链表的原因是为了方便处理"小于"的条件查询。
3阶b树生成,B树和B+树都是多路查找树,目的都是为了解决多次访问磁盘,IO耗时太长的问题;
如果采用二叉树,虽然查找的时间复杂度没变,但是由于每一个节点可能在不同的页上,因此访问磁盘的次数增多。
B+树进一步优化了磁盘访问次数,将索引和数据分开存储,因此每一个页中存储的索引更多。
B+树的叶节点增加了指针链接,可以查询效率更高;
但同样的,B+树对查询的优化操作会降低了一定写入性能。
如何构造3阶b树,感谢浏览阅读,如果觉得内容有价值欢迎点赞,转发;喜欢请关注“IT技术百货”
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态