089_尚硅谷_以太坊理论_梅克尔-帕特里夏树（四）

好，那接下来我们看一个整体的这个树结构的例子吧，这个就稍微的又复杂一点，对吧，大家看看能不能看得懂啊，首先我们先设想一下，我们要构建一个一个MPT数，我们构建一个数肯定就是里面要存存建值，对对吧，要存什么呢？我们存的是这些东西。Do verb，这是一个见识罪，K是do，然后value是verb。然后后面是dog puppy，这是我们前面存过了一个对吧，现在又多了别的，然后下面呢，是doy cor，但是这个嘛，这个狗狗B对吧，那大家知道这个B吗？有个B叫狗壁，或者叫狗狗B，它的名字就叫doy。然后它的那个标志就是对，就是刀具那个标志，就是长得像像一个狐狸犬的那个看起来很得意的那个那个笑容的那只小狗啊，大家可以感兴趣也可以看一看啊，就是狗币应该还是本身还是很很早的一个很老的一个币了啊，就是比特币之后相当于于就是出来的一个山寨币，知道是吧？嗯，对，然后后边还有一个建设队是叫house，呃，So，呃，这是存储的一个码啊，然后我们看一下我们第一步怎么做。

第一步我们是按键。的路径要去做存储和查询，所以说我们先得把这个英文字符先弄成我们以太坊里边真正认识的字符集，对吧？那同样我们还是要把这些路径做一个转码，转成S码表示的这个字符转转换成这些字节，那是什么样的呢？那同样do这里就是646F，好，下面的这个do那就是646F67了，那同样刀具和house也可以转换成它的S，所以现在我们的键值对就变成了这个样子，我们要存的键存的K是646F，后面的值是ver，当然以太坊实际存储大家知道是还做了那个RLP编码，对吧？这个我们先先不说，那个只是一个序列化的过程，所以我们先不不管那么多，现在我们的路径就变成了646F，而我们的值是一个位。

那现在大家想一想，我们在底层的数据库里边存储，到底应该怎么去存呢？我们怎么样去把这样的几个键值队存在我们构建好的一个MPT数里边呢？结果答案给大家写出来了，大家看看能不能看得懂，这是这个可能稍微有点有点复杂啊，首先下面的这个介绍就是每个节点它都是一个，就是像数组一样列出来，其实就是里边是它的每一个，就是大家可以认为是每一个存储位的东西，对吧，还有多少个存储位，就我们说的有多少个插槽，然后里边存什么东西，就会直接放在里面对吧？所以大家看一下能不能看得懂，这个可能会稍微有点难，因为这个太复杂，所以说我也我也就是。

呃，比较懒，就是画图比较费劲嘛，这个确实也是画不出来这么复杂的图，所以直接这么看的话，大家可能会有点有点看不懂啊，那我们来看另外一个例子吧，这个可能会会好好懂一点啊，或许会好懂一点，这么一个图，这个太太费劲了，这个我肯定画不出这么漂亮的图，好我们看一下这个是他所说的，就是传说中的world state tree，也就是我们所说的世界状态数。那这个我们先不管它世界状态不世界状态，我们就把它当成一个MPT数。那这个MPD数里面，大家看到是不是有很多个节点啊。那这个节点就有不同的类型，对吧？那节点它们之间互相连接，从上到下就构成了一个竖结构，我们首先从上面来开始看吧，上边是一个根节点对吧？而且这个根节点的类型是一个extension node，是一个扩展节点哦，大家想到那扩扩展节点它有什么特点呢？

他要存一段压缩的路径，对吧？编码之后的路径，然后后面那个值会指到下一个节点上去，这是一个扩展节点，所以大家可以看它存的东西是什么呢？它是把我们说的那个压缩路径的那个前缀单独拎出来了啊，没有放在一起，实际上我们存储的时候大家知道是合在一起的，对吧？他这个为了大家看的方便，就单独拎出来给大家看成是两个两个内容，两个元素了，但事实上它会存在一起，我们看一下它的prefix，也就是前缀给的是零。他为什么给零呢？因为大家看它后边的这个shared nis，也就是说压缩起来的那些路径对不对，压缩起来的路径是A7偶数对吧，偶数还是扩展节点，所以大家还记得吗？我们定义的时候偶数扩展节点。

