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
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 for a introduction to the blockchain foundations series.
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.
