0
我正在寻找如何最好地设计将有效使用缓存的N元树的方法。我期望树上的绝大多数操作都是从节点到根的遍历，因此我想要的目标是用例，对于插入/删除相当昂贵，我没有问题。设计缓存优化的N元树
在我的头上，前后存储节点（即根结尾）是一个理想的属性。然后我猜你可以将它存储在BFS或DFS中 - 对于这种情况最适合？一旦树达到一定的大小，它是否重要？
我也简要介绍了这个http://www.cs.au.dk/~gerth/papers/soda02.pdf - 这听起来很有希望，但这不是一个BST，我不需要搜索任何种类的东西，只需要进行孩子到根的遍历。
编辑：是的，将需要实现它的向量/数组ontop，所以连续的内存。它不需要是BST。节点通过矢量/阵列的随机访问属性直接访问，它是遍历从那里的根是问题
任何想法？
_Why_你遍历树？为了找到树叶和树根之间的节点，我假设？你如何找到正确的叶节点？如果你通过'Node *'找到叶子，那么你不能移动它们，这会使插入复杂化。 – MSalters
您能否将您的节点存储在连续的数据结构中，如矢量？你的数据有多大，你的树有多大？ –
不知道我完全理解了这个问题，但是如果你想要一个使用缓存的BST去B +树。现在已经有很多实现了。 https://en.wikipedia.org/wiki/B%2B_tree – AlexG