就是0000对不对，然后他还要补零对不对，所以它就是就是零对吧，所以啊，当然这个里面他没有补灵，他他说的其实就是我们单纯的前缀，他没有考虑这个补灵的问题，但我们知道它是会补零的，所以它的前缀是一个零，然后这里存了一个A7，然后它会后边存一个哈希指向下一个节点，那我们看一下下一个节点是什么。下一个节点是一个branch branch not就是。分支节点对吧，为什么呢？因为大家发现这个地方它没有办法去直接压缩路径了，因为它有各种各样不同的路径出现了，对吧？那这里边有的是一，有的这个值是一，有的这个是七，有的这个是F，所以说它就岔开了，那这里边如果是一，这里这个路径对应的它就直接连到了一个叶子节点上，大家看到。

这个叶子节点呢。大家看它的prex是二。二是什么意思呢？啊，它其实这里边是列出来的啊，大家看这里prex对吧，二代表的是叶子节点，而且是even是偶数对吧，偶数。所以这是因为它后面压缩的这个路径是偶数对吧，1355，所以它的前缀是二，然后后边直接yes节点吧，直接就有value了对吧？所以大家会看到他为什么管这个叫世界状态数呢？所以它存的应该就是一个地址，一个value是不是？

它就是这样，就是这样存的，所以大家看这里，我们从这个根节点到这个分支节点，再到这个叶子节点，它表示了一个什么样的键值，对存储呢？它的K就是这个路径，就是从前面压缩出来的路径A7。然后往下走。一对不对。然后1355，它的值是45个ETH，所以大家看我们要存储的就是A71135545个ETH，这样一个键是对。这就在MPT这个煤块尔帕特比加数里边有这样的一个表达，就是这样的一个过程，那同样大家就可以理解在这个里边，就是还有别的第二个，比方说这个A77D337，这个K是怎么去寻址呢？

A7是一开始的对吧，这是大家都公用的，都压缩的路径，A7它下一个是七，那我是不是要走到这儿来，对，根据我的路径是七，所以我直接找这个插槽位置，这个index是七的位置，往下去找，找到的那个哈希，我就找到了接下来的这个节点，这是一个扩展节点，所以它又压缩的路径，那我是不是直接就读它这个压缩路径就可以了，所以是A77D3对吧，D3，然后又有。扩展节点的话，它又指向下一个节点，又是一个分支节点，我们是第337对吧？所以我就D33指到三，然后一看这个叶子节点果然存的是一个七，对吧？所以这就是A77D337。然后它的prex，这是叶子节点，而且是奇数，所以是一个三啊，后面这里还专门画了一个方框，意思就是三和七要合并在一起的，对吧？到时候我们存储的时候真正是要合并在一起的，那最后它的value是一尾，所以我们看第二个账户，这个KA77D337 value是一位，这就是这样一个存储，同样大家可以看到第三个账户，我们从这边去寻址，A7F，然后93651.1个1TH，对吧，所有的这些都在叶子节点里面保存，那最后一个是A77D397，然后从这边分叉过来，所以这也是另外的一个叶子节点。

所以大家就可以看到，我们存真正存的时候存的是这样一个东西，所以我们在数据库里面存的是什么呢？我们存的是这样一个节点，然后它的内容是什么呢？它的内容就是00A7，然后后边是下边这个节点的哈希，对不对？所以这是我们第一个根节点存储的内容，第二个branch not，它存储的内容是什么呢？那前面零这里没有的话，那就空了，对吧，这是空，然后这个节点的哈希。

这些都是空，然后存下一个这个扩展节点的哈希，后面都是空，然后再存这个叶子节点的哈希，Value没有是空，所以这是我们第二个分支节点的一个存储，那叶子节点怎么去存呢？它存的是prex是二，那后面是要补零的对吧，它存的是201355，然后后边存储了它的value对吧？啊所以大家可以看到，就是我们具体在底层数据库里面到底怎么去存一颗MPT树就是这样去做的，好那现在大家再回来，大家看得懂这个了吗？大家先瞄一眼，看看能不能根据我们前面那个直观的图的解释，还是看图比较舒服是吧，这个直接写出来确实是会比较比较难以理解，但是如果大家看那个图已经有了这个概念之后，大家看看能不能看着这里描述的其实就是说每一个节点到底存什么，对吧？

