Apache Lucene — Part 2: Internals & the Segment Engine

maang.io System Design Series

What is this?

Back to the back-of-the-book index. In Part 1 we saw what the index is: term → the pages that mention it. Now watch how a publisher who's actually smart about it would keep such an index up to date for a book that keeps getting new chapters.

They would never re-typeset the whole index every time a paragraph is added — that's absurdly expensive. Instead they'd print the index for each new batch of chapters as its own small booklet, immutable once printed. To search, you check the main index and each booklet and combine the results. When booklets pile up, you occasionally reprint a few of them merged into one tidy volume. And when a chapter is deleted, you don't reprint anything — you just staple in an errata slip: "ignore entries for page 340." Nothing is ever edited in place; the index only grows by appending immutable pieces and is tidied by merging.

That is exactly how Lucene stores data. The booklets are called segments, and the whole buffer→flush→merge lifecycle is a close cousin of the LSM-tree you met in the Cassandra topic — immutable sorted files, background merges, deletes as tombstones. If Part 1 gave you the map, this chapter shows you the machine that maintains it.

The one-line idea: a Lucene index is a set of immutable segments. Writes buffer in RAM and flush into a brand-new segment; segments are never modified, only merged in the background; deletes and updates are recorded as marks, not edits. Immutability is what makes indexing fast, search lock-free, and caching trivially safe.

Let's follow a document in, then a query out, then unpack the two data structures — the FST and the compressed posting list — that make it all fit and fly.