多叉树怎么翻译，以及求推荐比较节约的可持久化 (persistent) 多叉树数据结构

[notcome]

需要建立一个类似文件系统的数据结构, 要求能追踪全部的版本信息. 想来使用一个可持久化的多叉树应该比较方便 (难道还有别的方法吗……)

又一次手残还没打完就发送了……

然后我发现不知道怎么翻译多叉树, 谷歌说是 multitree, 看了一下维基百科似乎不是指多叉树.唯一相关的术语是 branching factor, 不过谷歌学术无果.

目前我就是在纠结树节点如何保存. 因为每次修改的时候 branching factor 实际上已经确定了, 所以使用数组直接存指针应该就可以, 但是这样每次修改需要拷贝 N 个节点, 在平均 branching factor 为 10 的情况下比使用二叉树模拟空间消耗大两倍.

但是感觉使用二叉树模拟多叉树实现比较复杂, 还没有深入思考. 业界有没有什么成熟的解决方案, 供我借鉴借鉴?

搜索能力比较捉急啊……

[notcome]

我是不是应该先看一下 B-tree……

[fansekey]

不应该是 森林 吗？

[notcome]

@fansekey 啊？森林不就是额外加一个节点多叉树吗？

[TMBest]

《算法导论》里的，用二叉树实现多叉树，左孩子，右兄弟。

[notcome]

@TMBest 我想要建立持久化的存储，如果这样做的话，比如说第五号兄弟需要修改，那么前面四个也需要再备份一遍。在我的应用场景下（即每次增减兄弟都要创建新的版本），这种方式不如直接用数组存指针。

其实一开始我还愣了一下，后来想起来这是我构思的第一个数据结构，不过子结点我竖着画兄弟横着画，嗯，邻接链表什么的即视感。

[notcome]

在钻研 B-tree 之前我还是自己想一想吧。

如果使用二叉树模拟多叉树，即只用叶子节点存储信息，那么问题也就转变成实现一个二叉树，越平衡越好，只使用叶子节点存信息，支持叶子节点的插入和删除，持久化。嗯对。

[MasterYoda]

lsm tree

[ffffwh]

n-ary tree?

[vidon]

ancestry