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

我们上节课已经说了，在以太坊的系统里边，它是把梅克尔树和它的底下树结合在了一起。怎么样的结合法呢？它的结合方式就是帕特里下树里边指向下一个节点的那个指针存的不是简单的地址，而是它的哈希。那通过这个哈希在以太坊里边，那既是一个地址的指针，又可以做这个内容的校验，所以就相当于实现了梅克尔树和帕特里夏树的一个结合，呃，那这个过程大家大致知道它是这么做的了，但是大家还会有很多问题，那就是说不是说它这个它实现的MPT里边的帕里加数不是简单的奇数数吗？那奇数数里边怎么压缩的还没说呢，对吧，然后他还不是那么简单的一个压缩，他还做了别的一些一些花样的优化，那到底是怎么做的呢？那接下来我们给大家讲一下这部分内容，首先我们先来看一下MPT里边的节点分类。

MP里边它跟传统的这个，呃，字典数也好，或者是奇数数也好就不一样了，它定义的节点类型很多，首先啊空节点这个就不说了，这就是就是空字符串嘛，对吧，表示空字符串，其他大家也可以去随便定义这个呢，别的剩下的三个是主要的我们能够用到的数据类型，就真正去存储数据和在寻址的过程当中要用到的节点，哪三种节点呢？首先分支节点，分支节点它叫branch。这个节点就是我们前面提到的完整的这种字典数里边的节点，在以太坊的系统里面，因为它是has字符串字符集，所以说它就有17个元素，从零到16，呃，从零到15啊，就是前16个元素是存储我们下一个节点对应的哈希对吧？那它的这个对应的index就代表我们的has的这个角标，选址的这个角标，那同样最后就还会有一个VT，那就是可以有一个value，或者是可以有一个，呃，就是或或者是可以没有对吧，可以是now，也可以是value，另外还有两种节点，一种是yes节点，Yes节点大家比较好理解，就是你到最后寻是循完了，那我要直接拿出十了，对吧？啊，但是这里的叶子节点呢，跟我们平常所说的叶子节点也有一些不同，另外还有一个可能，之前我们接触不到。

呃，它叫扩展节点extenansion，这是一个什么东西呢？简单说就是要实现我们技数数里边把前缀做压缩的这个功能的一个节点，就是我们把它路径里边一串路径要压缩起来，压缩起来存成一个什么样的东西呢？存成一个扩展节点，那这个扩展节点里边它的内容是两个元素，它里面存在两个元素，一个叫做编码路径。

Pass。啊，这是什么东西呢？那大家直观的就能想象得到，这就应该是他把那个路径压缩了之后的那个值对吧？因为我现在不靠那个插槽的角标去读了，我肯定得把那个显示的存出来才行，所以它存的是这个东西，另外就还会存一个键，一个P，那这个键是什么呢？就相当于是会到我们下一个节点的一个哈希了。所以是这样的一个东西，与与它对应的叶子节点也有相类似的数据结构，它的数据结构是一个编码路径，行扣，Pass，还有一个是值，因为是叶节点嘛，到这里不会再指向下一层了，所以那么它的value就会写在这里，对应到后面的一个节点。那么有这么几类节点，它怎么样去实现我们所说的能够实现这种压缩编码，能够实现这种路径的压缩，对吧？压缩前缀，前缀术怎么实现的呢？我们看看它。

数据结构里面的优化过程啊，哎，这个就又会比较复杂一点，我们跟着这个思路一句就是一条一条的来看，首先对于我们前面说的，假如我们要存一个V32，它转成he字符之后，64个字符。那它的这个路径长度本来就是64对吧。对于他来讲，很有可能在某个地方，对于就是在某个节点，这个路径如果是64个长度的话，在进行到某一步的时候，访问到某一步的时候，很可能就发现，诶，下面有某一段，有某一段路径，它不会再分叉了，就像我们刚才看到的那种情况，对吧？当然也有可能从某一段开始，下面就全部分叉，直接到我们的值第节点了，这都是有可能的，所以这个东西是很难避免的，他不可能每一步都分叉，真要每一步都分叉的话，我们用字典数就完了嘛。

所以接下来就说这个解决方案，我们当然可以依然用标准的分支节点来表示，怎么表示呢？那大家就会想到，就像我们前面存储这个dog哈的时候，我们给每一个节点都扩展出16个插槽来，然后呢，用得着的插槽存下一个节点的哈希，用不着的呢，那存一个档嘛，对吧？所以这就是一个最标准的实现，我们当然可以这么实现啊，但是呢，这个就有点蠢了，对吧，明显这就是一个资源的浪费，所以呢，我们就通过设置一个扩展节点，就可以有效的缩短他的访问路径，这个时候他怎么样去。缩短访问路径呢，它的做法就是把乳常的这个层级关系，一层一层的这个访问路径直接压缩，压缩成一个键值对，它的键值对的关系，那它的K就是一个。

