Database Reference
In-Depth Information
Then it's on to indexing in practice. We'll discuss unique, sparse, and multikey
indexes, and provide a number of pointers on index administration. Next, we'll delve
into query optimization, describing how to use
explain()
and work harmoniously
with the query optimizer.
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 famil-
iar 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 u n d e r st a n d in d e x in g , y o u n e e d a pi c t u re i n y o u r h e a d . S o i m a g i ne a c o o k b o o k .
And not just any cookbook: a massive cookbook, 5,000 pages long with the most deli-
cious 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.
Although this might be the best of all possible cookbooks, there are two tiny prob-
lems with The Cookbook Omega. The first is that the recipes are in random order. On
page 3,475 you have Australian Braised Duck, and on page 2 you'll find Zacatecan
Ta co s .
That would be manageable were it not for the second problem: The Cookbook
Omega has no index.
So here's the first question to ask yourself: with no index, how do you find the rec-
ipe for Rosemary Potatoes in The Cookbook Omega? Your only choice is to scan
through every page of the topic until you find the recipe. If the recipe is on
page 3,973, that's how many pages you have to look through. In the worst case, where
the recipe is on the last page, you have to look at every single page.
That would be madness. The solution is to build an index.
There are several ways you can imagine searching for a recipe, but the recipe's
name is probably a good place to start. If you create an alphabetical listing of each rec-
ipe name followed by its page number, then you'll have indexed the topic by recipe
name. A few entries might look like this:
Tibetan Yak Soufflé: 45
To a s t e d S e s a m e D u m p l i n g s : 4 , 0 1 1
Tur k e y à l a K i n g : 9 43
As long as you know the name of the recipe (or even the first few letters of that name),
you can use this index to quickly find any recipe in the topic. If that's the only way you
expect to search for recipes, then your work is done.
