Tries

Characters along paths. Shared prefixes are stored once, which makes prefix queries natural.

The question

Which terms start with this prefix?

The structure responsible

Trie

In this lab: Build a trie from the real vocabulary, walk it, and measure what prefix sharing saves.

building the index…