090_尚硅谷_以太坊理论_MPT源码结构

我们主要是给大家讲了MPT，就是所谓的梅克尔帕德比下数，梅克尔盘特比下数这一部分内容，在以太坊里面，它在代码上到底是怎么实现的呢？呃，那么我们其实接下来还还是先看一看源码吧，来看一下源码里边到底是怎么做的这件事情，呃，首先大家看一看我们这个源码目录啊，我们还是过一下这个源码目录，呃，前面第一个这个抗子，大家前面跟大家说了，就是它其实里边点开的话，大家一看就能看到，我们前面看到它里边有k store对吧，有就是HD啊什么的，就是跟钱包相关的一些东西，所以这里的count其实有点像是，呃，就是自己的这个真正的钱包账户这样的一个相关的这些组件和应用，所以说如果说我们在以太坊系统里边，大家定义的说，诶不管。

是人还是合约，呃，大家对应的这个东西统一都是一个账户，一个account，那这种数据结构其实并没有在这个account下，这这account这个目录下面去实现这个基本的数据结构，那基本的数据结构前面我已经跟大家说过了，对吧，都是在这个Co下边，靠下边这个东西还是比较丰富的，就是以太坊最重要的一些东西，包括区块。交易账户状态，所有的东西其实都是在里边定义好的，呃，这是我们可能之后很多代码会在里边找，然后呢，我们大概的看一下build，这个就不用说了，这我们一开始在做源码安装的时候会发现，其实启动的脚本就是里边的脚本，对吧，有一个呃，叫invid sh对吧，有这样的一个脚本，然后如果大家。就是当时做了原码安装的话，会发现它在底下还会生成文件，呃，这个我们就不管了，这只是跟我们做这个安装和构建整个项目的时候用到的一个目录，CMD这个里边主要大家能想到的命令行嘛，对吧，所以它其实就是我们启动gas的时候，整个的那个命令行的体系都是在这个里面去实现的，CMD这个下面咱们去敲各种各样的gas命令，在这个里面，当然对应的就是哦，这里面好像现在没有。

Cons这个控制台的这个文件夹了，呃，有的我没看到，呃，所以大家可以看到就是除了command之外呢，还有一个conso conso这个控制台，那其实就是我们启动gas之后，在这个控制台里边用JS去做交互，它内嵌一个WEB3对象，我们用JS去做交互的这一部分内容，所以大家可以认为就是这个控制台这一部分呢，主要是跟我们在启动之后交互的这一部分组件和相关的功能都是在这个里边，然后common这一部分里边有很多，相当于就是我们公共的一些，呃，一些类库，对吧？大家基础的一些类库在里边，可以随便点开一下，大家看看里面大概是什么，这个确实太慢了啊啊，大家可以看到里面就有很多U类，比如说这个hax u。

还有们math这个数学的这些工具类，所以在里面都有具体的定义，呃，包括这个BI啊，Big啊，这些基本的数据类型和这些工具类的定义，那接下来还有一个cons cons，呃，这个应该读什么？Consensus就是我们所说的共识，那这一部分是很重要的，也就是说我们所关心的很多东西，比如说我们，呃，就是在整个这个挖矿树块的过程当中，交易怎么样去确认。

呃，怎么样去确认一个合法的区块，然后我们之前跟大家讲的就是还有书块奖励对吧，还有各种各样的这种奖励机制，这是怎么样去定义的，其实都是在这一部分里面去涉及到的啊，所以我们如果要看的话，主要就是consensus和call这两个目录，我推荐大家下去之后可以去好好看一看里边的内容。呃，那至于别的我们也都说一句吧，简单doer这个一一看这个名字这就知道了，这是相当于整个容器启动对吧，Docker启动的这样一个一个工具包对应的一些组件，Contracts这个下面是有一些就是相关的一些合约，因为我看到他其实不是底层的一些东西，可能是有人去做的一些别的周围的一些应用开发，呃，靠，这个就是我们最核心的一个一个组件了，接下来这个P，这个就是涉及到我们加密算法的一些东西。