他之前到现在为止可以压缩的这部分路径，这是K，那value，那就是如果它是。接下来要指向下一个分支节点的话，那就存储它的哈希。如果说。它对应的是一个，呃，就是我们真实的值的话，是已经是存。遍历完毕路径的一个yes节点的话，那就存它的值，所以是这样的一个存储过程。那大家就可以想到像咱们之前的这个dog puppy，如果要是把它做这个压缩处理的话，我们就可以构建一个。就可以对构建一个对应的这个压缩之后的。存储结构对吧？大家可以想象得到，我们在这个root和puppy之间就可以把这么多步都给压缩成一个扩展节点，好，那等一下我们还是看图来看它到底是长什么样吧，呃，那另外就是说在这里我们就就详细的。

来可以说一下扩展节点和yes节点的区别，那扩展节点它的内容形式是included pass和K，所以它的included pass包含的就是下面不分叉的那部分的路径了，那K呢，就是指向下一个节点的指针，也就是哈希。yes节点呢，就是某节点在从这个节点之后它就再也不会分叉了，所以我就把之后所有的路径全集成在里边。所以那它同样也是这样的一个内容形式，跟扩展节点一样，因Co pass后面是一个value，第二个元素就是自己的value，对吧？所以如果我们用这种方式去存刚才的那个dog puppy的话，它存起来就非常简单了。

当然大家可以看到，就是我们都不需要扩展节点了，对吧？因为我们有叶子节点，它之后不分叉了，直接就存到叶子节点里面就可以了，那从根节点，但是这里我们默认根节点可能还会有别的分叉出去，对吧？所以我们没有把根节点之间合并在一起，那从根节点出来之后怎么去访问呢？啊，第一个六访问，访问到这个对应的这里存着下面的这个哈希对吧，那访问到这里来之后，这里存着的就是一个剑指队。那么它是什么呢？前面存一个encoed pass，就是46F67全存在这里，这相当于是把K都存在这里了，对吧？啊，这就是大家更直观的一个k value的一个存储了，所以第二个元素就是它的值帕。啊，这个就简单多了对吧？啊，所以大家可以看到，这就相当于是实现了我们所说的压缩前缀数，啊，这其实就是奇数数，就是用这种方式实现出来的。好，那接下来我们再来看奇数数呢，前面我们提到它本身还有一个问题，就是我们想到了路径的表示，它是have，字符串存储的时候呢，每一个字符串我们存储是按照字节来存的，从来没有说我们一个操作可以存半个字节，对吧？所以说那我们的ha字符去表示去存储的时候还是要占用整个字节。

整个一个这就相当于浪费了一倍的存储空间，对吧。那这个东西可以去改进吗？以太坊的实现，他就提出了另另外一种方式来改良这个东西，说我们要采用一种紧凑编码的方式，它叫compac coding，怎么去紧凑编码呢？这个非常简单，其实说起来就非常简单，我你不是一个半字节吗？一个ne吗？我把两个ni合在一起，不就是一个字节嘛，所以它就做一个编码，做一个转码，把两个字节合成一个，合成一个BA，这样就压缩了存储空间，对吧？但是大家这个可能就会想到，呃，这是不是会有问题？

大家如果没想到的话，可以直接看下面这里写出来的，对吧？这里带来的一个问题是尼去合成一个，两个尼合成一个字节的话。你得保证它是偶数啊，你得保证它两两都能拼成一个字节啊，那如果要是说我刚好这里表示出来的路径字符串，它是一个奇数呢，假如是奇数，这这怎么办？那大家可以想到我们存储的时候，即使你大家可以想到，那那我你是要是基数的话，我就前面补零嘛，对吧，我我一个尼前面直接0000，然后后面跟上它的值，这不就完了吗？但大家可以想到，那我们存储的时候，大家是不是发现你不管怎么存，就是一和零一是不是都应该存成00000001，对吧，对于我们两个ne来讲。

