create account

Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie) by thomasoss

View this thread on: hive.blogpeakd.comecency.com
· @thomasoss ·
Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie)
This article focuses the radix tree (radix trie, PATRICIA trie). The concept is used for example in Ethereum to store the state.

The article is part of a series starting with this article: [Blockchain Foundations Part 1: Distributed, Decentralized and Centralized Computer Architecture](https://steemit.com/blockchain/@thomasoss/blockchain-foundations-part-1-distributed-decentralized-and-centralized-computer-architecture)

The articles are drawn from my book "Blockchain and Crypto Currencies Easy to Understand for Everyone, Thomas Bauer". Please refer to the [part 1 article](https://steemit.com/blockchain/@thomasoss/blockchain-foundations-part-1-distributed-decentralized-and-centralized-computer-architecture) for a introduction to the blockchain foundations series.

# Radix Tree (PATRICIA trie)

A radix tree (radix trie, prefix tree, PATRICIA trie) is a search tree and an ordered data structure. Common prefixes are stored only once. Hence data stored in a radix tree is compressed. 

The subsequent figure shows edges and nodes. Each edge represents a character. Starting at root strings are stored this way. Characters of strings starting with the same characters are stored only once.

![](https://cdn.steemitimages.com/DQmaKYiGD8o81MNrcTLcHL1iAHWa4Gvupiq7MptEgJRJ9FF/image.png)
Figure 8: Trie (prefix tree)

A radix tree is a more compact form of this search tree. We can see it in the subsequent figure. The number of edges is reduced distinctly.

![](https://cdn.steemitimages.com/DQmPYNKNiFA8XzvSdtSbLPkGvcR7tC2XySPEudSWDddzTFF/image.png)
Figure 9: Radix tree (PATRICIA trie)

The term trie is derived from information retrieval. Often tree is used instead of trie. PATRICIA is an acronym for Practical Algorithm to Retrieve Information Coded in Alphanumeric.

Ethereum uses the radix tree to store the state. This is explained later in this article series.
properties (22)
authorthomasoss
permlinkblockchain-foundations-part-6-radix-tree-patricia-trie
categoryblockchain
json_metadata{"tags":["blockchain","radix","patricia","ethereum","foundations"],"image":["https://cdn.steemitimages.com/DQmaKYiGD8o81MNrcTLcHL1iAHWa4Gvupiq7MptEgJRJ9FF/image.png","https://cdn.steemitimages.com/DQmPYNKNiFA8XzvSdtSbLPkGvcR7tC2XySPEudSWDddzTFF/image.png"],"links":["https://steemit.com/blockchain/@thomasoss/blockchain-foundations-part-1-distributed-decentralized-and-centralized-computer-architecture"],"app":"steemit/0.1","format":"markdown"}
created2019-09-03 16:20:21
last_update2019-09-03 16:20:21
depth0
children1
last_payout2019-09-10 16:20:21
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length1,876
author_reputation18,405,060,383
root_title"Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie)"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id90,198,640
net_rshares0
@steemitboard ·
Congratulations @thomasoss! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

<table><tr><td><img src="https://steemitimages.com/60x60/http://steemitboard.com/img/notifications/firstpayout.png"></td><td>You got your First payout</td></tr>
</table>

<sub>_You can view [your badges on your Steem Board](https://steemitboard.com/@thomasoss) and compare to others on the [Steem Ranking](https://steemitboard.com/ranking/index.php?name=thomasoss)_</sub>
<sub>_If you no longer want to receive notifications, reply to this comment with the word_ `STOP`</sub>



###### [Vote for @Steemitboard as a witness](https://v2.steemconnect.com/sign/account-witness-vote?witness=steemitboard&approve=1) to get one more award and increased upvotes!
properties (22)
authorsteemitboard
permlinksteemitboard-notify-thomasoss-20190903t185923000z
categoryblockchain
json_metadata{"image":["https://steemitboard.com/img/notify.png"]}
created2019-09-03 18:59:21
last_update2019-09-03 18:59:21
depth1
children0
last_payout2019-09-10 18:59:21
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length795
author_reputation38,975,615,169,260
root_title"Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie)"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id90,203,526
net_rshares0