Unit 4.4 · about 3 h
260 / 324Hash indexes, B-trees, selectivity and range scans
Assume Programming's indexes-query-plans unit and its scattered-versus-clustered comparison. Here you derive the structure underneath a probe and range scan rather than repeat the sequential-scan cost experiment.
- explain
- derive
You can now
- Derive B+tree fan-out, leaf capacity and lookup depth from an explicit page format.
- Trace a leaf split and distinguish copied leaf separators from promoted internal separators.
- Choose hash or ordered indexing for equality, ranges and a stated selectivity.
Covers
- Hash indexes, B-trees, selectivity and range scans
Study, in this order
3 steps
- Lecture 7: Hash TablesCMU 15-445/645 - database and storage core
Sections 2-5: hash tables, hash functions, static and dynamic hashing, pp. 1-4
- Lecture 8: Indexes & Filters ICMU 15-445/645 - database and storage core
Sections 1-2, Indexes and B+Tree, pp. 1-3; section 3.1, Node Size, p. 4; section 4.5, Bulk Insert, pp. 6-7
Depth · Use the B+tree structure and split rules, not the notes' broad claims about specific engines. Composite-index access is engine-dependent; do not infer a selective probe from an arbitrary non-leading predicate.
- DDIA, second edition: index trade-offsDesigning Data-Intensive Applications, 2nd edition - storage and transactions
Chapter 4, B-Trees, printed pp. 125-128, then Multicolumn and Secondary Indexes and Storing Values Within the Index, pp. 132-133
Focus on
- An internal node with \(f\) children needs \(f\) pointers but only \(f-1\) separator keys. Leaves store entries and links for ordered traversal.
- A range scan descends once to its first leaf, then follows leaf links. Fetching table tuples is additional work unless the index contains the required data and visibility can be established.
- Hashing supports exact-key lookup but gives no key order. Collisions need key comparison; resizing and overflow are part of the storage cost.
- Selectivity is the fraction of rows matching a predicate, not a promise that an index wins. Page occupancy, heap fetches, ordering and cache state also matter.
Reproduce closed-book
Derive a deliberately simplified, fully packed B+tree with 4096-byte pages, a 64-byte header including sibling-link space, 16-byte keys and 8-byte pointers or record IDs. Internal capacity obeys \(64+8f+16(f-1)\le4096\), so \(f=168\). Leaf capacity is \(\left\lfloor(4096-64)/24\right\rfloor=168\). For 1,000,000 unique entries, \(\left\lceil1000000/168\right\rceil=5953\) leaves, \(\left\lceil5953/168\right\rceil=36\) parents and one root: three index-page visits per uncached point lookup, excluding heap access. This is a model, not PostgreSQL's format or a measured I/O count. Then draw a separate tiny tree with at most three keys per leaf: insert 1,2,3,4, split it into
[1,2] and [3,4], and copy separator 3 into the root while retaining 3 in the leaf.Traps
- Using \(f\) separator keys for \(f\) children, or applying full-occupancy height as a worst-case bound.
- Counting an index lookup as the complete query cost when result tuples require heap fetches.
- Deleting the promoted separator from a leaf split. B+tree data entries remain in leaves.
Practice
The section mini-project covers this: rebuildable key-to-offset indexing, point and range fixtures, and a page-capacity derivation contrasting an ordered index with the in-memory hash index.
Self-test
-
Why is fan-out 168 rather than 169 in the model?
169 children need \(64+169\times 8+168\times 16=4104\) bytes. 168 children need 4080 bytes and fit. -
Does halving occupancy necessarily add a level?
No. Recompute leaf and parent counts with the new capacities; height changes only when the next level can no longer cover them. -
Why cannot a hash index answer a key interval by walking adjacent buckets?
Bucket placement follows a hash, not key order. Adjacent keys need not occupy adjacent buckets.
Completion criterion
Stop when
You derive all three tree levels, draw the split without losing an entry, and account separately for index pages, leaf scanning and heap fetches.
Mark passed, then open 4.5 Only mark this when you can do it without notes.Leads to
- 4.5 Sorting, join algorithms and query plans Use index probes and ordering as inputs to join algorithms.
Comes after
- 4.3 Pages, buffer pools and storage layoutsBuild a search structure from these pages.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
Also in this section
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.