Course contents
On this page
Lesson plan 10: Tree and hash indexes
Follow point and range lookups through a B+ tree and explain leaf links and separators.
The guided lesson now introduces one mechanism. This original plan covers the wider topic; follow the deeper-reading links at the end of the guided lesson for the remaining material.
Placement: Part 2: Representing and locating data.
Prerequisites: Lesson 09: Memory and buffer management, plus the earlier dependency chain.
Learning outcomes
- Follow point and range lookups through a B+ tree and explain leaf links and separators.
- Explain hash access, composite-key order, covering access, and page-split maintenance costs.
- Calculate how fanout and entry width influence height without treating an idealized bound as measured capacity.
- Separate a general mechanism, a documented implementation choice, and an illustrative numerical assumption.
Teaching sequence
- Establish the motivating situation: An index supports one tenant’s time-ordered feed but poorly supports a query missing the leading key.
- Introduce the vocabulary and the correctness obligation before an optimization. Define B+ trees, hashing, composite keys.
- Develop the mechanism: Trace lookup, leaf traversal, split publication, and a hash lookup; connect physical order to query shape.
- Follow the complete worked example: Fanout 200 gives capacities of 200, 40000, 8 million, and 1.6 billion leaf references across successive levels. Explain the assumptions, intermediate units, and limiting interpretation.
- Extend the scenario to changed load, skew, or failure, explaining covering indexes, range scans, splits, index maintenance.
- Connect the mechanism to a documented implementation and an alternative with a different workload fit. Close by stating the remaining cost and the next lesson dependency.
Required chapter material
Use a complete execution trace or worked calculation, supported by an annotated static diagram or table. Include language-neutral pseudocode or labeled SQL when it clarifies the mechanism. State preconditions, ownership, visibility, and failure boundaries for algorithms. Describe operational costs as well as the normal path. All questions raised in the narrative must be resolved in the text.
Visual explanation
A small B+ tree traces a search and a leaf split; a composite-key ordering table explains which predicates produce contiguous ranges. The accompanying prose explains the arrows, state changes, or table entries so the lesson remains understandable in a plain Markdown reader.
Editorial checks
Confirm that the numerical example agrees with its units and assumptions. Check that a faster path preserves the stated contract, or explicitly identify the changed guarantee. Keep hypothetical figures separate from product measurements. Explain both an appropriate use and a limitation of the case design. Check terminology against the glossary and links against the course index.