Skip to content

data-structures

2 posts with the tag “data-structures”

A Map of Blocks

How a search engine keeps every word it knows in a few bytes each.

A search engine has to remember every word it has ever seen, keep them in order, and find any one of them in a fraction of a microsecond, often from a file it has not even read yet. The thirtieth familiar is really two: a tiny machine that spells out a whole vocabulary in about six bytes a word, and the dictionary that uses it as a table of contents.

The Fork in the Path

Matching a URL to one of a thousand routes in time that ignores how many there are.

Every request that reaches a server is a URL, and something has to decide which of a thousand handlers owns it before any real work starts. The obvious router gets slower with every endpoint you add. A radix tree does not: it walks the path, not the table, and stays flat at a thousand routes. The fourth familiar, and the forks in its tree are where it gets interesting.