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

啊，接下来我们再往再往后讲。这个里边我们就说技数数的问题，我们就先把刚才那个数据当成一个技数数了，因为在以太坊的官方文档里面，他是这么说的，因为我这部分是直接翻译的，就是以太坊这个就是get up上VP里边的内容，那么他对这个上面这个结构，他就认为这是技数数的一个实现，所以我们就认为那个是奇数数吧，呃，当然这个就是我们等一会儿再说啊，就是这些定义上的一些混乱，等一会儿再说，我们就是说刚才这个存储结构到底它有什么问题呢？这样一个存储的，这样一个存储，大家首先就发现了。你每一层节点是不是都得有这么16个节点去做分叉，对吧，你要去这个存一个东西的话，你得完整的把这16个都摆出来，然后你这个字典字典去去访问这个便利路径的时候，一层一层，每一层都要把这16个铺开啊，这太耗这个存储了，那大家可以看到这里边提到的第二个访问效率，其实主要说的就是这个事情。

那他举的例子是什么呢？如果我们想刚才我们存的是一个do，那就是一个646F67，就是一个六个字节，大家可以认为对吧，那我们要存一个32个字节，那三二呢。它的访问长度大家可以想到BI32，如果转成hex字符的话，是不是应该有64个？呃，因为它是32 32个字节嘛，然后我们一个字节就是两个汉字符对不对，因为hi字符是四位有效的这个二进制位，所以它它的仿问长度就得是64。那这个东西我们仿每每一层级的节点呢，我们又又得有这个16个存储，对吧，想象一下这个整个我们只要存一个这个三二，就得浪费多少空间。那访问长度是64，这是二的六次方，对吧？那每一层访问都得需要16个字节，这是二的四次方。

那二的四次方，每一层二的四次方，然后有二的六次方乘，乘起来。24。1K对吧，所以我们只存一个BASE32，然后用这个最基础的字典数，结果就就直接存出1K的数据来，这个简直就是太夸张了，所以说这个肯定是不能忍的啊，而且这个还没有说你这光是存储，你要去查找呢，要去删除呢，每一次都得从上到下。把它的这个路径全遍历完对吧，所以在这个60SP32里边，你的这个64次访问一次都不能少，所以在这个过程当中是非常的低效的。啊，当然大家可以想到就是这其实说的是经典的字典数对吧？那对于奇数数而言，我们前面所介绍的奇数数而言，其实是解决了这个问题的，因为它会把这些不必要的存储路径会合并，对吧？啊，但是我们这里没有给出奇数数的实现。

等一下我们一起合在这个以太坊实现里边，我们一起来说怎么样去实现这个压缩合并的这个过程，呃，那这里其实还。呃，还有另外一个问题，大家就是看到啊，他说到一个数据校验的问题，我们看奇数数，它的节点之间连接方式是指针，我们前面说了，这里一个插槽里边存着的是下一个节点的指针，对吧，指向下一个节点的指针。那对于我们一般的实现来讲，大家怎么实现这个指针？那其实就是内存里面的地址了，或者我们这里如果不是内存是这个数据库的话，那你存一个数据库里面的地址对吧，那正常来讲的话，肯定就是这样一种一种做法了。呃，但是这里边啊，就是C语言里面包括很多大家在这个，呃，我不知道go里面大家写的一些程序里面会不会这么去做啊，就是如果要去实现一个存储一个指针的话，肯定就是直接指向它的地址了，对吧，但是这种直接存储地址的方式，在区块链系统里面可能就会有一点问题。

啊，因为威神就想到了那比特币里边，它是可以对我们存储的这个内容去做校验的，因为存储的哈希他用梅克尔数的方式，对吧，存储出来之后会发现它其实是不可篡改的，你改一个就会牵扯到牵一发而动全身，但是我们这里你如果要去只存一个地址的话。我对应的地址里边的内容改了，那那这个东西完全没影响啊，对吧，你只是你存了一个地址而已，那个地址里边我随便去改，甚至有可能我程序跑飞了，内存泄露，把你那个地方改了，你就完全不知道，就像我们之前是这个，呃，打那个猜数字，猜数字的这个这个陷阱合约一样，那你直接把这个内存改了，状态变量改了，没人知道的啊。

