1

Can you explain to me the main differences between these 4 tries?

Thank you

1

A trie is just a trie of information such as storing the word dog would then store from top to bottom as d-o-g. The wikipedia page shows it in this picture: trie demonstration

As you can see it stores several words such as "to", "tea", "ted" "ten", "A", "inn". Each one of those words is a key in this data structure. So it I query a trie database with "to" it would return 7. It's traversal would first go to t then to. It saves time from search every word in a database. Think of it as simply creating a smaller and smaller group from iterating over each character. So let's say you query "ten" the database would first say let's look at all words beginning with "t", then "te", then "ten" which returns only one entry.

Radix trie includes an improvement to this structure. In my previous example of dog and dot being stored. Instead of storing d and o as nodes in the trie, it instead stores "do" as a node and "dog" and "dot" as sub nodes of that node. It means that there is less traversal, but if dam comes along it has to creates d-a-m and d-o-g since there is now a combination of d-a and d-o instead of just d-o words.

radix trie demonstration

I believe the picture is pretty self explanatory. It just instead of storing every character as a node of the trie, it instead concatenates characters that are used in all of the words below a node into one node. If you look at Ruber, before hand you could have pictured that rubens had only 1 node off of the e node. But since we added Ruber we had to create 2 nodes.

So that is the basics of tries, now to get into merkle patricia tries. Now here is a picture to help understand as we talk about how the merkle patricia trie works:

enter image description here

Now that is complex, but it helps you see as you go along how this trie works. As you can see there are now 3 different types of nodes, no longer are we just looking at "e" or "ear" in a bubble, but instead some more complex information, but it follows similar steps. There are some keys at the top that you can see. Look at "a711355" and it has a value of 45.0 ETH. Now try traversing the trie starting at the top. First we have an extension node that has a shared nibble of a7, then the next node it a branch node that has 16 different possibilities for the next traversal, so we choose 1 since we are following our key. Then the node from there has a key-end of 1355 which completed the traversal of the trie and we now receive a value of 45.0 ETH.

As you probably noticed each node has a part of the string, an extension node has a shared nibble which is the part of the string we use for traversal, the branch node contains 0-f in hex which will represent 1 character in the string, then the key-end in the leaf node represents the remaining traversal. The prefixes help the trie when being constructed.

Aside from the traversal there isn't a lot added to these tries, it is just optimized for huge data. For example an alternative to a Branch node would be 2-16 different nodes for each separate character in a radix trie.

For more technical information on how the merkle patricia trie is an optimized radix trie you can look at the wiki. I think I simplified what they were getting at pretty well.

Now I can get into how a levelDB would store these values, but that is getting outside of the question. Patricia tries are just radix tries so I didn't include a separate section for Patricia tries.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.