CSE Roadmap

Core tier · about 2 hours · 6 parts

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.