版本比较

密钥

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

...

增加节点时,如上图,分别增加了 P ,其父节点为 J 和 M,它的 dag 结构和 accumulator 如下,可以看到 P 挂在 J 和 M 下,而 J 和 M 映射到 accumulator 叶子 3 这个节点,因此,需要对 3 所对应的叶子节点重新生成后续节点:

...

例子二

增加 P 和 V 节点,V 节点挂在 K 和 L 下,而 K,L 和 D 下,D 对应了 1 节点,而 K 和 L 对应了 accumulator 的 叶子节点 2,因此从 2 开始,需要重新生成新的 3 和 4:1 开始,需要重新生成后续的 3, 4, 5:

...

这里可以看到保存广度优先搜索的队列好处就是某个节点新加入了子节点,那么对其拓扑顺序是会有影响的,如果不保存搜索使用的队列,那么就需要回溯父节点,uncle 节点(例如 V 的加入,导致跟 L 相关的拓扑顺序变化,因此需要去找 L 的父节点和兄弟节点,因此需要回溯到 的加入,导致第二层的拓扑顺序变化,因此需要去找 D 的父节点和兄弟节点,需要回溯到 Genesis 节点,再重新广度优先遍历),逻辑比较复杂,因此这里选择了保存广度优先搜索使用的队列。

...