你如果认为这个东西不做校验都可以的话，那我们这个区块链它的不可篡改的特性，你就是对于比特币它很好的实现了，那以太坊上你怎么能保证它这个不可篡改呢？所以这里就想到我们还得加入在奇数数的基础上，你不光能够查到这个值，还应该能够校验这个值。那大家这个就可以想到了，那这个校验怎么样去校验的，那肯定就是比特币已经有很现成的解决方案了，对吧？我们肯定就是引入梅克尔树了，呃，这就是最经典的相当于解决数据校验问题的一种方式，比特币其实已经做了一个很好的例子，呃，那它的这个方式呢，大家都很熟悉了，就是说用每个节点的哈希值来建立一个对应的关系，对吧？底层的数据节点他们每一个都算一个哈希。

然后他们的两两这是一个二叉数，所以两两的哈希之间再去算一个哈希，所以再往上层的话，两两再去算一个哈希，那整个的这个top哈希，我们可以存在这个区块里边作为一个根，对吧，存在区块里边，那我们去校验的时候呢，你随便去改下面的一个数字就会我随便的，呃，按照这个规则，两两一哈希，最后算你肯定上面这个。跟哈希是不一样的，所以说我肯定就能知道你这个交易是有问题的，所以这是呃，大家很熟悉的，在这个比特币的系统里面实现了的维克尔数，大家可能自己都呃，就是手动去敲过对吧，维克尔数的数据结构大大写过没有。简单的啊，简简单的写过是吧，啊对，所以这个东西大家应该是比较已经比较熟了，那我们这里边给大家想要去说的一点是，这个本身是能保证我们实现这个数据校验，防止篡改，那对于我们在以太坊里边怎么样去用这个梅克尔树呢？就是他拿什么东西去做哈希呢。

啊，那我们之前跟大家说过啊，就是他要去做哈希的是整个要存储内容的一个RLP的编码，所以它相当于是把自己的那个value。去做了一个RLP编码，然后再去求哈希。然后把最后得到的那个哈希的值作为存储自己这个值的。地理位置。就相当于我们真正在以太坊这个数据库里面去存的时候，也就是按照他的那个哈希去把它存存储的。那么这样我们在上面的节点里边就可以拿这个哈希作为他的K对吧，所以我们访问的时候就可以直接访问这个地址，就找到这个对应的这个，呃，我们的这个元素，所以是这样的一个对应关系啊。

呃，大家可以简单的先先了解一下，那接下来我们再跟大家说，这是梅卡尔树这一部分，那接下来再跟大家说帕比下树。那前面我们说奇数数有两个基本的问题，一个是数据校验，这个我们用维卡尔数据解决，另外一个是它的访问效率，那访访问效率效率这个问题怎么去解决呢？首先大家可以想到我们前面这个，呃，以太坊的官网，它把这个这种实现的形式是叫做奇数数的实现，其实我们知道这就是一个经典的字典数对吧？那这个字典数其实它有一种改良，就是我们所说的。就是。呃，奇数数的这种这种模式就是压缩前缀数，我们可以把它压缩起来吗？我们可以把这个你只要是同样的路径，我合并在一起不就可以了吗？所以这也是。

以太坊里边想要去把它做的一个改良，另外以太坊里边就是关于我们这个奇数数本身的这种压缩之后的状态，还有更进一步的改良和优化，所以呢。以太坊里边所用的数据结构，这样的一个改进之后的奇数数是叫做帕以下数。帕特里夏树的这个就是最正规的定义，就是我去查了wiki啊，Wiki上面的一个就是维基百科上面的一个定义，他说帕特比下数是什么呢？他是说如果一个奇数数的奇数practice。是二或者二的整数次幂，也就是说二，四、八、16这些数的话，以这些作为奇数的话，那么就被称为判断加数，所以其实大家可以认为帕特加数就是一种特殊的奇数数，对吧？按照我们前面的定义来判断话，所以呃，有时候呢，大家也可以认为其实所谓的帕特里加数就是奇数数。

所以大家如果去找一些学习资料，看一些文章的话，他有可能直接就说他以下数就是就可能给的给大家的图，就是前面这个图啊。这是有可能的，他有可能就是说判断，以下说是压缩前赘述，呃，不知道大家有没有看过这样的文章，我这里就先给大家，呃，就是提前说一下，就是这个只是定义上的一个混乱，这个不代表说就是跟对我们理解底层数据结构没有影响，大家可以认为就是基于这样一个东西来做的，那以太坊里边的实现呢？以太坊里边不仅仅是。实现了一个这种就是奇数为16的判断加数，前面我们说了它是以汉字符作为字符集的，对吧？所以呢，它的基数肯定是16，如果像刚才那样展开的话，就是16个插槽啊，所以这是一个基数为16帕特里下数，呃，那么。

