Algorithms & data-structures that power Lucene & ElasticSearch
summary
Lucene stores a sorted term dictionary plus posting lists on disk and answers queries by iterating with next and advance, using a leapfrog algorithm (lead list by smallest doc frequency) to intersect postings cheaply. Regex and fuzzy queries compile to finite automata that are intersected with the term dictionary instead of testing every term. Numeric doc_values use bit‑packed deltas, table encoding, and a GCD trick (e.g., divide millisecond timestamps by 1000) to shrink bits per value. Cardinality uses HyperLogLog++: Murmur3 64‑bit hashes, few KB memory, mergeable and accurate at scale.
AI-written summary · about
chapters (8)
- 0:00Introduction to Lucene internals
- 1:30How inverted indexes work
- 5:08Executing term queries
- 6:09Conjunctions and leapfrog algorithm
- 9:23Regular expression queries
- 14:48Numeric values compression
- 25:04HyperLogLog for cardinality
- 36:43Closing remarks and Q&A
related talks
40mWhat's evolving in Elasticsearch and Lucene?
25mApache Lucene: From Text Indexing to Artificial Intelligence
55mFull-Text Search Demystified
46mFull-Text Search Internals with Elasticsearch
36mSearch on the fly: how to lighten your Big Data
31mUnspoken overhead of the Inverted Index
30mCaching for Speed: Practical Performance Optimization in OpenSearch & Lucene
39mEntity Linking at scale with Lucene