教育改变生活

标题: 【数据结构】B树与B+树详细解析 [打印本页]

作者: wander    时间: 2022-8-2 16:24
标题: 【数据结构】B树与B+树详细解析
本帖最后由 wander 于 2022-8-2 16:30 编辑

B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统
定义

B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

下图是一个M=4 阶的B树:






可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。

B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示动画:



B+树是对B树的一种变形树,它与B树的差异在于:

如下图,是一个B+树:




下图是B+树的插入动画:




B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

B+ 树的优点在于:







欢迎光临 教育改变生活 (http://bbs.goldoar.com/) Powered by Discuz! X3.2