An Introduction To Tries

2018/04/05 Christian Seberino

1cMuhjTGzOLV5U K ZTIu6w

I will describe tries and explain why they are so important.

Introduction

1PspwIHWBVRfeUmS3hppEhA

Tries are used extensively in blockchain systems and elsewhere. They are tree structures that represent sets of key value pairs in software. It is possible to instead just represent key value pairs contiguously. However, then it would be more difficult to make changes and perform searches than with tries. Tries are composed of connected nodes that store values. Different nodes imply different keys based on their positions. A common application that uses tries is internet routing.

Examples

1NxSDER7l2eRRfmzsa17Xlg

In the trie diagram above, the dots represent nodes and line segments represent connections. Note that each dot has a left and right line segment below it. The key corresponding to each node is found as follows:

  1. Find the path from the top node to the node.
  2. For each left line segment along the path, add a "0" to the key.
  3. For each right line segment along the path, add a "1" to the key.

Therefore, the yellow dot corresponds to the key "010". The blue dot corresponds to the key "11". A similar procedure is used for all tries to determine keys.

1sxni7tZ2TQ9PR1 lFPFlaQ

The diagram above represents a trie where each node connects to 16 nodes below it. Note that each line segment will add one of 16 possible values (nibbles) to the keys. Therefore, the yellow dot corresponds to the key with the hexadecimal representation "0x0f2". The previous trie diagram represented 15 nodes. This one represents 4369 nodes!

Compression

1BM8klqQeu4ZTO9BxU7dC8w

When representing sets of key value pairs with tries, there is often thousands of unused nodes. Compression techniques are often used to more efficiently store tries with lots of unused nodes.

Nomenclature

1xPRi16jbkoUaQpF3OX3NJg

The terms radix trees and Patricia trees also refer to tries. Sometimes, but not always, these terms imply "compressed" tries that more efficiently manage unused nodes.

Conclusion

1fELeYRhN2hKLIbwtkX7dcw

Tries are tree structures that store key value pairs in a format that facilitates changes and searches. They are used extensively in many applications. Hopefully now you have gained the fundamentals to be able to take a deeper dive into these concepts.

Feedback

You can contact me by clicking any of these icons:

0eoFC6QOWZ  bCngK

0i3CwTFEKUnKYHMf0

0HQj6HSHxE7pkIBjk

Acknowledgements

I would like to thank IOHK (Input Output Hong Kong) for funding this effort.

License

0hocpUZXBcjzNJeQ2

This work is licensed under the Creative Commons Attribution ShareAlike 4.0 International License.