data-structures - m-way树的实际使用

Question

我又开始研究数据结构了。我发现它的实际用途很少。其中之一是关于磁盘上的文件系统。有人能给我更多关于 m-way tree 实际用途的例子吗？

Answer 1

M-way树出现在很多领域。这是一个小样本：

1. B树：这些是搜索树，例如具有巨大分支因子的二叉搜索树。它们的设计方式使得每个节点都可以放入内存中，可以一次从硬盘读取。它们具有常规 BST 的所有相同的渐近保证，但旨在最小化搜索节点以找到特定元素的数量。因此，许多大型数据库系统使用 B 树或其他相关结构将大型表存储在磁盘上。这样，昂贵的磁盘读取次数被最小化，整体效率更高。
2. 八叉树。八叉树及其二维表亲四叉树是用于在三维空间中存储点的数据结构。它们在视频游戏中被广泛用于快速碰撞检测和实时渲染计算，如果没有它们，我们会变得更糟。
3. 链接/砍树。这些专门的树用于网络流问题，以比传统方法更有效地计算匹配或找到最大流，这在运筹学中具有巨大的适用性。
4. 不相交的森林。这些多路树用于最小生成树算法，以快速计算连通性，将运行时间优化到理论极限附近。
5. 尝试。这些树用于对字符串数据进行编码，并允许对字符串集进行极快的查找、存储和维护。它们也用于一些正则表达式游行者。
6. Van Emde Boas Trees - 一种闪电般快速的整数优先级队列实现，由具有巨大分支因子的树木森林支持。
7. 后缀树。文本处理世界的这些宝石允许快速字符串搜索。它们通常还具有远大于二的分支因子。
8. PQ-树。这些用于编码排列的树允许进行线性时间平面性测试，这在电路布局和绘图中具有应用。

呸！那是很多树。希望这可以帮助！

Answer 2

通过m-way，您是指广义树吗？如果是这样，几乎任何“单亲”层次结构。