Hash and tree indexes

Why it matters

An index is the difference between reading one page and reading a million. The System Design track covers which indexes to create; this lesson covers what they are inside, using the classifications DBMS exams rely on and the structures engines implement. Knowing that a hash index cannot answer a range query, or that a table can have only one clustered index, prevents some very expensive mistakes.

The idea

An index is an auxiliary structure that maps search-key values to the location of matching records (a row id, or the primary key). Indexes are classified along several independent axes.

Classification	Meaning	Notes
Primary versus secondary	A primary index is on the key the file is ordered by; a secondary index is on any other attribute	Secondary indexes are always dense
Clustered versus non-clustered	Clustered: the data rows are stored in the index's order; non-clustered: rows are elsewhere and the index points to them	At most one clustered index per table
Dense versus sparse	Dense: one entry per search-key value (or per record); sparse: one entry per page or block	Sparse only works when the file is sorted on that key
Single-level versus multilevel	Multilevel: an index on the index, until the top level fits in one page	This is exactly what a B+ tree is

B+ trees

A B+ tree is a balanced multilevel index: internal pages hold separator keys and child pointers, leaves hold the keys with record pointers (or the rows themselves for a clustered table) and are linked left to right. With hundreds of keys per page, three or four levels cover hundreds of millions of rows, and the top levels stay in the buffer pool. Splits and merges keep every leaf at the same depth. The System Design B-trees lesson works through splits and write costs; the essentials here are that B+ trees support equality, range, prefix and ordered access, which is why they are the default index everywhere.

Hash indexes

A hash index applies a hash function to the key to choose a bucket (a page or chain of pages) holding matching entries. An equality lookup costs about one page read, but hashing destroys order, so a hash index cannot answer ranges, prefix matches or ORDER BY. Static hashing with a fixed number of buckets degrades as data grows (long overflow chains), so databases use dynamic schemes.

Scheme	How it grows	Notes
Static hashing	Fixed bucket count; overflow chains	Simple; degrades as data grows
Extendible hashing	A directory of 2^d pointers indexed by d bits of the hash; a full bucket splits, and the directory doubles only when needed	At most two page reads per lookup; directory doubling is the occasional cost
Linear hashing	Buckets split one at a time in round-robin order, regardless of which overflowed	No directory; smooth growth; temporary overflow chains

Bitmap indexes

For a column with few distinct values (status, region, a yes/no flag), a bitmap index keeps one bit vector per value with a bit per row. Conditions combine with fast bitwise AND and OR, and bitmaps compress extremely well, which is why analytical databases and data warehouses use them. They are poor for frequently updated OLTP tables, because one row's change touches shared bitmaps.

Using indexes well

Index-only scans answer a query from the index alone when it contains every needed column (a covering index). A composite index on (a, b) serves conditions on a, or on a and b, but not on b alone, because entries are sorted by a first. Every index speeds reads and slows writes, since inserts and updates must maintain each one.

Query	B+ tree	Hash	Bitmap
WHERE id = 42	Yes	Yes, cheapest	Only for low-cardinality columns
WHERE price BETWEEN 10 AND 20	Yes	No	Poor
ORDER BY created_at LIMIT 20	Yes, no sort needed	No	No
WHERE name LIKE 'Ra%'	Yes (prefix)	No	No
WHERE status = 'open' AND region = 'EU'	With a composite index	Per column only	Yes, bitwise AND

Trade-offs

B+ trees are general-purpose and order-preserving, at a few page reads per lookup and some write amplification. Hash indexes are marginally faster for equality and useless for anything else, so most engines offer them but rarely default to them. Bitmaps are excellent for low-cardinality analytics and poor for frequent updates. Clustering the table on one key speeds that key's ranges and makes every secondary index lookup a two-step access.

In an interview

Classify precisely and pick by query: "The table is clustered on order_id, so that is its primary, clustered, sparse-capable index; customer_id is a secondary, non-clustered, dense B+ tree index because we query by customer and date range. A hash index would not help the date range. For the warehouse's status and region filters, bitmap indexes combine cheaply."