算法学习：从B树、B+树、B-树谈到R-树_b+树和b-树的区别i资源-CSDN文库

版权申诉

17 浏览量 2023-09-20 22:50:29 上传评论收藏 985KB DOC 举报

资源推荐

资源详情

资源评论

第一节、B 树、B+树、B*树

1.前言：

动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找

树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，

B-tree/B

+

-tree/ B

*

-tree (B~Tree)。前三者是典型的二叉查找树结构，其查

找的时间复杂度 O(log

2

N)与树的深度相关，那么降低树的深度自然会提高查找效

率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询

这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的

话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的

深度过大而造成磁盘 I/O 读写过于频繁，进而导致查询效率低下（为什么会出

现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当

然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树

节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的

启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的第一个主题

B~tree(B 树结构)。

B-tree（B-tree 树即 B 树）这棵神奇的树是在 Rudolf Bayer, Edward M.

McCreight(1970)写的一篇论文《Organization and Maintenance of Large

Ordered Indices》中首次提出的（wikipedia 中：

http://en.wikipedia.org/wiki/B-tree，阐述了 B-tree 名字来源以及相关的开源

地址）。

剩余41页未读，继续阅读

内容反馈

版权申诉

小小哭包

粉丝: 1900
资源: 3864

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip