Spelled Out: Tries, Radix Trees and Finite State Transducers

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 59m

On 12 August 2014, Frankfurt network engineer Yusuf Demir watches chunks of the internet flicker as the global IPv4 routing table passes 512,000 routes, the default hardware limit of a widely deployed family of routers. In part eight of The Deep End's Data Structures series we build the structures that index by spelling: tries for autocomplete, Patricia and multibit tries for longest-prefix match, the adaptive radix tree that made tries as fast as hash tables, and the finite state transducers that let Lucene hold millions of terms in less space than the words themselves. We route a packet bit…