包括我们的哈希算法，还有我们椭圆曲线都在里面有大家看到了对吧，这个一进来就能看得到，除了这些之外，大家还可以看到，就还有dashboard dashboard这个主要就是一些，呃呃，对，就是大家能想到dashboard叫什么叫。呃。应应该叫什么叫叫表盘还是叫叫什么对吧？对仪表盘对，所以它其实是做一些那个监控，环境监控和这种呃，测试用的啊，然后下面这个ETH这个呢，其实也是比较关键的一个组件，不过它主要是在协议层去实现以太坊协议的一部分内容，所以我们可能涉及的比较少，大家如果要关心这个整个以太坊协议盖这个客户端怎么样基于他去去搭建，怎么样基于它去实现，大家可以看这个就是pth这个目录下面的内容，它就包括我们互相之间消息调用，怎么样去通信，这些东西都是定义好呃，那下面就是还有这个客户端了，对吧，ETH client，这就是具体的客户端的实现，ETHDB这个是，呃，相当于是我们底层的数据库，就整个以太坊底层数据库的一个，呃公整个的这一个包下面还有这个sta e。

那就是跟统计信息相关的一些东西，对吧，跟收集统计信息相关，Even这是事件相关的一个包，一个包，我们如果用到的话，可以到里面去查啊，平常可能就没什么东西，呃，Internal这个我好像也没有关注过，Internal是什么？啊，这个看起来不是什么东西，对吧？EAPI就看起来就是可能内部做一些测试可能用的东西，所以应该我们大家也用不到，呃，然后下面的这些东西其实都比较少用了，这个light这个是跟我们的新客户端相关的一些东西啊，然后log这个是日志机构，大家知道那个我们的事件和日志其实就是紧密结合的，所以它它是分了两个目录日志相关的，放在这个里边，呃，下面比较重要的，其实。

主要这个matter呢，大家知道这是挖矿相关，对吧，矿工相关的东西，Note是节点相关，那p two p，这就是网络，我们的网络组件了，PP网络组件，然后这里要说一个就是这个parents，这是参数，大家会发现我们所有这个以太坊。启动的时候定义的初始的配置和参数都在这个里面定义，我们可以看一下这个。这确实是比较慢，非常慢。大家其实如果自己能打开的话，应该也能看到，就是大家对如果对源码感兴趣，对底层开发感兴趣，大家经常就可以呃上去就就翻一翻对吧，这个源码目录结构也比较清晰，大家可以看到在这个conflict下面，大家看到没有，这里它定义的什么东西。

Mid chain conig，也就是主网的配置，对吧？Chain ID big new in one，也就是这是一个big int，对吧？然后new了一个int，一，所以TID是一，哦，这就是主网的ID，它下面还有别的home sad block定义了一个数字。然后下面它还有什么这个door fork block，所以大家知道这是在说什么吗？EP150BLOCK，这在说什么吗？拜占庭block，君士坦丁堡block。啊，大家可以看到这其实后面指定的是当时分叉的区块高度对吧？呃，就是从这个时候开始是应用我们这个，呃，就是它到底是应用这个homestead的协议，还是应用这个半阵庭的协议，所以大家可以注意看，它都是在我们的配置文件里面把它指定的，因为如果我们整个的历史数据都是在一起的，你即使是这个版本换了，那大家如果要是说你没有一个地方告诉大家的话，我都不知道啊，那我校验历史数据的时候，我现在版本跟之前不一样，有可能就会觉得它是错的，对吧？它它就不能成立了，所以说这里一定要定义好从哪个块开始，你用新的东西去校验啊，所以都在这里边有啊。

大家，而且大家可以看到，就是拜占庭的这个block是从400多万块，437万块开始的，而君士坦丁堡的block还是一个还是一个空，对吧，因为还没有真正的上线。好，这是这个。

就是基础的这些配置，而且在这个里边大家都可以看到我们测试网络的配置。Test ne chin con，大家看这个ch ID是三，这就是我们的rob test network，大家还记得一开始跟大家说的这个他们的ID是多少吗？呃，这个测试网络ID就是三，那下面还有一个ID是四的，这大家记得是什么吗？R by con对吧，在这里边这个配置文件里面所有的都有啊好，那大家感兴趣的话，下来再详细看，这个都是一些基本的配置，我们就不详细说了，这里还有一个这个bootnos，这个可以给大家再也简单的说一下，这个bootnos是什么东西呢？大家知道以太坊的网络，大家如果要是说一开始。去。去启动一个全节点，那大家去找哪些？

