前書き#
最近、プロジェクトのスマートコントラクトの状態ツリーのデータ構造をレッドブラックツリーからトライに変更し、両方のデータ構造のパフォーマンスを比較するという仕事を受けました。トライは、Ethereum の公式 Java 実装ethereum/ethereumjを参考にしています。一方、レッドブラックツリーは自分で実装しました。この記事では、両方のデータ構造の理論と実際のパフォーマンスを比較した結果を記録しています。
データ構造#
レッドブラックツリー#
レッドブラックツリーは、近似的にバランスの取れた二分探索木であり、赤と黒のノードを持ち、任意のノードの左右の部分木の高さ差が 2 倍以下であることを保証します。
特性#
以下の 5 つの特性を満たす必要があります：
- ノードは赤または黒である。
- ルートノードは黒である。
- 葉ノード（NIL）は黒である。
- すべての赤いノードの子ノードは黒である。
- 任意のノードから葉ノードまでのパスには、同じ数の黒いノードが含まれる。
レッドブラックツリーは完全にバランスしているわけではありませんが、左部分木と右部分木のレベルは同じです。したがって、黒い完全バランスとも呼ばれます。近似的にバランスが取れているため、回転の頻度が低下し、メンテナンスコストが低下し、時間の複雑さが LogN に保たれます。
操作#
レッドブラックツリーは、自己バランスを保つために次の 3 つの操作を主に使用します：
- 左回転
- 右回転
- 色の変更
AVL 木との比較#
- AVL 木はより高速な検索操作を提供します（完全にバランスしているため）。
- レッドブラックツリーはより高速な挿入および削除操作を提供します。
- AVL 木はより多くのノード情報（バランスファクターと高さ）を格納するため、より多くのストレージスペースを占有します。
- 読み取り操作が多く、書き込み操作が少ない場合、AVL 木が適しています。これは主にデータベースに使用されます。書き込み操作が多い場合は、一般的にレッドブラックツリーが使用されます。シンプルで実装が容易であり、マップやセットなどのさまざまな高級言語のライブラリに使用されます。
コード実装#
レッドブラックツリーは比較的複雑なため、学習と参照のためにコードを GitHub にアップロードしました。
トライ#
トライは、ディクショナリツリーまたはキーツリーとも呼ばれ、大量の文字列の統計とソートに使用されます。例えば、検索エンジンのテキストディスク統計などです。
トライは無駄な文字列比較を最小限に抑え、高速なクエリを実現します。
特性#
- ノードは完全な単語を格納しません。
- ルートノードから特定のノードまでのパス上の文字を連結すると、そのノードに対応する文字列が得られます。
- 各ノードのすべての子ノードのパスは異なる文字を表します。
- ノードには追加の情報（出現頻度など）を格納することができます。
ノードの内部実装#
トライの高さは比較的低く、ストレージスペースを多く占有します。その核心アイデアは、共通の接頭辞を利用してクエリ時間を削減し、効率を向上させることです。単語の予測などのビジネスシナリオを自然に解決することができます。
コード実装#
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;
}
}
Modified Merkle Patricia Tries#
Ethereum のアカウント状態の保存方法#
- キーバリューのハッシュテーブルを使用して、ブロックごとに新しいトランザクションがパックされ、Merkle ツリーが変更されますが、実際にはごく一部のアカウントのみが変更されます。コストが高すぎます。
- アカウントを直接 Merkle ツリーに格納することはできません。内容を変更する場合は、Merkle ツリーを直接変更することはできません。なぜなら、Merkle ツリーには高速な検索と更新の方法が提供されていないからです。
- ソートされた Merkle ツリーを使用することもできません。新しいアカウントが生成されるたびに、アカウントアドレスがランダムになるため、挿入後に再ソートする必要があります。
MPT の構造#
Trie 構造の特徴を利用しています。
- 順序を変更しても、Trie 構造は変わらず、自然にソートされます。新しい値を挿入しても影響を受けません。イーサリアムのアカウントベースの構造に適しています。
- 更新の局所性が非常に高く、ツリー全体を走査する必要がありません。
ただし、Trie 構造はスペースを多く使用するため、キーバリューペアがスパースに分布している場合、効率が低下します。イーサリアムのアカウントアドレスは 40 桁の 16 進数であり、アドレスは 2^160 種類ありますが、非常にスパースです（ハッシュ衝突を防ぐため）。
したがって、Trie 構造をパス圧縮する必要があります。これがパトリシアトライであり、圧縮後、ツリーの高さが明らかに減少し、スペースと効率の両方が向上します。
Modified MPT の構造#
イーサリアムが実際に使用しているのは、Modified MPT の構造です。その構造は次のようになります。
新しいブロックが発行されるたびに、状態ツリーの新しいノードの値が変化し、元の値を変更するのではなく、いくつかの分岐を新しく作成して元の状態を保持します（したがって、ロールバックが可能です）。
イーサリアムシステムでは、フォークが頻繁に発生し、オーファンブロックのデータは前方にロールバックする必要があります。また、ETH にはスマートコントラクトが存在するため、スマートコントラクトのロールバックをサポートするために、以前の状態を保持する必要があります。
コード実装#
コードは Ethereum の Java 実装を参照しました。
まとめ#
以上がEthereum MPTとレッドブラックツリーのデータ構造の解説です。LeetCode の問題を解くときには、これらの知識は使わないだろうと何度も考えましたが、意外にもすぐに応用シーンが現れました。理解と実践をしっかりと行う必要があります！