B+ Trees and Hash Indexes: Choosing Through Page I/O

The purpose of an index is not to save a few comparisons. It is to reduce the number of pages a query reads.

B+ Tree preserves order

                         [40 | 80]          root
                    /        |        \
          [10 20 30] -> [40 50 60] -> [80 90 100]
             leaf          leaf           leaf

Internal nodes contain separator keys and child pointers. Sorted leaf pages contain index entries and links to neighboring leaves.

An equality lookup descends to one leaf. A range lookup finds its lower bound, then follows leaf links until it passes the upper bound. The same order can satisfy ORDER BY when the requested ordering matches the index.

In plain terms: internal pages are a directory; leaves are shelves. Once a range query finds its first book, it walks along the shelf.

Fanout keeps the tree shallow

The course uses a simplified 4,096-byte page, 4-byte key, and 8-byte pointer:

(2d × 4) + ((2d + 1) × 8) ≤ 4096
d ≈ 170

After allowing free space for updates, an illustrative average fanout is 133:

133³ ≈   2,352,637 entries
133⁴ ≈ 312,900,700 entries

These are scale estimates, not an exact formula for a particular engine. The lesson is that one page chooses among many children, so the tree gains levels slowly.

Writes maintain the tree

A full leaf splits and sends a separator to its parent. A parent can split in turn; only a root split increases tree height. After deletion, an underfull node tries redistribution with a sibling before merging.

Each additional index therefore adds work to inserts, updates, and deletes. Read improvement must justify write amplification and cache usage.

Hash gives up order

A hash index computes h(key) and jumps to a bucket. With even distribution and no long overflow chain, equality can be efficient. But neighboring values need not occupy neighboring buckets, so hashing cannot naturally serve range scans or ordered output.

Static hashing can accumulate overflow pages. Extensible hashing splits through a directory; linear hashing grows one bucket at a time. Both improve growth behavior without restoring key order.

In plain terms: hashing knows the locker number. It does not know which lockers contain “everything from 42 through 90.”

Reproduce the difference

CREATE TABLE events AS
SELECT g AS event_no,
       g % 1000 AS topic_id,
       DATE '2020-01-01' + (g % 1825) AS created_at
FROM generate_series(1, 1000000) AS g;

ANALYZE events;
CREATE INDEX events_no_btree ON events USING btree (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

Now test hash alone:

DROP INDEX events_no_btree;
CREATE INDEX events_no_hash ON events USING hash (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no = 424242;

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

Hash can support the equality predicate, not the range. The planner may still prefer a sequential scan when a query returns a large fraction of the table.

Read EXPLAIN in this order

Signal	Interpretation
Scan node	How rows are reached: sequential, index, or bitmap
Index Cond	Predicate that narrows index access
Filter	Predicate applied after candidates are read
estimated / actual rows	Cardinality-estimation quality
Buffers: hit/read	Cached versus read pages

EXPLAIN ANALYZE executes the statement. Use caution with writes.

Multicolumn indexes follow query shape

For equality on topic followed by a date range:

CREATE INDEX events_topic_date
ON events (topic_id, created_at);

The first column isolates one topic; the second narrows a range inside it. Column order determines which search space is reduced first.

Review card

• B+ Tree order supports equality, range, and sorting.
• Leaf links make range scans sequential after the first lookup.
• High fanout keeps the tree shallow.
• Split, redistribution, and merge are write costs.
• Hash serves equality, not ordered range access.
• A sequential scan can be correct when selectivity is low.
• Verify with actual rows and buffers, not one timing number.

Sources

• CS 411 B+ Tree and Hash Tables lectures.
• PostgreSQL index types
• PostgreSQL hash indexes

                         [40 | 80]          root
                    /        |        \
          [10 20 30] -> [40 50 60] -> [80 90 100]
             leaf          leaf           leaf

(2d × 4) + ((2d + 1) × 8) ≤ 4096
d ≈ 170

133³ ≈   2,352,637 entries
133⁴ ≈ 312,900,700 entries

CREATE TABLE events AS
SELECT g AS event_no,
       g % 1000 AS topic_id,
       DATE '2020-01-01' + (g % 1825) AS created_at
FROM generate_series(1, 1000000) AS g;

ANALYZE events;
CREATE INDEX events_no_btree ON events USING btree (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

DROP INDEX events_no_btree;
CREATE INDEX events_no_hash ON events USING hash (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no = 424242;

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

CREATE INDEX events_topic_date
ON events (topic_id, created_at);