再根据这里存着的这些东西，能不能画出那棵树来？大家要想画的话，可以自己自己就是找张纸或者怎么样的画一画，看看能不能可以可以把这个作为一个作业给大家留着，大家试图去把这棵MPT树构建出来，好，那我给大家来讲解一下吧，这棵树到底是什么样子呢？这棵树的样子是。首先我们有一个根节点，根节点里边啊，当然了，这里就是这里就是说我们的根哈希了，对吧？根的哈希直接就会对应到一个节点去，对应的节点里边存着什么内容呢。

它存着的内容是前边是幺六，后边存储的一个值是哈希A的哈希，那大家可以想它两个元素。所以这个跟节点应该是个什么节点，它这里有两个元素，咱们前面说的节点类型有哪几种？扩展节点，分支节点，叶子节点，它应该是哪种？当然不是空节点对吧？对，大家一看扩展节点对吧？两个元素的就是叶子节点和分支节和扩展节点会是两个元素，那它显然根节点啊，下面肯定它指向的是另外一个节点，它是扩展节点，所以那么前面这就是一个enco的pass了，对吧？那我们要来解析一下，它为什么存了一个幺六呢？它就存了一个字符，呃，存了一个字节对吧？那大家就想到既然是编码压缩编码之后的这个ECO里的pass它的路径。

那第一个字节里边的第一个E一个一个半字符前四位应该是前缀对吧？所以它的前缀是一对吧，那大家就想起来了，那对吗？它的扩展节点，然后如果要是前缀是一，那说明它的路径长度本来是奇数嘛。那大就会想到了，那是不是后面它跟的就是一位的路径长度啊。对，就就是只有一个路径对不对，所以就跟在后边了，所以这个六是不是就是我们第一个路径。是不是这样，所以大家可以看，为什么我们会把六存到根节点里边，然后把它作为一个扩展节点呢？因为大家看我们要存的所有的这些节点的路径，是不是第一个都是六啊，所以是不是我们直接就把它相当于压缩起来了，不用分叉了，对吧？啊，所以会有这样一个存储，那只有这样一个路径，所以我们把它合在一起，奇数幺六，这样就可以了，那么接下来它会指向下一个节点。

下一个节点就是它，它存的是哈西A，那么就指向了A节点对吧？那么A节点存的是一个什么东西呢？大家看一长串啊，A是个什么节点，分支节点，对，一看到一长串，这肯定就是分支节点，因为它这里发现分叉了，那么我们看一下后边第二位是为什么你前面第一位六，然后下下一个节点就直接分叉了呢？我们看看本来要存的东西哦，一个四一个84448确实分叉了对吧。所以这里我们A这里是用了一个分支节点来把它构建出来的，那大家可以看到哈希B为什么在这个位置，它要指向B这个节点，对吧，后面指向C这个节点，哦对，因为这里是四和八，我们数一下。

第一个位置应该是零对不对？所以是001234，所以在索引是四个位置上存了一个B的哈希，那是不是就代表你要找下一位，路径是四的话，你就去B那找吧，对吧？所以六四就会跳到哈希B这里来，对不对？同样道理，C的位置那就应该是八了，对吧？45678，所以你要找六八的话，你就到C节点那里去找。同样，呃，那我们接下来再看B是个什么东西，B变成两个元素了，而且后面这个元素是另外一个节点D的哈希，那它应该是个扩展节点了，对吧？扩展节点，所以我们看它扩展是要扩展一个什么东西呢？我们看一下D这里它存着的内容是006F。

那大家一看前面这个零零，那应该能想到这肯定前缀是零的话，这应该是偶数，对，而且是扩展节点，所以它还补了一个零，对吧，所以零零都是没用的，就是这两个零都不是他的路径，它的真正的路径是什么呢？后面的6F，好，我们到这个本身的T里边来看一下。前面我们大家还记得吧，六四对吧，下来的从根节点到A，六四到了B这里，然后下面六四大家看是不是全是6F啊对，所以就把它压缩了，所以就变成了一个扩展节点，那这个扩展节点接下来又会指向一个D，那大家就会看到D就变成了一个分支节点，又是一长串对吧，我们看看为什么它会分支呢？6F后边哦，大家看。

有些没有了，有些是六七对吧，所以这个时候他也做了一个分值，为什么呢？因为我们要存值的，对不对对，我们这里是本身是要去存值的啊好，那么接下来，接下来大家就会看到我是不是就应该在六的这个位置位置上去有一个哈希，所以大家看0123456，所以646F6到这儿再去分下去，分下去之后大家就会看到下一个是不是都是七啊，所以又把它作为一个扩展节点再存起来，所以大家看它是只有一个嘛，基数，所以是一期前面是一对吧，然后这里又一个扩展节点，6F67之后再存又是一个分支节点。

