7.1. Indexing theory

We’ll proceed gradually, beginning with an extended analogy and ending with an exposition of some of MongoDB’s key implementation details. Along the way, I’ll define and provide examples of a number of important terms. If you’re not too familiar with compound-key indexes, virtual memory, and index data structures, then you should find this section eminently edifying.

7.1.1. A thought experiment

To understand indexing, you need a picture in your head. So imagine a cookbook. And not just any cookbook: a massive cookbook, 5,000 pages long with the most delicious recipes for every occasion, cuisine, and season, with all the good ingredients you might find at home. This is the cookbook to end them all. Let’s call it The Cookbook Omega.