那这个时候我其实就没办法区分，我是本来是一个奇数的字符串是一个一，还是偶数的字符串是两个字，两个尼零一，我就区分不了了。所以这个还是有问题的，对吧？所以在这种情况下就必须得去处理，分成基有两种情况去处理，所以大家可以看到，就是以太坊你要引进一个新的带点好处来的东西的时候，那你就得去处理它带来的问题了，就得做一些别的工作了，所以呢，为了区分路径长度的奇偶性，所以在encoed pass里边它又加了一个标志位。啊，这个我们就先先放在这儿，然后include pass里边呢，除了这个奇偶性的标志位之外，还有标志位，它标志什么呢？标志前面我们提到的它到底是扩展节点还是yes节点，因为大家看到扩展节点和yes节点它的内容形式都是一个include pass后面跟一个东西，对吧？扩展节点跟的是key yes节点跟的是value。

那我访问的时候，我怎么知道它那个到底是一个一个哈希还是一个真正的value呢？所以这个东西就在encoding pass里边，前面也也是在前缀里面要有一个标识位，表示它后面到底是一个就是这个节点到底是一个扩展节点还是一个yes节点，好，那我们看一下它的标准吧，我们在这里边就给了大家这个压缩编码的规则啊，标准怎么样去压缩呢？它要求在压缩好的这个coed的pass里边，首先我们前面那个6S，呃，6646F67项do的那个pass，我们首先把它转成16进字字符之后，然后把它两两的去合并成字节，对吧？首先我们是先做这个操作，然后呢，大家就会想到我们如果要是它是奇数的话，我们还得去把它凑凑整，对吧？

啊，大家可以看到，这是最下面写出来的这一条规则，如果路径是奇数，就跟前缀加一个前缀凑成整自己。所以说它前面是要加一个前缀的，那这个前缀是什么东西呢？大家看前缀是这样一个东西，就在这个表里面定义的前缀是一个nibo，那就是四位对吧，Ni是半字节嘛，所以它只加四位作为前缀，那么这样的ni它它现在只相当于用了其中的两位。这两位包含着四个状态，所以说它代表着四个汉字字符，就是零，一、二、三，就是00000001 0010和00114种情况，那么它的最后一位这个零还是一，代表的就是。

路径长度的奇偶性对吧？如果是零，路径就是偶数，如果是一，那么路径就是奇数，是通过最后的这一位来表示的，倒数第二位表示的是节点类型，如果是扩展节点是零，叶子节点就是一，所以大家会看到0000指的是这是一个扩展节点，而且它的给定的路径长度是偶数，如果0001的话，就是它的径长度是奇数。那0010就是这是一个叶子节点，然后路径是偶数，0011是叶子节点，路径是奇数，所以加这么一个尼去作为前缀，大家就会想到，呃，这个路径如果是奇数的话，那前面再补上这个，哎，刚好它就两两都凑成字节了，整字节了，对吧？这个就没问题，那那就又有一个问题，那你如果是偶数呢？

啊，那偶数就把前缀后边补上0000凑成整自己，所以大家会发现，如果它的这一个前面前缀是这个0000或者0010的话。那么大家可以想象得到这个最后存储的这一个字符呢，肯定就是后面00000000，或者是00100000对吧？因为如果是偶数，它后边得补0000构成整字节，所以这是这样的一个规则，这就是主要就是为了处理这个数据半字节的这个问题，要节约空间，所以我们前面就得还得加前缀去标识位啊，这就是带来的问题嘛，另外还有一个啊，就是MPT里边还有一个可选的结束标记，就是经常在代码里面，或者是在一些别的这个文章里面会用T来表示terminal，那它的值呢，就是0X10，也就是16进制的，也就十进制的16对吧，这就是幺零嘛，1000，呃呃，00000010000对吧，就是16这个数，那它有什么作用呢？就是。

表示结束，它只能在路径的末尾出现，而且只能出现一次，它代表的就是说这个节点是一个最终节点，它之后不会再有分叉，不会再有别的节点了，所以它也就是说代表叶子节点了，但是这个是一个可选项，就是大家可以知道，就是前面，因为咱们在这个标记位里面是有这个东西的嘛，呃，就是，所以这个是一个可选项，但事实上之后如果我们大家去看代码的话，就会发现，其实代码里面一开始就是判定这个，然后来写这个二进制位的，因为在编码的时候，一开始并不知道它是否结束嘛，如果你不知道的话，你怎么去确定这是一个yes子节点还是一个扩展节点呢？所以它是根据这个标志位去去简单处理的，快捷处理的好，那么接下来我们看一个例子啊，好，这里这个例子大家看的其实就比较明确了，首先这里给了好几个例子啊，第一个例子就是我们的路径是12345。

