algorithm - 大树数据结构是如何遍历的？

Question

我正在研究树算法，几乎所有算法都使用递归进行遍历当然遍历也可以在没有递归的情况下完成(通过创建堆栈数据结构和 while 循环)。但是出于好奇想知道当树中存在数百万或数十亿个节点时如何遍历这些树数据结构？当然这些问题在面试中也会被问到。

我能想到的一些方法是

• 将树存储在多个文件中作为不同的子树并遍历通过文件
• 在不同的机器上分发树
• 以表结构在数据库中存储树并设计查询遍历

任何更好的方法，如果有人可以分享指向此类问题的学习 Material 的链接，将会有所帮助。

Answer 1

如果这棵树适合内存，你就可以走它。我构建了构建具有数百万个节点的 AST 的工具(来自很多树，有时来自非常深的树)；我们将树存储在内存中。递归遍历工作得很好。而且，如果操作得当，每个节点只需数十纳秒(缓存行丢失时间)即可完成。

固定大小的堆栈通常会搞砸，因为这样的堆栈可以防止任意深度递归。参见 How does a stackless language work?我编写树操作代码的语言没有固定大小的堆栈。

您可以将树分布在多个机器上或(更糟!)数据库中。你仍然可以走过那棵树，但算法比较笨拙，而且额外的通信延迟(到远程机器，到数据库表)使这成为一个如此缓慢的操作，几乎没有人这样做。