JSON 树存储格式

Question

这更像是一种概念性的问题，用于存储和更新树的数据。让我们举一个常见的例子 - 来自 React 之类的虚拟 dom。

表示 dom 的树的常见 json 存储如下所示：

{
nodeId: 'nodeId1',
...nodeData,
childrenNodes: [
{
nodeId: 'nodeId2',
...nodeData,
childrenNodes: [...]
},
...
]
}

所以，我正在查看一棵带有 BFS 或 DFS 的树(我相信 React 做 DFS(来找到一个特定的元素来改变它。

同一棵树的另一个可能的实现可能是我将其存储得更像是哈希表查找格式：

{
nodeId1: {...nodeData, childrenNodes: [nodeId2]},
nodeId2: {...nodeData, childrenNodes: [nodeId3, nodeId4]},
...
}

因此，获取特定节点可能是 O(1(，因为我们只是对所有节点 ID 进行哈希处理，而不必每次遍历树。

对于像虚拟 dom 这样的东西，我们可以存储数万甚至数十万个可能元素的状态，我认为以一种方式存储另一种方式可以忽略不计，但我们可能不希望在内存中同时拥有这两种结构(尽管也许两者都有很好？

假设两个结构都为每个节点分配了 ID，那么在这两种情况下添加和删除节点都相当容易。我们也可以假设在这两种情况下，每个子节点都有一个对其父节点的引用。

我要讨论的问题是，在一般情况下使用哪种结构更有意义，或者如果我们专注于尽快更新一个节点或一组节点，那么跟踪这两种结构是否有意义？如果我要从头开始制作一个框架，我可以看到这两种情况对不同的场景都很有用，但我必须记住有限的存储设备，如旧手机。

Answer 1

没有人回答，所以我只是根据额外的研究和观察给出我的意见。

在某些情况下，提供的哈希解决方案在访问节点时会更快。但是，可读性和将此解决方案扩展到其他可能的集成使其结构更难处理。如果我要使用这些 id 数组，我希望将其作为一个单独的结构来执行，仅用于搜索，而不是一次更新多个节点。

在大多数情况下，更详细的树轮廓将有意义且更易于使用。