内容简介：本文翻译自 IPFS 社区教程本文接上篇正如我们所讨论的，去中心化的 Web 依赖于链接的数据结构。让我们来探索一下它们的样子。
本文翻译自 IPFS 社区教程 ProtoSchool 。ProtoSchool 是一个可以交互式学习 IPFS 编程的网站，涉及代码的部分大家可到该网站上直接运行测试！
本文接上篇 IPFS 去中心化数据结构（三） 。
LESSION 5 - 默克尔树和有向无环图（DAG）
正如我们所讨论的，去中心化的 Web 依赖于链接的数据结构。让我们来探索一下它们的样子。
默克尔树
默克尔树即“哈希树”，是一种树形数据结构，其中每个节点都是哈希值。
+--------+
| |
+---------+ root +---------+
| | | |
| +----+---+ |
| | |
+----v-----+ +-----v----+ +-----v----+
| | | | | |
| node A | | node B | | node C |
| | | | | |
+----------+ +-----+----+ +-----+----+
| |
+-----v----+ +-----v----+
| | | |
| node D | | node E +-------+
| | | | |
+----------+ +-----+----+ |
| |
+-----v----+ +----v-----+
| | | |
| node F | | node G |
| | | |
+----------+ +----------+
在默克尔树中，节点通过内容地址（哈希值）指向其他节点。当我们通过加密哈希运算数据后，我们会得到一个“哈希值”或“内容地址”，我们可以将其视为一个链接，因此一颗默克尔树是链接节点的集合。
如前所述，所有内容地址都是唯一的。在上图中， 节点 E 包含对 节点 F 和 节点 G 的哈希引用。这意味着 节点 E 的内容地址（哈希值）对于包含这些地址的节点是唯一的。
有点晕么？让我们把它想象成一组文件夹。如果我们通过哈希算法运行文件夹 E，同时它包含子文件夹 F 和 G，我们获取的内容生成哈希值对其当前内容是唯一的。如果我们删除文件夹 G，就像 Grace 从她的小猫照片中删除那个胡须，则以前称为 E 的文件夹不再具有相同的内容，因此它会得到新的哈希值。
在构建上面的树时，根节点的最终内容地址（哈希值）对于包含该树一直向下的每个节点的树是唯一的。 如果任何节点中的数据即使是单个字节发生改变，则改变的节点的哈希值也将改变，其所有父节点的哈希值都会被改变。
你可能注意到了，程序员将始终需要从底部向上来构建这棵树，从叶节点到根节点。
有向无环图（DAG）
DAG 是“Directed Acyclic Graph”的首字母缩写。这是一种描述特定类型的默克尔树（哈希树）的独特方式，其中树中的不同分支可以在单个前向方向上指向树中的其他分支，如上图所示。
（完）
以上所述就是小编给大家介绍的《IPFS 去中心化数据结构（四）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
可计算性和计算复杂性
朱一清 / 国防工业出版社 / 2006-4 / 18.0
本书深入浅出地介绍了研究可计算性的四个主要模型以及四个模型彼此之间的关系：介绍了计算复杂性的基本概念和重要的研究方法与一些研究成果。内容涉及递归函数、图灵机、λ演算、马尔可夫算法、计算复杂度的分类、NP完全理论、非一致复杂性等。分述于十章,书中附有习题。 本书可作为广大有志于突破计算复杂性研究僵局——“P=NP？”的科技工作者,计算机科学和元计算机科学工作者,数学和元数学工作者以及大......一起来看看 《可计算性和计算复杂性》 这本书的介绍吧!