在以太坊当中呢，它还不仅仅就是一个这样简单的奇数数，或者是帕特下属，他为了去优化这样的数据结构，还加入了一些特殊的一些结构和一些方法，主要就是为了解决效率问题，他就觉得之前所说的这个奇数数，就是我们所说的这种奇数数，还有一些效率问题，还是不够好。有哪些问题呢，比如说。呃，这里边我们就提前跟大家说，先介绍一下啊，比如说大家可以想象我们前面这里在存储的时候，其实已经跟大家说了，就是这个dog对吧。转换之后码它是646F67。那我们如果要在这个空间里面去存储的时候，这其实是六个字符对吧。

是不是六个字符，呃，六个汉字符嘛，所以我们存储的时候就应该是六个字节，对不对？呃，标准的存储都是按字节来存的嘛，但是。那大家就可以动脑筋了，我可以想象到这存储的时候就会发现你一个字节是八个位。那其实我这里面有校位，其实只有四位对不对。你比方说一个六存一个六六应该是。0110对吧，0110，那我一个字节里边存储的时候，其实就是00000110。对呃，那那前面那个如果要是存一个F的话，最多也就是1111对吧，所以说如果要是这样去做的话，大家可以想到我是不是可以把。两个汉字符拼在一起呢，啊，这其实就是以太坊里面做的一个改进。所以我们接下来来看一看，就是以太坊里边基于。

奇数树，然后他要引入梅克尔树，引入帕特里夏树，然后他又要在帕特里夏树的基础上做一些改进和优化，所以他就把这个结构自己又定义出来，他说这是我用的一种数据结构，叫做酶克帕特加数，叫MPT，所以这个数据结构应该就是，呃，一般情况我会认为就是以太防。他专门提出的一种数据就是结合一种结合，这两种数据结构都是现成的，但是他提出了这两种的结合，那大家简单理解的话，所谓的MPT可以理解成就是一个维克尔数加，加上了帕下数。那怎么个加法呢？我们等一下再来说在以太防里面的实现，首先它的K，那我们知道它帕里加数里边对K是用路径去存的，对吧？那么它的K呢？用hes编码每个has字符，大家注意啊，这里就是一个半字节，半字节被叫做nible啊，这个大家不知道见过没见过这个定义啊，啊ni这个就代表一个半字节，所以之后可能大家频繁都会见到nibo这个这个词。

所以大家可以想到遍历一个路径的时候，对一个节点呢，只需要访问它的一个尼。也就是说它的一个汉字字符对吧，它编码之后的一个汉字符，然后大多数的节点节点它是包含17个元素的数组，为什么呢？有16个插槽位置对吧？就是对应这个尼，然后还有一个value存值的地方。呃，所以这是这个就是这样的分支有一个名称，有一个定义叫做分支节点，这也是就是前面大家在这个字点数，或者说这个技术数里面看到的最基本的一种数据结构，一个节点的类型叫分支节点。那另外呢，这就还说分支节点每个元素，它的存储的就是我们前面说的这17个元素，对吧，前面的这16个。

这个插槽它存储的是指向下一级节点的指针，我们前面已经说了。它存的是一个指针，那跟传统的做法不一样。MPT里边存的不是他的地址，存的是哈希。也就是说，指向的下一个节点。我把它的内容直接做一个哈希，然后存到上面负节点的这个插槽里面。所以这个大家其实就可以想到了，这相当于父子之间就又有一个关系了，对吧。如果我要改动下面的子节点的话，它的内容的话，那相当于它的哈希就要变，它的哈希变了的话，那其实负节点的内容也就要变，对吧。所以负节点变了的话，再往一层上一层也要变，那一直会追溯到根节点也要变。所以大家可以看到，这其实就把梅克尔树和帕特比下属结合在一起了。

所以就是利用这种存储哈希的方式去寻址，有了这个特点之后，就能把这两种数据结合结合在一起，大家知道我们在这个做这个扫编程的时候，大家说存储一个状态变量，我们用一个mapping，它的这个散裂是散裂到什么地方呢？我们是散裂到一个非常大的存储空间。所以大家看他也就是因为有了这样一个底层数据支撑，所以他才敢这么干，就是说我去存的时候，我直接就把自己的哈希定义成自己的存储位置。那我的复写点存了我的哈希，一边可以校验我，另外一边还可以直接到这个位置去访问我。所以这样一种特性，所以大家可以这就是因为它的这个存储空间特别大，对吧，所以说哈希出去之后不会碰撞，所以就可以这么干，这样就实现了这个维克尔树的结构，保证了我们数据校验的有效性。