| ISSUE 19/30 · COMPUTER SCIENCE |
~3 MIN |
FOUNDATION / SEARCH · WEEK 04 — SYSTEMS AT SCALE
The shortcut beside your data
START HERE
An online shop may hold millions of orders but still needs to find one order number almost instantly. A database is software that organises records. A database index is an additional lookup structure that helps find records without scanning every row. One common kind is a sorted tree. The guide takes extra space and must be updated, but it prevents the computer from checking every order for every search.
|
/ WHY NOW
You type an order number and a website retrieves one purchase from millions. Without help, the database could inspect rows one by one until it gets lucky. An index is the help: a separate, organised structure that points from searchable values to the full records.
|
/ THE IDEA
Think of the index at the back of a book. It repeats selected words in sorted order and gives page numbers. The repetition costs pages, but it prevents rereading the whole book for every question. To see the scale, imagine a simpler sorted guide where every comparison halves the names still possible. Common tree indexes use a related idea but can branch many ways at each level and work in whole storage pages.
THE FORMAL IDEA
binary search steps ≈ log₂(n)
| n = number of indexed entries | | this formula describes the toy sorted guide, where each comparison halves the remaining region | | log₂(n) = number of halvings needed to reach one item |
|
RUN THE TINY EXAMPLE
Find one name among 1,048,576
Unindexed worst case: inspect about 1,048,576 rows Ideal halving search: log₂(1,048,576) = 20 decisions Add the index: reads speed up; writes must update two structures
|
Real databases work in disk pages and use more than simple binary search, but the size difference captures why indexing changes product responsiveness.
/ SO WHAT?
This predicts the trade-off. Index fields people filter, join or sort by often; do not index everything blindly. Every extra index consumes storage and makes inserts and updates do additional work.
ONE CAVEAT |
| For a sorted index, usefulness depends on whether its leading column order matches the query. Other index types support different searches, and data distribution, caching and the query planner can still make an apparently sensible index irrelevant. |
KEEP THIS
A suitable database index trades storage and write work for a shorter route to matching records.
|
NEXT: What information entropy measures
|