How does database indexing work?

searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. Whereas with a sorted field, a Binary Search may be used, which has log2 N block accesses.

Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and a pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.

Since indexes are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided.

Useful Resources

The Joy of MongoDB Indexes

The Joy of MongoDB Indexes (Reprinted)

Bonus Quiz:
- Our cookbook now has three indexes: one on recipe name, one on ingredients, and one on ingredient->name. With the compound index in place, is it possible to eliminate either of the first two indexes we created?
Answer:
- Yes! We can safely tear out the single-key index on ingredients. Why? Because a search that just specifies an ingredient can use the index on ingredient->name. If we know an ingredient, we can, using that compound index, easily get a list of all page numbers containing said ingredient. Look again at the sample entries for this index to see why this is so.

MongoDB Document - Indexes

Single Field Index

db.collection.createIndex( { name: -1 } )

Compound Index

db.collection.createIndex( { userid: 1,  score: -1 } )
// the index sorts first by userid and then, within each userid value, sorts by score.