那因为你这里有些没有了，有一个还有所以没有的那个存在这里party，所以大家看到这里是不是。六四到B对吧，然后去找到B6F，再找到D，这里又是六，然后找到E7，然后找到F，直接存到是不是就是646F67存的内容就是就是这里好，这就是我们找到了它对应的值，那么同样它这里如果要再去分支的话，还有一个分支在六这个位置又分出来，分到G上，后面还有一个三五，那大家可以想到三是前缀的话，是代表一个只有一个路径的子节点对吧？呃，叶子叶子节点对吧。奇数的叶子节点是三，那后边它的路径是五，所以就跟了一个6646F6765，它的内容是coin。

啊，这就是我们这样一个存储的过程啊，当然我们在前面最早的这个是从一开始A这里就分叉了，对吧？A这里如果要是走哈C这个节点去访问的话，那就是六，C这里应该是八，对不对，六八到C这里看哦，全存下来了，直接就是叶子节点了，对不对，它是二零，这是一个叶子节点偶数，所以它的路径就是686F727365，然后存的值是story对吧？所以这就是我们这这个整个这个数结构的一个完整的解释。呃，可能会有点绕对吧？呃，大家可能会觉得有点不好理解，但是我觉得有些同学如果要是能跟着我的思路把这个整个的去捋一遍的话，特别是自己能去画一画的话，应该这个MP就完全掌握了啊，这个确实确实比较难啊，所以说一开始我们在做这个理论介绍的时候，他也跟我们编程完全没关系，对吧，我们根本不需要了解这么多东西，所以一开始我们在做这个介绍和这个理论讲解的时候，其实跟都没有，没有就是接触到这部分内容，但是如果我们这两天我们是要去讲这个黄皮书，讲源码这些东西的话，那这些东西确实不想不行，就是这个确实还是得拿出来单独讲一下，好看一下时间啊，哇，我们还来得及吗？

好，剩下不多了，我们快速过一下吧，好，那到此为止，我们其实就已经完全了解这个所谓的维克尔帕下树这么高大上的一个东西到底是个什么东西啊，确实里边还是有点难，对吧？啊，确实有点绕，但是其实对于大家而言，只要能理解清楚维克尔树是什么，帕特里下树是什么，然后以太坊是怎么样把这两个结合在一起，然后就实现了，我们既可以按照字典去按照P值去查询，同时还能够利用它的哈希去做校验啊，大家只要能理解到这儿就行了，至于它里边的这些就是啊，字符什么的，大家能理解就理解，不能理解的话就就算了啊。好，那么我们接下来我们再来多讲一点，就是关于以太坊里边的树结构，这里给大家一句一句结论，就是以太坊里边。

所有的梅克尔数都是MPT都是梅克尔判断一加数，它没有用到单独的梅克尔数，那在一个区块的头部里边，一个区块的头部里边有三棵煤克，就是MPT梅克帕加树的树根，那这就是之前给大家提到过的啊，一个叫做state root。

一个叫transaction route，还有一个叫re receive root，所以一个就是状态树树根，一个是交易数的树根，还有一个是收据树的树根，啊这就是我们说的说的三颗MPT的树根，那大家可以看到就是整个一个区块头里面，大家可能见过这个图对吧？一个区块头里面有哪些内容呢？除了我们大家都已经很熟悉的，它的副节点的哈希，它的NUS，它的时间戳，还有什么这个书块哈希，乱七八糟这些东西对吧？除了这些之外，还有三个很重要的就是三棵煤块树树根，那这一个通过这一个树根大家就会看到，我们就可以直接访问到以太坊底层数据库里边的这一棵梅克尔树，梅克尔帕特里下树，那大家可能就会想，那这个state root，它其实代表我们整个一个全局状态的一个一个内容，对吧，我们之前不是讲了吗。

