Radix Trie, Patricia Trie or Compressed Trie

Radix Trie, Patricia Trie or Compressed Trie

Tree is synonym to Trie. When we talk about tree, below picture comes to our mind. Tree having lot of branches, green leaves.

You might be wondering how this is related to Blockchain. We will explain you in this post.

 

In our previous blog, we talk about Merkle tree, you can click here to read that post. Before we move to Trie (tree) introduction in Blockchain, let's understand some basics.

Data structure is one of most important concept in computer science. If you are from computer science background, you might have read/heard about different data structures and one of the concept is Trie (tree).

 

Key Value Pair

Trie is used to store the data in Key value pair. Before we jump to Trie, lets understand why we need Trie to store key value pair. Let's take one example to understand that.

Assume that we have one small box where we have kept 5 balls and every ball has some coin inside it as shown below.

{1 coins,2 coins,3 coins,4 coins,5 coins}

 

Let’s say, we need to pick a ball having 4 coins, for that we open the box start searching for that ball and during that search we may end opening all the files so this is inefficient process.

Now question comes, do we have any better way?

Yes, we do have better way, we can use Trie to make it more efficient. For that, let’s assign string key to each ball (means past the image of animal on each ball) so that it looks like below.

{ “Doge”: 1, “Cat”: 2, “Cate”: 3, “Dog”: 4, “Mouse”: 5 }

 

Here to search for the ball having 4 coins, we just need to check “Dog” image on the ball and simply pick that ball, this is more efficient and faster method.

 

What is Trie ?

Trie is data structure that is used to store key-value pairs where the keys are usually strings. Here keys are a sequence of elements from some fixed alphabet, for example strings.

Let's see how below key value stored in Trie.

{ “Doge”: 1, “Cat”: 2, “Cate”: 3, “Dog”: 4, “Mouse”: 5 }

 

Trie

Trie

 

Issue and challenge with Trie

Everything seems correct above so you might be thinking, what could be the issue with current trie structure. Let's understand these issues.

 

Memory :

One of the major issue with this trie structure is that, it take lot of memory and waste lot of space. Now question comes how ?.

If you have noticed, there are total 14 nodes in above trie to store these key value pairs and many of nodes contains null value.

 

Slowness:

Since there are 14 nodes to store these key value pairs and many nodes empty so it take lot of time to get to the actual value based upon key.

 

Any solution to these issues ? Yes, Radix, Patricia or Compressed Tree

Solution to above issue is Radix trie. Radix trie is also known as compressed or patricia trie. Let's understand what it is and why it is known as compressed trie.

As you can see in below diagram, we removed all nodes that were having NULL value and combined the nodes that makes unique value.

radix trie, patricia trie, compressed trie

 

Use of Patricia Trie in Blockchain

Now you understand the concept of trie and radix trie and question still remain how this helpful in Blockchain (mainly in Ethereum).

In Ethereum, we store the state in key value pair where key is account address and value can be like account balance etc. These key value pair stored in form of patricia trie.

This enable faster search. But how ?.

In normal, trie, to reach to value 2, we need to cover 3 nodes as shown in below diagram.

 

Search in Trie

Search in Trie

 

With Patricia tree, this search become more efficient as to reach to 2, we need to just cover only one node.

 

Search in Patricia Trie

Search in Patricia Trie

 

Inquire Now
close slider