У MPT (Merkle Patricia Trie) — есть 3 типа узлов:
- Branch Node — для ветвления, содержит от 1 до 16 ссылок на другие узлы, а также может содержать значение
- Extension Node — хранит часть пути, общую для нескольких дочерних узлов, содержит ссылку на Branch Node, который лежит далее
- Leaf Node — содержит часть пусти и хранимое значение, является конечным в цепочке.
Что мне не понятно — так это то, когда должен создаваться Extension Node или Leaf Node?
Если читать записанную структуру, то всё выглядит понятно:
/*
*
Допустим нам надо получить значение какого-то ключа, хеш (путь) которого равен
aec952b24ff4d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff.
Что мы делаем:
1. Сначала переходим в 10 узел (первый полубайт/ниббл [a] хеша)
2. Потом идём в 14 узел (второй ниббл [e] хеша)
3. Потом идём в 12 узел (третий ниббл [c] хеша)
4. Потом идём в 9 узел (четвёртый ниббл [9] хеша)
5. Потом приходим в конечный узел 52b2...80ff (оставшаяся часть хеша) где и лежит значение нашего ключа.
*
*/
const MerklePatriciaTrie = {
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {}, {},
// 10-ый узел первого уровня
{
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},
// 14-ый узел второго уровня
{
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},
// 12-ый узел третьего уровня
{
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {},
// 9-ый узел четвёртого уровня
{
"type": "leaf",
"partPath": "52b24ff4d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff",
"value": {
"name": "Patricia Trie"
}
},
{}, {}, {}, {}, {}, {}, {}, {}
]
},
{}, {}, {}, {}, {}
]
},
{}, {}, {}
]
},
{}, {}, {}, {}, {}, {}, {}
]
};
Но если бы у нас был ещё и Extension Node где-то между начальной и конечной точкой, то, возможно это должно выглядеть так?
//a e c952b24ff 4 d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff
const MPTWithExtension = {
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {}, {},
// 10-ый узел первого уровня
{
"type": "branch",
"children": [
{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},
// ******************* 14-ый EXTENSION узел второго уровня ********************
/*
То, что мне точно известно — это то, что Extension Node содержит
только ссылку на Branch Node.
Что касается выражения "partPath" — это только мои догадки... Не знаю
верно ли понимаю эту часть дерева.
Понимаю, что Extension Node используется оптимизации — т.е. вместо хранения 16 узлов
- хранится только одна ссылка на Branch Node. Именно поэтому у меня складывается мнение,
что Extension Node должен содержать какую часть пути (хеша). Если это не так, то прошу
поправить меня и объяснить как правильно понимать это.
*/
{
"type": "extension",
"partPath": "c952b24ff",
"nextNode": [
{}, {}, {},
// 4-ый узел третьего уровня
{
"type": "leaf",
"partPath": "d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff",
"value": {
"name": "Patricia Trie"
}
},
{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}
]
},
{}, {}, {}
]
},
{}, {}, {}, {}, {}, {}, {}
]
};
Так вот. Как это устроено в целом понятно.
Не понятно как это по итогу записывается? Ну, т.е. по какому принципу создаётся Leaf или Extension узел? И как вообще прокладывается и создаётся этот "ПУТЬ"?
Каким образом функция вычисляет количество вложенных уровней и вообще делает ли она это? Или как это устроено?
Можете показать функцию, которая бы добавляла в дерево новые значения на примере хешей (путей), чьё начало имеет одинаковые нибблы?
