Storage & Indexing
Indexing
A separate structure that trades extra storage and slower writes for dramatically faster lookups on specific columns.
Without an index, finding a row means scanning every row in the table and checking whether it matches — a full table scan. An index is a separate data structure, sorted or organized specifically to make lookups on a column fast, at the cost of extra disk space and slightly slower writes (every index has to be updated too).
Searching for key 13: a full scan compares 14 of 16 rows, one by one, until it finds a match — O(n).
B-tree indexes
The default index type in almost every relational database. A B-tree keeps keys in sorted order across a balanced tree of fixed-size pages, so a lookup, insert, or range scan all take O(log n) page reads no matter how large the table gets.
CREATE INDEX idx_orders_customer_id ON orders (customer_id);Hash indexes
Some engines offer hash indexes: a hash function maps a key straight to a bucket, giving O(1) point lookups. The catch is they only support exact-match queries — WHERE id = 5 — not range queries like WHERE id > 5, since hashing destroys the original ordering of the keys.
Composite and covering indexes
An index can span multiple columns ((customer_id, created_at)), which speeds up queries that filter or sort on that exact column combination — but column order matters: an index on (a, b) helps a query filtering on a alone, but not one filtering on b alone. A covering index includes every column a query needs, letting the database answer entirely from the index without touching the underlying table.