全局状态，它是每个账户里边的账，所有状态的一个集合，一个总和，那我们看一看它到底应该包含哪些内容啊，这里又是一个一个讲解啊，就是首先状态数它是会随时更新的，那么它存储的键值对。大家是不是到时间准备想要下课，应该可以把这个讲完吧，可以是吧，好呃，状态数呢，它存储的键值对，大家看一下这个表表达啊，这个表达其实也是很专业的一个表达了，这个等一下我们在红皮书里边应该也能看到，它存储的键值段是什么呢？是一个是pass，一个是value，它的pass是什么？就是以太坊地址的一个哈希，这是它的pass，然后它的value是什么呢？是它的。账户对应的以太坊账户的所有数据的经过RLP编码之后的那个序列化之后的字符串，所以这是它真正状态数里面存储建质对存储的是什么？存储的是这个东西，那这里呢，靠的就是四个元素组成的数组了，前面我们黄皮书里面见到了，对吧？黄皮书里面说的这四个到底是什么东西？Non balance storage root code就是这里面。

存储到这里面的东西啊，所以啊，那除了状态数之外，还有存储存存储数，存储数是什么东西呢？因为我们这里边已经看到count的四个元素里边有一个，它就叫storage root，又是一个root，所以是不是它也是一棵树的树根啊，而且这棵树还应该也是一个没开尔帕以下树，对吧？所以大家就会想到这是一棵存储树，那我们单独拿出来说，它是保存所有合约数据的地方，我们的数据全存在对应的这个空间里面，当然在本身的账户的这个空间里面，它只存了一个数根，那当然它对应的东西呢，那就又存在别的地方了，哈希出去了，对吧？每个合约账户都有一个独立隔离的存储空间，每个账户都有这个东西，大家互相不能访问，所以这个是有这个地址运营空间里面去处理的，呃，另外就还有交易数和收据数，这个是针对区块来讲的。

每个区块都会有它单独的一棵交易树和一棵收据树，那交易树它的路径是什么呢？这里边就跟状态数不一样了，它的路径直接就是它的transaction index，也就是说在这个区块里边交易是要排序的，对吧？所以它就会有一个索引值，有一个序号。它的序号做RLP编码之后就是它的路径。那当然了，那大家想他的那个value会是什么呢？肯定就是那个交易哈希了，对吧，所以呃，他这个剑指队，他的这个路径只有在挖矿的时候才能确定，那大家应该能够想到你既然它的key就是它的这个跟他的transaction在块里边的位置有关，那我不不挖矿之前怎么能知道这块里面它这个交易在哪个位置啊，所以说必须在挖矿的时候才能确定，一旦出块之后就不太能改了，所以说整个块里边的交易数都是确定的，大家如果去访问历史的话，这个就是不能改这个东西啊，同样就还有交交易数了，交易数它的表示路径也是就是它的index的一个RLP，所以当然也是挖矿，当然这个就是应该是既然是收据数嘛，它里边的内容是你真正出块之后才能够才能够确定的，而且肯定是不能再更改的，对吧？好，最后再跟大家说一句吧，把这个图看一看，这个图。

说这是什么呢？上面这就是我们的区块头，区块头里边有一个叫做state root的东西，就是我们所说的状态数，对吧？那我们说状态数是一个世界状态，它包含了所有账户的状态的一个集合，所以它下边的数，那是不是根据我们前面说他存的东西是每个账户的地址作为K对吧？哈希之后作为K，然后存的是每个账户的内容，就是它的数据内容，所以大家可以想到我是不是访问一个账户的时候，就要按照地址做哈希，哈希之后按照我们那套规则对吧？根据这一个去去找它的路径，找找找找找，我可能就找到了某一个它的叶子节点。

它的yes子节点里面存的东西是什么呢？是这么一个东西，大家看，这就是这个账户的它的account的内容，它的内容是一个not，一个balance，一个cold hush，然后还有一个叫做storage root的东西，这些是存储在这个对应的空间里面的，那同时呢，Code harsh呢，只是一个哈希，只是一个32字节的哈希，对吧？它还对应到真正我们code的存储空间去，而我们的storage root呢，它本身又只是一颗维R帕以下树的树根，它对应的又是我们如果想要去在我们的合约的存储空间里面查一个状态变量，那你就到它对应的这个账户的地址里边去，再到它对应的这个story数里边，根据它的K查查查，查到对应的值。所以这张图出来之后，大家是不是整个。

头脑里边就对我们整个以太坊的这种数据存储有一个大致的概念了，对吧，这个可能就会清晰多了，所以前面我们介绍那么多绕来绕去的东西，都为最后这这张图这得瑟给给大家一个做个铺垫，所以大家只要能把这张图能弄明白，我们这节课就算是完成目标。