Radix Tree

Definitions

1. A space-optimized trie (prefix tree) in which each node with a single child is merged with that child, so edges represent multi-character strings rather than individual characters. Radix trees are widely used in HTTP routers (like httprouter in Go), IP routing tables, and the Linux kernel's page cache for fast prefix-based lookups.

   In plain English: A compact tree structure that efficiently stores and looks up strings by their shared prefixes — like a phone book organized by common beginnings of names.

   Example: "The router uses a radix tree so matching /api/v2/users/:id against thousands of routes is O(path length), not O(number of routes)."

Related Terms

• Amortized Analysis
• JSON Pointer
• Navigation Guard
• Persistent Data Structure
• Ring
• Segment Tree
• Skiplist
• Union Find