周，那大家一开始启动全节点的时候，自己本地是什么数据都没有的，对吧？所以一上来之后肯定要去请求周围的节点去给自己发数据，那大家是不是就会觉得，那我是不是一开始应该先找比较可信的节点去对去做一些这些基本信息重要。重要信息的这些确认，要不然的话，我周围有一个有一个非常非常的一个节点，他直接把所有的区块头全篡改了，然后他把自己的那些东西全放进来，那我们根本不知道，我们一上来就从他那里同步，咱们还以为诶他那里是正确的，所以这个肯定是不行的。所以大家可以看到在以太坊启动的时候，在自己的配置文件里面预设就配置了一些启动节点，这也就是相当于官方配置了一些节点，大家初始的时候，而且大家知道就是一开始我在做，呃，启动一个全节点连自己的这个p two p网络的时候，一开始你怎么样去发现周围的节点呢？其实一开始你可能并没有办法很快速的连接到周围的节点上，对吧？所以你必须要有一个启动的连接方式，那连接谁呢？就连接这里他已经写写好的这些节点啊，所以是有一个默认配置的，大家说一句。

好，那刚才我们说的是说到哪了。说到node，呃，说到parents对吧，然后下面这个RLP，那大家就知道了，这是我们所说的RLP这个编码方式，他在这里专门用一个目录，就是来处理这个整套的编码方式，呃，大家要是感兴趣可以去看，但是我觉得可能没太大必要。然后RPC，那大家知道，这就是我们的这个RPC调用了，对吧？GCRPC整个的这个协协议和整个这种调用方式都在这里有实现。呃，下面像这个SW，这是整个以太坊，基于以太坊的一个，就是分布式存储的一套一套机制，大家可以认为它跟以太坊的这个，呃，就是本身的协议，可以认为它是并行的一个东西，它是基于以太以太坊协议上，呃，大家可可以认为它是一个应用层的东西，但是它又相对来讲比较底层，它不是就是大家所认为的像DF这样的应用比。

比较底层的一个东西，一个服务，呃，同样就还有一个很有名的服务，叫下面这个whisper也跟大家说过，对吧，这是一个消息机制的一个服务，大家可以它是低语嘛，私语对吧，所以这两个是以太坊上面最重要的两个，呃，以太坊生态上的两个基础服务。然后还有一个需要跟大家说，这个就是跟我们今天上午刚刚讲过的内容很相关的，大家看到这个这个目录吗。

这里存储的就是我们今天就这里放着的代码，它主要是用来干什么的，就是实现我们今天上午给大家讲的MPT，好，那么我们今天上午刚讲的，所以我们就点进去看看。Tree这个里边，那大家就看到了database有node对吧，然后有这个coding，然后有hassher，有呃，ER，然后还有这个同步啊什么的这个，当然还有tree整个的这个定义，我们可以看一下这个节点定啊，Noe就是节点。好，大家看这里no的是interface对吧，大家看它的type。诶，他这里定义了type，然后里边好几种数据结构对吧，上面一种叫做。Fullno。全节点，诶这个全节点是我们起以太坊时候那全节点吗？对，那肯定不是，它是竖结构里边的全节点，那大家看看这个所谓的全节点是什么，是我们说的什么东西，它里面有什么东西呢？有children。

17NO，所以它是一个node类型的数组，对吧。有17个。那这是一个什么东西啊，16加一，所以它是我们的分支节点对吧，就是我们所说的分支节点，在它这个里边，它认为哦，你这个就是相当于我们原始的字典数里边很完整的那个节点，所以这就是全节点，他要管这个叫full notde，然后下面还有一个short note，大家看一下这个short note是什么东西啊，当然这个就是它除了我们讲的那些，它还多了一个flag，对吧，会有一个标志位，这个我们不管，我们看这个商note，它主要就是一个K，一个value。

对吧，那大家想这个key这里应该存什么东西，然后下面的这个，呃，我们就不写叫它value吧，对吧，Value里面存的是一个node类型的value，这应该是什么东西。大家这个搞不懂的话，那我们再看下面啊，它又定义了两种类型，都是字节变长，变长字节数组对吧，一个叫passion not，一个叫value not。大家觉得？能能想到这个东西是是在干什么吗？咱们除了咱们讲的节点类型，除了所谓的分支节点，也就是这里的全节点之外，还有两种叫。扩展节点和叶子节点对吧？他们是不是数据结构都有一个共同的特点，就是有两个元素，一个是它们编码之后的路径，Included pass。

