EnglishEnglish中文中文DeutschDeutschEspañolEspañolFrançaisFrançaisΕλληνικάΕλληνικάहिन्दीहिन्दीHrvatskiHrvatskiMalayMalayItalianoItaliano日本語日本語한국어한국어NederlandsNederlandsрусскийрусскийاَلْعَرَبِيَّةُاَلْعَرَبِيَّةُภาษาไทยภาษาไทยTürkTürkTiếng ViệtTiếng ViệtEditor
Learn
FAQs
Frequently asked questions by various stakeholders
Why Classic?
Start here to get the lowdown on Ethereum Classic's reason for being and unique value proposition
Knowledge
Further reading on the foundations that underpin ETC
Videos
A collection of videos and podcasts to keep you informed on ETC concepts and happenings
Support ETC by helping to translate this website!
Ethereum Classic Blog

An Introduction To Tries

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.

This page exists thanks in part to the following contributors:


cseberino
cseberino
  • EnglishEnglish
  • 中文中文
  • DeutschDeutsch
  • EspañolEspañol
  • FrançaisFrançais
  • ΕλληνικάΕλληνικά
  • हिन्दीहिन्दी
  • HrvatskiHrvatski
  • MalayMalay
  • ItalianoItaliano
  • 日本語日本語
  • 한국어한국어
  • NederlandsNederlands
  • русскийрусский
  • اَلْعَرَبِيَّةُاَلْعَرَبِيَّةُ
  • ภาษาไทยภาษาไทย
  • TürkTürk
  • Tiếng ViệtTiếng Việt
  • Editor
Add ETC to MetaMask
The ETC community is active on Discord
Discord
Discord
ETC Coop Discord
ETC Coop Discord
Github
Github
ETC Labs Github
ETC Labs Github
Reddit
Reddit
Twitter
Twitter
This site is powered by Netlify

Learn

  • FAQs
  • Why Classic?
  • Knowledge
  • Videos

Made with <3 for the Original Ethereum Vision