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.  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.  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.
author | thomasoss |
---|---|
permlink | blockchain-foundations-part-6-radix-tree-patricia-trie |
category | blockchain |
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"} |
created | 2019-09-03 16:20:21 |
last_update | 2019-09-03 16:20:21 |
depth | 0 |
children | 1 |
last_payout | 2019-09-10 16:20:21 |
cashout_time | 1969-12-31 23:59:59 |
total_payout_value | 0.000 HBD |
curator_payout_value | 0.000 HBD |
pending_payout_value | 0.000 HBD |
promoted | 0.000 HBD |
body_length | 1,876 |
author_reputation | 18,405,060,383 |
root_title | "Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie)" |
beneficiaries | [] |
max_accepted_payout | 1,000,000.000 HBD |
percent_hbd | 10,000 |
post_id | 90,198,640 |
net_rshares | 0 |
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!
author | steemitboard |
---|---|
permlink | steemitboard-notify-thomasoss-20190903t185923000z |
category | blockchain |
json_metadata | {"image":["https://steemitboard.com/img/notify.png"]} |
created | 2019-09-03 18:59:21 |
last_update | 2019-09-03 18:59:21 |
depth | 1 |
children | 0 |
last_payout | 2019-09-10 18:59:21 |
cashout_time | 1969-12-31 23:59:59 |
total_payout_value | 0.000 HBD |
curator_payout_value | 0.000 HBD |
pending_payout_value | 0.000 HBD |
promoted | 0.000 HBD |
body_length | 795 |
author_reputation | 38,975,615,169,260 |
root_title | "Blockchain Foundations Part 6: Radix Tree (PATRICIA Trie)" |
beneficiaries | [] |
max_accepted_payout | 1,000,000.000 HBD |
percent_hbd | 10,000 |
post_id | 90,203,526 |
net_rshares | 0 |