V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 4345 days ago, the information mentioned may be changed or developed.
需要建立一个类似文件系统的数据结构, 要求能追踪全部的版本信息. 想来使用一个可持久化的多叉树应该比较方便 (难道还有别的方法吗……)
又一次手残还没打完就发送了……
然后我发现不知道怎么翻译多叉树, 谷歌说是 multitree, 看了一下维基百科似乎不是指多叉树.唯一相关的术语是 branching factor, 不过谷歌学术无果.
目前我就是在纠结树节点如何保存. 因为每次修改的时候 branching factor 实际上已经确定了, 所以使用数组直接存指针应该就可以, 但是这样每次修改需要拷贝 N 个节点, 在平均 branching factor 为 10 的情况下比使用二叉树模拟空间消耗大两倍.
但是感觉使用二叉树模拟多叉树实现比较复杂, 还没有深入思考. 业界有没有什么成熟的解决方案, 供我借鉴借鉴?
搜索能力比较捉急啊……
又一次手残还没打完就发送了……
然后我发现不知道怎么翻译多叉树, 谷歌说是 multitree, 看了一下维基百科似乎不是指多叉树.唯一相关的术语是 branching factor, 不过谷歌学术无果.
目前我就是在纠结树节点如何保存. 因为每次修改的时候 branching factor 实际上已经确定了, 所以使用数组直接存指针应该就可以, 但是这样每次修改需要拷贝 N 个节点, 在平均 branching factor 为 10 的情况下比使用二叉树模拟空间消耗大两倍.
但是感觉使用二叉树模拟多叉树实现比较复杂, 还没有深入思考. 业界有没有什么成熟的解决方案, 供我借鉴借鉴?
搜索能力比较捉急啊……
 |
1
notcome OP 我是不是应该先看一下 B-tree……
|
 |
2
fansekey Jun 4, 2014
不应该是 森林 吗？
|
 |
4
TMBest Jun 4, 2014
《算法导论》里的，用二叉树实现多叉树，左孩子，右兄弟。
|
|
5
notcome OP @TMBest 我想要建立持久化的存储，如果这样做的话，比如说第五号兄弟需要修改，那么前面四个也需要再备份一遍。在我的应用场景下（即每次增减兄弟都要创建新的版本），这种方式不如直接用数组存指针。
其实一开始我还愣了一下，后来想起来这是我构思的第一个数据结构，不过子结点我竖着画兄弟横着画，嗯，邻接链表什么的即视感。 |
|
6
notcome OP 在钻研 B-tree 之前我还是自己想一想吧。
如果使用二叉树模拟多叉树，即只用叶子节点存储信息，那么问题也就转变成实现一个二叉树，越平衡越好，只使用叶子节点存信息，支持叶子节点的插入和删除，持久化。嗯对。 |
 |
7
MasterYoda Jun 4, 2014
lsm tree
|
 |
8
ffffwh Jun 4, 2014
n-ary tree?
|
 |
9
vidon Jun 5, 2014
ancestry
|
Select Language