假如说就是这是我们的16进制字符，对吧，假如我们的16进制字符就是12345，那我们编码出来之后会是一个什么样子呢。大家可以想象一下，然后它后边的这个省略号表示的是后边没有那个就是结束位啊，表示的是后面不知道结束了没有，它，它就是这么一串12345路径。那这个节点里边真正存储它的路径的时候，应该这个enco pass写什么呢？那我们分析一下，它的路径是12345。

这是他想要去存的这个路径，对吧，就是这已经是没有分值的路径了，我要存在这里面，这是不带结数位的，而且是一个奇数的路径，那大家可以想到你既然不带结数位的话，那我是不是应该默认你是一个扩展节点呀，不是叶子节点对吧？所以大家就会想到另外它还是基路径，大家看一下前前面的定义扩展节点，然后还是积。长度的路径是不是二进制位应该是一啊，前面给的前缀应该是一对吧，然然后呢，大家就会想到他在去做这个压缩编码的时候，后边的每一个尼就直接跟上了，对吧？基于自己嘛，这个前缀直接就跟在跟在跟在后边，把我们的这个E直接跟在后边就可以了，所以。前缀一后边直接跟一，这就是我们一，一就是我们的第一个字节，所以这就是我们这个字节的16进制，表示我们存的就是一一这个字符，也就是00010001对吧，这是第一个字节，那后边的第二个字节很简单了，两两合并全存在一个字节里面就可以了，对吧？所以第二个字节就是0010001123对不对？第三个字节四五，那就是01000101第三个字节，所以合并起来之后，整个这个扩展节点，它的扣的pass，这里就三个字节就把它存起来了，那就不像我们之前你这个还得存五个字节对不对，12345对吧？所以这就节省了空间，好，那接下来我们再再做一个练习，就是看一下这个012345，那跟刚才的区别其实就是多了一个零。

那就是奇数变偶数了，对吧，那奇数变同样还是不带奇数倍，这是一个扩展节点，扩展节点偶数长度的路径，那看一下它的这个前缀应该给什么，0000对吧。

那它是偶数的路径，有了这个前缀之后还得把它补足对吧，因为偶数人家本来就能配对的嘛，那后面是不是还得再补四个零啊，所以这个它前面就相当于是补了一个前缀是后边又补足了0000，所以第一个字节是零零，也就是00000000。看起来好像没什么用，全补的是零，但是事实上它是有意义的，对吧？后面就比较简单了，两两个字节合在一起，零幺第二个字节，二，三第二个字节，四五第二个字节，所以最后是用四个字节存储了六个字符的路径。呃，那接下来我们再看一个，如果要是带结束位呢，大家看啊，它本身给我们传进来这个路径是什么呢？是0F10F1CB81010，其实就是传了一个啊，就是传了一个16对吧，就是00010000传了一个这个进来，所以这个就代表结束了，因为在我们的这个字符集里边没有这么大的数，我们就是零到F嘛，F上一个再加一才是幺零对吧，所以它就代表结束，那这是一个叶子节点，叶子节点然后大家看它的路径是奇数还是偶数，对，大家注意啊，数路径的时候不包括最后的结束位，对，只看它这个标准的这个数位，因为我们在编码它的这个路径的时候，结束位是不是根本不需要。

对吧，我能把它查出来就行了，你还要结束位干什么呀，所以我我们关于这个它是不是叶子节点，我我们在前面都都已经编码写进去了嘛，所以就不需要结数位的，所以它的长度也是不包含结数位的，所以前面它是六个路径长度，所以这是一个带结束位的偶数路径，Yes，节点偶数前面是00102对吧，同样偶数路径是不是后面得补零，所以我们第一个字节就是二零，所以这个二是指的我们的前缀零是补足的。

后边这个零才是我们真正的数据，对不对，真正我们的路径是从这里开始的，所以后面两两合并在一起，01CB8。好，那前面三个都已经讲了，第四个大家能应该自己能看懂了，对吧，那第四个这是一个带结数位的奇数的路径，所以叶子节点奇路径，那所以它是0011了，对吧，前缀就是三。然后它是奇数路径所，所以三后面直接跟我们的路径对吧？所以第一个就是这里的F后面直接跟3f fe cb吧，所以大家可以看这里，如果带上结束位的话，这里有六个字符，我们这里三个字符就搞定了一半，所以大家可以想象得，如果这个长度特别特别大的话，它基本上就是一半对吧，一半加一这样的一个状态，所以大家可以看到这就是以太坊里边对它做空间上的一个优化，另外一个优化的点。