マークルパトリシアトライとは何ですか？イーサリアムではどのように利用されていますか？

はい、承知しました。それでは、一見難しそうに聞こえる「マークル・パトリシア・トライ」について、平易な言葉で解説していきましょう。

マークル・パトリシア・トライ（Merkle Patricia Trie）とは？

イーサリアムを、巨大で常に更新され続けているグローバルな公開台帳だと想像してみてください。これほど膨大なデータを、間違いなく、改ざんされずに、しかも高速に検索できるように管理するには、非常に優れたデータ構造が必要です。マークル・パトリシア・トライ（Merkle Patricia Trie、略称MPT）は、イーサリアムが採用している、この「スーパーファイルキャビネットシステム」なのです。

理解しやすくするために、これを二つの部分に分けて見てみましょう。「Merkle（マークル）」 と 「Patricia Trie（パトリシア・トライ）」 です。

まず、要素ごとに見ていきましょう

1. トライ（Trie、別名：辞書木） - 賢い「パス圧縮」ファイルキャビネット

「トライ（Trie）」という木構造は、「辞書木」とも呼ばれ、辞書を引く際に使う、部首で検索する目次のようなものだと想像してみてください。これは、(アドレス, アカウント残高) のような「キーと値のペア」（Key-Value Pair）の保存と検索に非常に優れています。

その賢い点は、「パス共有（Path Sharing）」 にあります。

例えば、二つのデータを保存すると仮定しましょう。

• キー cat に対応する値は 🐱
• キー car に対応する値は 🚗

一般的なシステムであれば、これらを完全に独立した二つのデータとして保存するかもしれません。しかし、トライは次のように処理します。

• キーである cat と car の最初の二文字 ca が共通していることを発見し、c → a というパスを共有させます。
• そして、a のノードから分岐し、一方は t（🐱 を格納）、もう一方は r（🚗 を格納）を指し示します。