Part 3 of 6 · 1 min read
Why a lookup needs an index
Without an index, finding a key means scanning every stored record; an index turns that into a direct lookup.
Think of a pile of receipts dropped into one box in no particular order. Finding one specific receipt means checking every single one in the box. Compare that to a card catalog listing exactly which drawer holds each receipt, by its number.
In plain words: a key-value store without any index has to scan every stored record to find the one matching a given key. The cost of that scan grows with the number of records stored. An index fixes this. The simplest kind is an in-memory hash map pointing from each key straight to the location of its value. A lookup then costs roughly the same amount of work no matter how many records are stored. This is why every practical key-value store maintains some form of index over its keys.
A worked example. A key-value store holding one million carts, with no index, might need to check all one million entries to find cart:501, in the worst case. The same store, with a hash-map index from key to value location, finds cart:501 in roughly one step, regardless of how many other carts exist.
The key lines. No SQL; the index here is an internal data structure, not something a query expresses directly.
index = {"cart:501": offset_4096, "cart:502": offset_8192, ...}
get("cart:501") -> read value at offset_4096
Index (for a key-value store)
An index for a key-value store is a data structure, typically a hash map, that maps each stored key directly to the location of its value. It lets a lookup find a key's value without scanning every other stored record.
Example: a card catalog listing which drawer holds each receipt, instead of checking every receipt in an unsorted pile, mirrors an index turning a scan into a direct lookup.