BlockTree

A small index navigates; blocks store the terms. One enormous FST is not the answer.

The question

How does a dictionary too large for memory still get searched?

The structure responsible

Prefix index plus term blocks

In this lab: Compare an index over every term against an index over block keys, then look a term up through both.

building the index…