ELI5 Как работает дерево Merkle-Patricia-trie?

Я понимаю, что Merkle tree - хэш хэш, у них есть то преимущество, что вы можете проверить только поддерево. Но как насчет Patricia ? Что означает trie ? И как он используется в Эфириуме?

43 голоса | спросил Roland Kofler 22 J0000006Europe/Moscow 2016, 13:42:44

2 ответа


51

Trie (также называемое цифровым деревом, префикс trie или radix trie)

Структура упорядоченных древовидных данных, которая используется для хранения динамического набора или ассоциативного массива, где ключи обычно являются строками. Позиция узла в дереве определяет ключ, с которым он связан. https://en.wikipedia.org/wiki/Trie

 введите описание изображения здесь>> </a> </p>

<p>  Три ключа для клавиш «A», «to», «tea», «ted», «ten», «i», «in» и «inn».  </p >

<p> <strong> Patricia </strong> -  Практический алгоритм для получения информации, закодированной в алфавитно-цифровом  (<a href = источник ) ( оргинальная бумага Дональда Р. Моррисона ). Patricia trie представляет собой двоичный radix trie - двоичный выбор на каждом узле при прохождении trie; это модифицировано в Ethereum.

 введите описание изображения здесь>> </a>
Источник: <a href= https://en.wikipedia.org/wiki/File:An_example_of_how_to_find_a_string_in_a_Patricia_trie.png

В ethereum используется шестнадцатеричный символ - X символов из 16-символьного «алфавита». Следовательно, узлы в trie имеют 16 дочерних узлов (16-символьный шестнадцатеричный «алфавит») и максимальную глубину X. Обратите внимание, что шестнадцатеричный символ называется «nibble».

Merckle Patricia Trie

Как описано здесь , термин Merkle следует, что

  

корневой узел становится криптографическим отпечатком всех данных   Структура

Эфириум Модифицированная Меркле Патриция Три

В желтой статье описывается модифицированная мерилка patricia trie. Это определяет три разных типа узлов; расширение, ветвь и лист. Они описаны, используя упрощенное мировое состояние, на диаграмме ниже:

 введите описание изображения здесь>> </a> </p></body></html>

ответил atomh33ls 22 J0000006Europe/Moscow 2016, 16:40:16
4

'Trie' происходит из поиска слов, так как он использует только префикс слова, чтобы найти его в словаре. Это упорядоченное дерево, где ключи обычно являются строками, заканчивающимися терминальным символом, и каждая вершина представляет собой префикс. Корень trie обычно представляет собой пустую строку, как мы видим на диаграмме, взятой из википедии.

 Диаграмма из Википедии

Для получения дополнительной информации о различии между деревом trie и radix (Patricia).

https://stackoverflow.com /вопросы /14708134 /что-это-разностной-между-синтаксического дерева-и-Radix-TRIE-структур данных

Дополнительные спецификации дерева Merkle Patricia, которые использует Ethereum, можно найти в блоге ethereum

https://blog.ethereum.org/2015/11/15 /merkling-в-Эфириума /

ответил rupshabagchi 22 J0000006Europe/Moscow 2016, 16:39:14

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132