Indexes

An index is a data structure that, when given a specific piece of data, is able to find corresponding information quickly. Much like an index in a book, which maps phrases to page numbers, an index is able to take a given value and return data related to that value.

Finding data is frequently one of the most expensive operations that a system will undertake. Consider looking up orders for a given customer: when there are one hundred orders it may be relatively trivial task to simply look through all the orders and pull out the desired orders; if there are a million orders, this becomes a much more challenging task.