还有一个。我们当时是说扩展节点，它是要存一个K，因为它存的是指向下一个节点的指针，对吧，是一个哈希那。叶子节点呢，直接存着的就是值，所以那大家是不是能够想到这样一个short node，是不是就涵盖了我们所说的扩展节点和叶子节点两种情况啊？所以大家可以看到就是这个理论上的东西和这个实际代码里面的实现还是有一些差别的，对吧？呃，这里它的实现其实就是用同样的这个short short note，然后就代表了我们扩展节点和子节点，那么扩展节点跟子节点不同的是什么呢？前面的这个K其实就是自己的那个encoed pass对吧？那后面的这个value它是一个node类型，所以如果我是扩展节点的话，我就可以让这个node变成一个下面的hassh node，对吧？就相当于是我把一个。

他的那个哈希直接存到这个里面来，所以就代表着我指向了另外一个节点。那如果要是说。是叶子节点的话，那我直接就存一个value就好了，对吧。好，这是就是跟我们上午讲过的几种节点类型相关的一段代码啊，呃，当然下面大家就可以看到具体的这些方法，这些函数，呃，可以去这个inco inco的这个RLP调这个方法去做RP编码，对吧？然后下面这个就定详细的定义了，这个no flag到底是个什么东西，它包括一个哈希，然后还包括它的这个generation的counter，就是在cash里边创建出来的这个一个计数器。

最后还有一个dirty是一个就是标志位，呃，在这个文件里边，大家可以看到下边其实是有这个关于节点操作的所有方法的，包括这个怎么样去编码一个节点，对吧？那有编码肯定就有解码了，Decode for，然后decode re，所以这些东西大家都可以下来之后再详细的去看一看，呃，那我们看这一段源码的话，我们重点看一下这个吧，就是还能加深一下大家上午的那部分印象啊，Encoding，我看一下encoding，他说的应该是什么呢？就说的是我们今天上午给大家介绍的这个。压缩编码的机制，大家看一下它是怎么样去做压缩来，首先大家看这里直接上来一个函数，叫做has to compact。大家根据这个名字能猜出来它是干什么，我们在做这个压缩的时候，除了定义了这么多节点能把它的路径压起来之外，然后还进一步做的那个压缩空间的做法，优化的做法，我们是要干什么来着？

还记得吗？我们当时是因为本身16进制的字符它应该只占四位对吧，但是我们存的时候要占八位一个字节，所以我们是想把它四个字节的这样一个ni全合在一起，变成一个紧凑型的一个字节，对吧？所以这就是我们这里所说的compact compact应该就是就是压缩这个各种各样打包这样的一个意思，对吧？所以hes compact其实就是说把原先的16进制的字符压缩成两个16进字的字，字符合在一起，拼在一起，拼成一个字节这样的一个存储方式，对吧？好，我们看一下这个代码怎么写的啊，首先定义了一个terminator，对吧。

特是什么？Terminator是。终止符对吧？终止符我们当时说过，有可能里边可以定义这个终止符，它就代表它是不是终结了，是不是最终节点，也就是说它是不是yes节点，好那么我们看它这里边要求的是传进来的参数是一个ha的。字节数组对吧，变长字节数组，我们看到。然后要返回的也是一个字节数组，所以就是进来一个pass，除去一个压缩在一起的。字节数组那一上来之后，他就先定义了terminator。

Terminator是什么呢？它要求的是这个FAT0。这个BA0应该是什么东西？就是一开始先给定义一个初值是零，对吧，BAT是我们的基本数据类型嘛，后面就相当于是给定一个值，所以这是一开始先给terminator给他零，然后我们看他说如果。Has has her。Has。掉了这个方法，如果has term的话，Terminator就制一，大家能想到这个has term应该是个什么方法，我们查一下，对大家肯定能想到它其实就是在看，大家看它是怎么检查的呢。直接return，它是个布尔形的对吧，直接return，呃，首先它的长度要大于零，而且。什么样的情况下就has term呢？什么样情况下有这个terminator呢？

