本文翻译自 IPFS 社区教程 ProtoSchool。ProtoSchool 是一个可以交互式学习 IPFS 编程的网站,涉及代码的部分大家可到该网站上直接运行测试!
本文接上篇 IPFS 去中心化数据结构(三)。
LESSION 5 - 默克尔树和有向无环图(DAG)
正如我们所讨论的,去中心化的 Web 依赖于链接的数据结构。让我们来探索一下它们的样子。
默克尔树
默克尔树即“哈希树”,是一种树形数据结构,其中每个节点都是哈希值。
1 +--------+
2 | |
3 +---------+ root +---------+
4 | | | |
5 | +----+---+ |
6 | | |
7+----v-----+ +-----v----+ +-----v----+
8| | | | | |
9| node A | | node B | | node C |
10| | | | | |
11+----------+ +-----+----+ +-----+----+
12 | |
13 +-----v----+ +-----v----+
14 | | | |
15 | node D | | node E +-------+
16 | | | | |
17 +----------+ +-----+----+ |
18 | |
19 +-----v----+ +----v-----+
20 | | | |
21 | node F | | node G |
22 | | | |
23 +----------+ +----------+
在默克尔树中,节点通过内容地址(哈希值)指向其他节点。当我们通过加密哈希运算数据后,我们会得到一个“哈希值”或“内容地址”,我们可以将其视为一个链接,因此一颗默克尔树是链接节点的集合。
如前所述,所有内容地址都是唯一的。在上图中,节点 E
包含对 节点 F
和 节点 G
的哈希引用。这意味着 节点 E
的内容地址(哈希值)对于包含这些地址的节点是唯一的。
有点晕么?让我们把它想象成一组文件夹。如果我们通过哈希算法运行文件夹 E,同时它包含子文件夹 F 和 G,我们获取的内容生成哈希值对其当前内容是唯一的。如果我们删除文件夹 G,就像 Grace 从她的小猫照片中删除那个胡须,则以前称为 E 的文件夹不再具有相同的内容,因此它会得到新的哈希值。
在构建上面的树时,根节点的最终内容地址(哈希值)对于包含该树一直向下的每个节点的树是唯一的。 如果任何节点中的数据即使是单个字节发生改变,则改变的节点的哈希值也将改变,其所有父节点的哈希值都会被改变。
你可能注意到了,程序员将始终需要从底部向上来构建这棵树,从叶节点到根节点。
有向无环图(DAG)
DAG 是“Directed Acyclic Graph”的首字母缩写。这是一种描述特定类型的默克尔树(哈希树)的独特方式,其中树中的不同分支可以在单个前向方向上指向树中的其他分支,如上图所示。
(完)