知识卡片

普通读书笔记卡 · 2914.c

IAVL版本化

理解等级:未标注

Cosmos-SDK 把 Merkle 树和自平衡二叉搜索树组合成 IAVL+ 树:继承 AVL 树的自平衡,查找、插入、删除都是对数复杂度,又能生成存在性和非存在性证明。树中每个节点不可更改,修改某个节点时生成新节点替换它,被替换的节点成为孤儿节点;配合节点中保存的版本信息,就能方便地实现版本化和生成快照。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《区块链架构与实现:Cosmos详解》第6章《Cosmos-SDK的架构设计》(源文件:_epub-src/OEBPS/Text/chapter006.html) - 结论依据:原文说明 Cosmos-SDK 组合 Merkle 树和自平衡二叉搜索树构建 IAVL+ 树,查找、插入、删除为对数复杂度;树中每个节点不可更改,修改时生成新节点替换,配合节点中的版本信息容易实现版本化和快照,被替换的节点成为孤儿节点。 - 原始内容:虽然IAVL+树可以随着节点的加入和删除不断更新,但是树中的每个节点是不可更改的。……这种更新方式配合在节点中保存的版本信息,容易实现IAVL+树的版本化和生成快照的功能。