就是在长度大于零且它的末尾元素。是16对吧，我们定义的16是放在最后的话，就代表这是一个终止，这是一个终止符，所以这里它has特。去这样定义，那么我们就看就在这啊，如果说它最后是一个16的话，那么我们就把这个terminator制成一，标志位置成一，然后he等于he后面这样。冒号，这相当于是数组的那个surprise方法，对吧？大学够的时候应该学过对吧，这是表示什么意思，这个。取这这这个截取是吧，截截哪一部分导，对其实就是把最后那个字节终止符砍掉对吧？对，其实就是这个，所以大家看这个其实代码还是很简单的啊，咱们知道它的算法之后，就一看就明白他是要做什么事情，好那么我们现在其实就是已经把终止符砍掉了，然后又它到底是不是终止我们也已经知道了，有了一个标志位，好接下来看，然后有一个buff定义成。

啊，这是这个创建了一一个这个字节数组，对吧，然后大家看它的这个。Les是多少？它是的，Length除以二再加一。十，17为为，为什么是17呢？大家觉得这个ha是16是吧？这个has是前两我们定义的变量对吧？传进来的参数就是整个我们传进来的这个字节数组，它的名名字叫hex，所以它其实是说我们当前整个传进来的这个has。

那其实这是我们已经要压缩好的这个路径，对吧，这个路径它的长度，它本身现在的这个长度先除以二。一半对，其实我们只就觉得压缩之后是不是只需要一半了，但是我们还有一个前缀，对，所以后面还要再加一，诶那大家想一想这个，那那它的这个lengths如果是奇数的话，这么算对吗？之前我们就想过对吧，你你这个奇偶性是有影响的，所以大家想一下，如果是偶数的话，肯定没毛病，偶数的话就是除，呃，除以二变成一半之后，加上前面一个前缀，它还要补零的嘛，对吧，那这个肯定没问题，如果是奇数的话，大家想除以二的话。是不是应该相当于它减了一之后除以二的那个值。

那减的那个一是不是直接就放到前缀里边，跟前缀拼起来了，所以我们后面再加上一是不是还是一样的长度，对，所以这就是我们最后buff，就是我们最后转换成的这个字节数组的长度，所以我们一开始先给它分配好啊，这个go本来是这个就是静态类型语言，而且对这个内存的操作跟C很像对吧？一开始先分配内存好，那么我们定义好它的长度了，接下来就给了buff，零等于terminator，这个是什么？后面这是什么意思？位移对吧？移五位，左左位移，移五位，这什么意思？对，大家还记得，呃，Terminator，它是代表。是否是终止，也就是说它如果是零的时候就没有终止，那我们这个压缩的路径相当于它是一个扩展节点的路径，对吧？如果他要是唯一的话，说明终止了，那就是一个叶子节点，那个标志位是在第几位来着？

还记得吗？前缀里面的第几位忘记了，对倒数第二位，最后一位是奇偶对吧？倒数第二位是判断是叶子节点还是扩展节点，所以那么这里面它倒数第二位为什么他直接以五个呢。因为我们的前缀最后是不是应该放在第一个字节的前四位，后面要不补零，要不把我们第一个奇数的那个尼补上来，对吧？对，所以我们这里的这个标志位，它之后一定是在第六位的，对不对，从低往高数是第六位，所以我们现在是不是就应该。

把这个terminator它是一的话，现在在第一位是不是左移五位就移到了第六位，对，所以是这样一个过程啊，大家想一下这个位移操作，因为我们要涉及到字节里边的这种这种操作去拼一个字节，所以肯定是要做这种位移的位操作的好，那么它定义出来之后，这我们这个标志位就有了，然后接下来再看。如果LSX，也就是它的长度，这个是与一对吧，然后等于一，这是在干什么的？对，判断基有这个语，不是我们逻辑上的语，这个是按位语对吧？所以大家想一个字符或者是一个数，一个二进制数跟一。去安慰语的时候，这代表什么意思？

一对是不是，就是看它最后一位到底是不是一对吧，如果是一的话，它跟它跟这个呃，一暗位语之后，那就应该是一对吧。那如果他要是零的话，那安位语之后就全是零了，因为一前面都是00000001对吧，所以这个安位语最后前面都是零，这个没话说，就看最后一位，所以这其实就是判断奇，那如果它等于一的话，那说明这个L本身最后一位也是一，那这是奇还是偶啊，这应该是对，这是奇数，好，我们看奇数下面怎么操作。啊，大家就看到了它的BUFF0，大家看啊，这是或等于这这是货对吧，按位或嗯或按位或等于一在向左位移似哇，这个好复杂呀，这什么东西。

