Merkle-Patricia Trees. Часть 6

Обход путей в Patricia Tree

Обход Patricia Tree начинается с корневого узла. Каждый путь от корневого узла к узлу листа дерева соответствует адресу учетной записи. Для того, чтобы обойти дерево и найти состояние конкретного счета, вы следуете по пути, который соответствует интересующему вас адресу счета.

Ключи узлов вдоль пути - это отдельные полубайты адреса счета. В случае Ethereum адреса имеют длину 20 байт, то есть их можно разбить на 40 полубайтов.

Например, если вы хотите найти состояние учетной записи с адресом 0xabcdef, вы начнете с корня и сначала перейдете к дочернему элементу, который соответствует полубайту 0xa. Оттуда вы перейдете к дочернему элементу, соответствующему 0xb, затем к 0xc, и так далее, пока не пройдете всю последовательность полубайтов 0xa, 0xb, 0xc, 0xd, 0xe, 0xf.

В конце этого пути вы придете к узлу листа, который содержит состояние счета с адресом 0xabcdef.

Patricia Tree в Ethereum различает два типа узлов: узлы листьев и узлы расширения. Кроме того, в этих узлах может храниться ключ с четным или нечетным количеством разрядов. Для указания типа и длины ключа используется двухбитный префикс. Возможными значениями префикса являются:

0x00: Узел расширения, четное количество полубайтов.

0x10: Узел расширения, нечетное количество полубайтов.

0x20: Листовой узел, четное количество полубайтов.

0x30: Листовой узел, нечетное количество полубайтов.

Расширяющие узлы служат внутренними узлами, которые помогают ориентироваться в дереве, а листовые узлы являются фактическими держателями данных.

Четное и нечетное количество полубайтов связано с тем, как хранится ключ. Ниббл - это четырехбитное объединение, или половина октета (octet или октет - это 8-битный байт). Ключи в Patricia Tree Ethereum представлены в виде шестнадцатеричных строк, где каждый шестнадцатеричный символ представляет собой ниббл (4 бита).

Когда мы говорим о «четном» или «нечетном» количестве нибблов, мы имеем в виду длину пути от корневого узла до конкретного узла. Если число полубайтов в пути четное, узел имеет четный префикс (0x00 для расширения, 0x20 для листа), а если число полубайтов нечетное, узел имеет нечетный префикс (0x10 для расширения, 0x30 для листа).

Эти префиксы играют ключевую роль в обеспечении эффективного обхода и манипулирования древовидной структурой. Например, если у вас есть хэш узла и вы хотите получить его данные из базы данных, вы можете расшифровать префикс, чтобы узнать, является ли узел расширением или узлом листа, а также четное или нечетное количество полубайтов в ключе. Обладая этой информацией, вы можете эффективно расшифровать ключ и значение и продолжить обход или манипулирование данными, как это необходимо.

Фух, это достаточно сложная тема, и, вероятнее всего, потребуется прочитать пост и рассмотреть графику несколько раз, чтобы понять всю суть.

#merkle #patricia