最近接到了一个工作任务,将项目智能合约状态树中的数据结构从红黑树改为字典树,并对比一下两个数据结构的性能,Trie 主要参照的是 Ethereum 官方的 Java 实现 ethereum/ethereumj,而红黑树则是自己实现,本文则是对两个数据结构的理论和实际表现对比的记录。
红黑树是一种近似平衡的二叉查找树,含有红黑结点,能够确保任何一个结点的左右子树高度差小于两倍。
必须满足以下五个性质:
红黑树并不是完美平衡的,但是左子树和右子树的层数是相等的,因此,也成为黑色完美平衡。因为是近似平衡的,所以旋转的频次会降低,维护成本下降,时间复杂度维持在 LogN。
红黑树主要通过三种操作来保持自平衡:
因为红黑树较为复杂,实现代码上传至 GitHub 供学习查看。
Trie 被称为字典树,又称单词查找树或键树,常用于统计和排序大量的字符串,如搜索引擎的文本磁盘统计等。
它能够最大限度减少无谓的字符串比较,查询效率较高。
字典树的高度较低,但占用的存储空间较大,核心思想是空间换时间。
利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的,可以很天然地解决单词联想等业务场景。
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
利用了 Trie 结构的特点
但是 Trie 结构比较浪费存储空间,当键值对分布稀疏时效率较低,而以太坊的账户地址是 40 位十六进制数,地址约为 2^160 种,极其稀疏(防止哈希碰撞)。
因此,需要对 Trie 结构进行路径压缩,也就是 Pactricia Trie,经过压缩后,树的高度明显减少,空间和效率都得到提升。
而以太坊真正采用的是 Modified MPT 结构,其结构如下
每次发布新的区块时,状态树中的新节点的值会发生变化,并不是更改原值,而是新建一些分支,保留原来的状态(因此可以实现回滚)。
在以太坊系统中,分叉是常态,orphan block 中的数据都要向前回滚,而由于 ETH 中有智能合约,为了支持智能合约的回滚,必须保持之前的状态。
代码参照以太坊的 Java 实现。
以上就是对Ethereum MPT
与红黑树数据结构的解析,在刷 LeetCode 痛苦的时候想过很多次这些学了也用不到,没想到那么快就有了应用场景,还是要好好理解和实践呀!