其实这个操作是想干什么，就是既然你是基数，我要把前面那个标志位得得制成基数的标志位是制成一对吧，其实就是这个意思。那它的操作是什么呢？首先一向左位移四位，是不是到了第五位了，就是我们所说的前四位那个前缀的最后一位，对吧，那就到了这个位置了，那到了这个位置之后。怎么操作呢？啊，它是我原先的BUFF0里边是什么。我先跟他做一个货为货。所以如果要是跟一直接去做备货的话，那肯定就是一了，对吧？啊，但是前面的值还保留不变。因为你不能直接把一给他，因为我们前面它前面一为还有有可能已经变了对吧，已经有可能是叶子节点前面已经制了一了，它本来是有可能是0010，你现在如果把一直接给他的话，他变成0001，这肯定不对，我们标志位就错了，所以他是要按位做一个未货，所以如果前面0010的话，跟一做一个位货就变成0011，对吧，两位就都变成一了，所以说这样一个过程，然后未获的结果再给到他，那就是它，它这个未获等于就相当于是把这个BUFF0跟后边的这个表达式在一起霍，霍完了之后再付给BUFF0，对吧，这就相当于要写进去了，这个尽管很短一段代码，但是可能大家看起来还是得对，还是得想想对吧，这个过程还是有点绕，所以就是即使我们上午已经知道它的算法了，但是这边看的时候可能还是会有一点绕。

好，那下边这还有一个操作，X等于X1冒号。

这是又干什么事情了，这是。这是干什么事情了啊，我们我们漏了一步啊，漏了一步BUFF0，又来一个按位或等于X0，这是干啥的？先说X0是什么吧。Has。嗯，HA0是我们的第一个路径，压缩路径上的第一个汉字符，对吧。所以现在他是不是要把我们的第一个字符要放到我们。压缩之后的那个那个buff里边去了，对吧，那它怎么放呢？我们现在buff里边是不是只有一个元素，就是带标志位的那个元素对吧？前面我们已经把那个判定是叶子节点还是扩展节点标志位置置上去了，然后上面的第一步这个一位移四位，又把我们的奇偶位的这个标志位也置上去了。

那现在前四位已经好了，前缀已经好了，但是他后面四位还没东西对吧，所以我们是不是把我们的对第一个直接给到这个后四位拼上就行了呢？是不是对基数嘛，直接拼在后面就可以，那大看这个它是怎么拼的呢？它就是。对，直接拿这个值跟我们的BUFF0做一个货，按位或。为什么这样就行呢？四位全是零对，因为BUFF0一开始我们没赋值的时候，肯定它后面都是零对吧？所以是不是跟他疑惑，那后四位就变成我们我们原来这个第一个字符的后四位对吧？那一样，我们原来字符因为它是个汉字符，它的前四位都是零对吧？所以跟我们的这个BUFF0的前四位疑惑之后，我们BUFF0的前四位前缀还保留，诶这个就完美的让让我们把它两个拼在一起了，给大家看一下，这个确实是还是有一点小技巧的，对吧？就这么简单的代码，就把我们这个整个这个逻辑就搞定了。

就看起来非常简单，所以就导致有可能看不懂对吧？呃，那在下面这一行，这是什么意思，X等于X1。好，那这个大家就想到了，对，你既然第一个已经过来了嘛，那我就把has往后移一下吧，第一个你砍掉就行了，我不要了，那接下来我是不是就继续可以用这个。呃，HE0来来拿我里边的元素了，对吧？对，所以就是这样的一个过程，好，那接下来大家就可以看到，呃。好，接下来还得做一个这个decode对吧，得把它再再做一个这个解析has和这个，呃，就是BUFF1后面的内容去做一个抵扣，然后return这个buff，就把我们这个要做的这个压缩，这个过程完成。

所以大家可以看到就是啊，当然这个decode nis大家可以看它是它是一个什么东西啊，对这个de decode nis，它其实是在做一个循环，所以说我们刚才这个其实就是一个循环调用，对吧，就是不停的我去deco的一个把一个移位拿出来放到里边，然后继续把我前面的这个往后移一个位置，为什么要把那个减一了，对吧，第一个要砍掉呢，下一次来去做这个递归调用的时候，我就可以继续用这个方法了，给大家可以看到它这个设计的。就是这就是很漂亮的代码，设计出来非常简洁，就是这么简单的几行，就把这么复杂一个功能就搞定了，呃，当然就是说可能似乎可读性上大家好像有点不太好理解对吧？呃，就是我们得结合着上午给大家讲过的这些理论，大家去去想一下他到底是什么样的一个状况好，呃。

