实际使用m-way树

Question

我已经开始再次研究数据结构.我发现这很少有实际用途.其中一个是关于磁盘上的文件系统.有人能给我更多关于m-way树的实际用途的例子.

Answer 1

M路树出现在很多竞技场中.这是一个小样本:

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

唷!那是很多树.希望这可以帮助!