前言
树形数据结构在区块链开发中有着十分重要的作用，常见的包括Merkle tree、Trie、Patricia Tree、Merkle Patricia Trie等等。其中最为熟知的当属Merkle tree与Merkle Patricia Trie—MPT，其中Merkle tree用于快速计算状态根，MPT则综合了Patricia Tree和MPT的优势，不仅可以快速计算得到状态根，而且可以做到快速的状态数据增改查，但实现起来较为困难，例如以太坊中关于MPT的实现就十分复杂难懂。而JMT（JellyfishMerkle）树则是一种新的兼具MPT树优点，同时实现起来较为简单的一种树形结构，因为其实现的树形结构就像水母一样，所以被称为水母默克尔树。
Trie（字典树）
首先我们介绍一下字典树。字典树是指用于保存关联数组（例如字符串）的这一种树形结构，如下图所示：
顺着某一path遍历即可获取该path对应存储的字符串，对于有相同前缀的字符串在树中共用相同的前缀path。Trie不仅可以减少具有相同前缀字符串的存储占用大小，也用于快速查找某一字符串是否存在。
例如在实现一个简单的一个搜索框时，底层数据结构就可以采用Trie树，如采用上图所示Trie树，当用户输入ad时，那么我们就可以根据字典树的内容给用户advice，adance两个提示词。
Patricia Tree（压缩字典树）
使用Trie时可能会出现一个问题，如下图所示：
对于图中的字符串“abandon”因和其他字符没有共同前缀，导致其一个字符串占用了很长一个path，浪费了存储资源，Patricia Tree就是为解决该问题的。
如下图所示，上图的Trie变成如下结构：
Patricia Tree在字符串没有共同前缀时，让其剩余字符作为一个叶子节点存在，而不是每个字符起一个新的节点。同时中间节点如果有相同的就合并一个节点，如图中所示的 dv 。
JMT树（JellyfishMerkle）
实现原理
JMT树是在Patricia Tree基础上改造实现的一个16叉树，用来存储(kev,value)类型的数据。其中key即是上文提到组成path的字符串，value则存放在对应叶子节点。
在区块链中一般以hash结果作为key，因此key的长度是固定的。对于key长度为256位的JMT，256位key按nibble（半字节 4位）被划分为64组，每组等同于一个16进制的hex（0—F）元素。理解为每一个nibble等同trie中的一个字母。
如下图所示（演示最理想的满树的场景）：
在满树的情况下，每个中间节点都有16个元素（因为一个nibble有16种可能0—F），中间节点中的每个元素又都对应一个拥有16个元素的子节点，如此不断延展向下。因为key长度是256位=64个nibble，也就是说，树的高度最高是64。延着某一个path向下直至叶子节点，就可以获得一个完整的key，对应叶子节点就存储该key对应的value值。
JMT树同样拥有类似于默克尔树那样计算状态root的能力，对于一个中间节点root hash，不断两两归并其叶子节点最终获得一个hash，如下图所示：
（Aptos的实现中对于root hash的计算有一些优化，这里为了理解方便，我们就简单理解中间节点的root hash就是子节点的两两归并。Aptos的root hash的计算见：github代码，感兴趣的可以看下。）
从叶子节点开始不断向上归并，就可以计算得到最终的root hash。也就说计算root hash时，只需要计算最顶部节点的root hash，而计算顶部节点的root hash，需要不断递归向下计算所有子节点的root hash。
除此之外，JMT还做了类Patricia Tree的优化：
- 单叶子节点优化：当构建子树时，如果某个中间节点位置只有一个子节点且该子节点是叶子节点，则不创建中间节点，而是直接将该叶子节点提升到当前位置。
- 多子节点情况：当某个中间节点位置有多个子节点时（即该路径上有多个key共享相同前缀但在此处分叉），必须创建多个Internal Node来管理这些分叉的子节点。
与Patricia Tree不同的是，JMT 中间节点如果有多个重合前缀的也不会合并，而是每个nibble新起一个中间节点。
因为做了类似于Patricia Tree的优化，所以在计算中间节点的root hash时也有以下改变：如果子树只有1个叶子节点，就直接使用该叶子节点的哈希。
举例说明
我们在JMT中按许插入以下3个数据：
A27DC801AB01C812……
A279F201AB01C812……
A26F9801AB01C812……
先插入A27DC801AB01C812…… ：
此时计算整棵树的root hash其实就是计算A27DC801AB01C812……对应的该中间节点的hash，因为其只有一个叶子节点，所有root hash就是A27DC801AB01C812……的hash。
再插入A279F201AB01C812…… ：
如上图所示，两个数据有相同的前缀A27，按照Patricia Tree的处理会将A27作为一个中间节点处理，但JMT这里会将其拆分每一个作为一个中间节点。此时计算整棵树的root hash其实就是计算A对应中间节点的hash，递归向下就是计算中间节点2的root hash，继续向下计算中间节点7的root hash，因为其有两个叶子节点，所以7的root hash就是两个子树hash的归并hash。
再插入A26F9801AB01C812……：
此时计算整棵树的root hash其实就是计算A对应中间节点的hash，递归向下就是计算中间节点2的root hash，继续向下就是计算对应6，7两个子节点的归并hash，而计算6，7两个节点的hash，就是根据其子树的归并hash获得。
总结
以上就是JMT的实现原理，将一个256位的key按nibble（半字节 4位）划分为64组，每组作为构成path的基本元素，每组元素有16种可能0-F，即为一个16叉树。同时结合Patricia Tree的优势，只有在遇到分叉时，才向下扩展子节点，极大的节省了存储空间，而且相对于MPT理解和实现起来也都较为简单。
文章评论