那大家可以看到，就是下面它还有一些方法，比方说这个，呃，Perfect。那就是要去判定这个前缀的一个长度，对吧，这从字面就能看得出来，然后除了这一个，我们做这个has to compact的话，还可以compact to hacks。还可以把它解出来，那解的这个过程可能就大家想到就比较简单了，对吧，我就把它直接这个地位拿出来之后，直接扩展到一个字节就完了，所以这个是比较简单的啊，当然这个就你得区分它是低位还是高位，一个一个解对吧？好，那这个我们就不再详细说了，嗯，好，那我们这里可以再给大家看一下这个tree，这个tree的话，那大家就想到这是整个数的这个结构，对吧，看它里面还有什么东西。

啊，这个确实是很慢啊。大家对这个源码感兴趣嘛，看看很多同学可能有一点不是很感兴趣是吧，呃呃，当然其实我觉得源码的话。呃，能看当然更好，但是不看的话，其实我觉得没什么，为什么呢？因为大家可以看到这个源码去找东西，其实是挺没效率的，对吧，大家你不知道他一开始的这个代码构架是什么样的，而且这已经是迭代了，已经到1.8，大家看到之前是很已经是很多个版本了，就是这这已经是就是正式发布的版本都已经这么多，那之前的commit已经有很，大家看是有多少，诶这里没有显示commit啊，也至少几千个commit了，所以大家看不到它最初的这个样子，可能就不太好理解，现在它为什么写成这个样子，有很多这个结构大家也很难去一下子找到，所以呃，我觉得这就是我们结合黄皮书，结合今天给大家讲的内容，我们讲到什么来看一看，也就是就是具体说我们要把源码一就是一一行不落的全读一遍，我觉得这个确实没必要啊，这个就很花精力，可能也没有什么好的效果。

好，我们看一下这个tree这个结构，呃，它在这个里边呢，它是定义了一些像这个什么empty root empty state这些东西，这些东西我们可以不管啊，大家可以看到这个empty state，这就是把这个空去做了一个，做了一个哈希对吧，但是它这个empty root呢，它是单独的指定了一个一个。呃，相当于指定了一个地址，然后去做哈希的这个我们就不管它了啊，呃，然后接下来我们可以看一看，就是它里边的这些啊，大家看这个结构的定义啊，Tree结构的定义，它定义的是什么呢？就定义了DB，那首先就是我这个tree。

我的底层数据结构是什么对吧？我首先得定义好我自己的底层数据结构，然后还有一个重要的东西就是root，那大家就想到一个tree，它需要什么东西呢？有我的底层数据结构，然后还有我的一个根就完了，这就代表了一棵树。有根就就可以了，对吧，从根出发就可以访问到它所有的节点，呃，当然下面它还定义了一个这个呃，开始转，开始转，那就是整个的这个catch缓存的一个增长的一个一个限制，还有这catch limit对吧，这些东西大家可以可以不管它啊，下面其实大家可以看到在这一个文件里边，这个源码里边。

它实现了我们一个数学，呃数结构里边的正常的所有的方法，比方说新建一个数，这肯定是有的，对吧，大家可以看到下边它有get，那这就是要访问一个一个节点了，对吧。下边有update呃，增删改查，呃，我们已经有了查，那这个是改对吧？Update，那还有增删是不是有呢？Insert，呃，这个就是标准的数据结构的操作，Delete对吧？所有的东西都有，当然具体的这个过程大家感兴趣可以去看一看，比方说像他这个insert，我们怎么样往一个。梅克尔帕特里下树里面去插一个节点。看看它这个到底是怎么定义的，当然这个里面可以看到它还分了不同的情况，肯定不同的情况会不一样，对吧，你是这个就是要插入的这个这个node，你到底是一个short node呢，是一个扩展节点子，呃，Yes，节点呢，还是一个分支节点，一个full node，这个肯定是有差别的啊，当然它还有可能你是一个空。

对吧，你要往空的地方去直接去插一个插一个这个节点，所以这个都是有可能的，呃，还有这个哈哈弄就是有可能你直接往这个一个一个值这个位置去插，对吧，所以大家可以去详细的看一看它这些数据结构的实现。