6.0.2 B- 树
Robert Sedgewick Kevin Wayne
在第 3 章中我们已经看到，能够快速访问大量数据中的特定元素的算法对于实际应用有着重要意义。例如在巨型数据集中，查找是一项非常重要的操作，该操作在许多计算场景中会消耗掉大部分资源。随着互联网的进步，某项任务访问到的信息可能非常庞大——我们的挑战在于在其中进行有效地查找。在本小节中，我们将介绍一种 3.3 节的平衡树算法的扩展。它支持对保存在磁盘或者网络上的符号表进行外部查找，这些文件可能比我们以前考虑的输入要大的多（以前的输入能够保存在内存中）。现代软件系统正在淡化本地文件和网页之间的区别，这些内容也可能保存在一台远程计算机上，因此我们可以找到的信息实际上近似于无限。令人惊讶的是，我们将要学习的算法只需使用 4 ～ 5 个指向一小块数据的引用即可有效支持在含有数百亿或者更多元素的符号表中进行查找和插入操作。
6.0.2.1 成本模型
数据存储的机制多种多样且在不断发展，因此我们将使用一个能够抓住本质的简单模型。这里用页表示一块连续的数据，用探查表示访问一个页。假设访问一页需要将它的内容读入本地内存，因此之后的访问就可以相对高效。一个页可能是本地计算机上的一个文件，也可能是远程计算机上的一张网页，也可能是服务器上的某个文件的一部分，等等。我们的目标是实现能够仅用极少次数的探查即可找到任意给定键的查找算法。我们不想假设页的具体大小或者一次探查（对于远程设备显然需要通信）所需时间与随后访问块中内容（显然这发生在本地处理器上）所需时间的比例。在一般情况下，这些值的数量级可能是 100、1000 或者 10 000。我们不需要更精确的值，因为在我们感兴趣的范围内，算法对这些值的不同并不非常敏感。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
B-树是一种高效的外部查找平衡树算法，能够支持大规模符号表的查找和插入操作。该树通过构造键的副本组成的树，实现了索引和符号表的分离。文章详细介绍了B-树的结构、构造方式、内外部结点定义、查找和插入操作原理，以及应用场景和优化讨论。B-树在适当参数下，查找成本是常数级别的，具有重要的实际应用意义。此外，文章还涉及B-树的数据表示、性能分析和空间需求。B-树的代码实现和图示展示了其在实际应用中的重要性和高效性。文章还提到了B-树的变种和参数选择对设备和应用的适应性，以及B-树的高效性对于大规模符号表和大量事务处理需求的重要意义。整体而言，B-树是一种高效的数据结构，对于大规模数据处理具有重要意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论