B-Trees: Ordered Pages, Fast Lookups

16.1.1 PLAIN — in simple words#

1. An ordered tree stores guides to smaller regions. A guide says which child region can contain the key you want. Each decision removes regions that cannot contain it.
2. The guide works because the keys obey an ordering rule. Without that rule, skipping a region could skip the answer.
3. Our teaching tree keeps actual key entries in leaves. Internal pages contain separator keys and child references. A separator is a boundary, not necessarily another stored record to return.
4. Every path from the root to a leaf has the same number of levels in the balanced tree we use. This prevents one unfortunate branch from becoming a long chain while others remain short.

16.1.2 PLAIN — a picture in your head#

1. A large archive has a sign: numbers below 25 are in the left room; numbers 25 and above are in the right room. Inside a room, another sign may divide the range further.
2. You do not open the wrong room because the signs and filing rules agree. The value 25 belongs to the right side because that is the boundary convention we chose.
3. Where the comparison breaks: a separator is encoded data interpreted by an algorithm, not a sign understood by a clerk. Different implementations can use different separator conventions. Equality must follow the specified convention, not an intuitive guess.

16.1.3 PLAIN — a worked example#

1. Here is the smallest two-leaf version of our toy tree. Each leaf can hold at most three keys. The root’s separator is the smallest key in its right child.

                 root: [25]
                 /        \
          keys < 25      keys >= 25
             /              \
        [10, 20]  ------>  [25, 30]
                     next leaf

2. Search for 20: compare with 25, follow the left child, then find 20 in [10, 20].
3. Search for 25: equality follows the right child under our rule, then finds 25 in [25, 30].
4. Search for 27: follow the right child, compare within [25, 30], and report absence. The tree does not return the nearest key unless the operation explicitly asks for a nearest or range result.

16.1.4 PLAIN — what is really happening inside#

1. Each internal page partitions its permitted key interval between child references. The selected child must contain every key that could match the lookup within that interval.
2. Separators are sorted. With several separators, the search chooses the region between adjacent boundaries or an edge region before the first or after the last.
3. Our equality-goes-right convention corresponds to selecting a child using the insertion position after equal separators. The companion model implements this with bisect_right on a small in-memory list. [S109]
4. The sorted keys inside a leaf then decide whether an exact entry exists. The absence conclusion follows from the leaf’s ordering and the correctness of the path, not from checking only one arbitrary nearby key.

16.1.5 TECHNICAL — the engineer’s version#

1. In this pedagogical B+ tree, internal nodes store ordered separators and child references; leaves store searchable entries and a next-leaf link. Search maintains the invariant that the target, if present, lies in the selected subtree.
2. The separator convention is explicit: each separator is the lower bound represented by the first key of the child immediately to its right. Other implementations may encode boundaries differently without changing the high-level ordered-tree purpose.
3. Product documentation often uses “B-tree” for an ordered multiway index with implementation-specific leaf and internal layouts. PostgreSQL’s description provides one concrete example, not the exact specification of our toy. [S105]
4. A valid structural invariant is necessary for correct lookup. It does not by itself provide durable writes, concurrent mutation safety, transaction visibility or recovery; those are later mechanisms.

16.1.6 WORDS — remember these#

1. Separator key: a boundary directing the next step — an internal key dividing ordered child ranges under a defined comparison convention. Leaf: the bottom searchable page — a node containing data entries rather than further child pages in this teaching B+ tree. Root: the starting guide — the top node from which every lookup begins.

16.2.1 PLAIN — in simple words#

1. A database tree is usually organised around pages rather than one separate allocation for every key. One page can hold many separators and references.
2. A page with many children has high fan-out. Each step can then choose among many regions instead of only two, keeping the number of levels small.
3. Wider keys and extra payload reduce how many entries fit. Partly filled pages also hold fewer entries than a perfectly packed capacity calculation assumes.
4. A shallow tree is helpful, but “three levels” does not automatically mean exactly three slow device reads. Some pages may already be cached, and retrieving the full row may add work beyond the tree.

16.2.2 PLAIN — a picture in your head#

1. One archive sign can list hundreds of room ranges. A visitor chooses one room from that sign, then one cabinet from the next sign.
2. If the signs could show only two choices each, the same archive would need many more successive decisions.
3. Where the comparison breaks: a physical page has byte limits, headers, reference widths and variable-sized keys. A sign’s number of lines is only an analogy for capacity; the real fan-out must be derived from the actual layout and occupancy.

16.2.3 PLAIN — a worked example#

1. Use an invented internal-page layout: 8,192 bytes per page, 128 bytes of fixed overhead, 8 bytes per child reference and 16 bytes per separator. With m children there are m - 1 separators.
2. The payload condition is 8m + 16(m - 1) <= 8,192 - 128, or 24m - 16 <= 8,064. The largest whole m is 336 under these simplified assumptions.
3. If a leaf entry also occupies an assumed 24 bytes, a leaf holds at most floor(8,064 / 24) = 336 entries. With one root and one leaf level, full capacity would be 336 × 336 = 112,896 entries.
4. Adding another full internal level gives 336 × 336 × 336 = 37,933,056 leaf entries. This is an upper-capacity illustration, not a guarantee that a real 38-million-row index has exactly three levels.
5. Real page overhead, variable key lengths, occupancy, duplicate representation and record locators change the result. The point is the multiplicative effect of fan-out, not the chosen number 336.

16.2.4 PLAIN — what is really happening inside#

1. Each page read brings several possible next decisions together. Searching within the page uses CPU comparisons; moving to a child may require another page access.
2. Root and upper-level pages are frequently reused. Caching them can make many lookups avoid repeated device access to those levels.
3. Index size affects cache residency. A wider covering index may save base-row retrieval while making its own pages less likely to remain in memory. These are competing effects to measure.
4. Page occupancy changes as entries arrive, split, are deleted or are reorganised. A capacity formula using completely full pages does not describe every point in that lifecycle.

16.2.5 TECHNICAL — the engineer’s version#

1. With effective fan-out B, an ordered balanced tree needs on the order of log_B N page levels for N entries under ordinary occupancy assumptions. Comparisons inside each page and fetching associated records are separate costs.
2. The fan-out calculation must include separator representation, child references, slot directories, headers and free-space policy. The arithmetic above deliberately uses a simplified fixed-width model.
3. PostgreSQL’s documented B-tree implementation has its own page and tuple constraints, sibling links, splitting behaviour and maintenance details. Do not infer its exact fan-out from our invented layout. [S105]
4. Keep logical page visits, buffer hits, device reads and bytes transferred distinct. A statement about one does not establish a count for the others.

16.2.6 WORDS — remember these#

1. Fan-out: how many next regions one guide can select — the number of child references in an internal tree node. Occupancy: how full a page is — the used share of its usable entry capacity under the actual layout. Tree height: how many levels a lookup crosses — the root-to-leaf depth under a stated counting convention.

16.3.1 PLAIN — in simple words#

1. Searching is repeated narrowing. At each internal page, compare the target with sorted boundaries and choose exactly the child range that can contain it.
2. At the leaf, compare actual keys and return either the matching entry or an explicit not-found result. A missing key is an ordinary outcome, not a broken tree.
3. The comparison rule must be consistent everywhere. If a parent orders text differently from a leaf, the path can lead to the wrong region.
4. Duplicate values require a representation policy. An index can contain several records with the same product identifier; it must still distinguish the entries or store an associated collection of locators.

16.3.2 PLAIN — a picture in your head#

1. Follow road signs to a house: district, street, then house number. At each sign, you keep only the direction that can contain the destination.
2. Arriving on the right street does not prove that house 27 exists. You still check the actual addresses.
3. Where the comparison breaks: roads can form loops and offer many routes. Our tree traversal follows a structural hierarchy, and correctness depends on its maintained range invariant. A cached guess is not a substitute for checking the relevant entry.

16.3.3 PLAIN — a worked example#

1. Use this larger toy tree, whose construction appears in section 16.4:

                         [35]
                    /            \
               [15, 25]          [45]
              /    |    \        /    \
          [5,10] [15,20] [25,30] [35,40] [45,50]

2. Search 25: at the root, 25 is below 35, so choose the left internal page. At [15,25], equality to 25 chooses its right-hand region. In leaf [25,30], the key exists.
3. Search 27 follows the same internal path, but the leaf contains no 27. Search 45 takes the root’s right side and then equality-goes-right at separator 45.
4. The tree height here is three node levels, counting the root and leaf. The small capacities are chosen to make all steps visible, not to imitate a practical page size.

16.3.4 PLAIN — what is really happening inside#

1. With separators s0, s1, ..., child zero contains keys below s0; child one begins at s0; and so on under our convention. Selecting the position after equal separators implements those intervals.
2. A binary search inside a page reduces comparison work compared with a linear search, but a very small page representation may use another strategy. The high-level tree invariant does not mandate one CPU algorithm.
3. For non-unique product keys, a conceptual composite entry (product_id, row_identity) supplies a total order among equal products. Another implementation can use a posting list of row locators. Either way, returning the first matching entry alone would not answer “all lines for this product.”
4. A real transaction may need to verify that a located row version is visible. Finding an index entry is a structural result; deciding whether its referenced version belongs to this query’s snapshot is a separate step.

16.3.5 TECHNICAL — the engineer’s version#

1. The toy lookup can use bisect_right(separators, key) to select an internal child, then bisect_left(leaf_keys, key) plus an equality check at the leaf. An insertion position alone is not proof of membership. [S109]
2. Search assumes a stable tree or an implementation that coordinates readers with mutations. Python list operations and the bisect module do not supply a complete concurrent B-tree protocol.
3. Collation and comparator consistency are structural requirements. A changed comparison rule can invalidate ordering assumptions even when stored bytes have not changed; engine-specific upgrade procedures must handle such changes deliberately.

16.3.6 WORDS — remember these#

1. Search invariant: the condition kept true at every step — the target, if present, remains inside the selected subtree’s permitted range. Record locator: information leading from an entry to its record — an engine-specific reference or identifying value used to retrieve associated data. Membership check: confirm that the target actually exists — equality verification after locating a candidate or insertion position.

16.4.1 PLAIN — in simple words#

1. To insert a key, first find the leaf where it belongs. If the leaf has room, place the entry in order. If it is full, the tree must create room without breaking its range rules.
2. Our toy splits an overflowing leaf into two ordered leaves and inserts a new separator into their parent. If the parent overflows, the split can propagate upward.
3. Splitting the root creates a new root and increases the tree’s height by one. Every leaf remains at the same depth because the new level is added above the whole tree.
4. This is why a tree can grow while remaining shallow. It is also why an insertion can touch more than the one leaf containing the new key.

16.4.2 PLAIN — a picture in your head#

1. A full filing drawer is divided into two drawers. A new sign tells visitors which numbers moved to the second drawer. If the signboard is itself full, it too must be reorganised.
2. The old sign cannot be left pointing to the wrong interval while people rely on it.
3. Where the comparison breaks: database engines must coordinate intermediate states, failures and concurrent readers. The toy’s neat before-and-after drawings omit the logging and synchronisation that make a real split safe.

16.4.3 PLAIN — a worked example#

1. Our toy rules are: at most three keys per leaf; at most four children per internal node; equality follows the right side of a separator. An overflowing four-key leaf splits into two two-key leaves.
2. Insert 10, 20 and 30. The root is still one leaf: [10,20,30]. Insert 25: the four sorted keys split into [10,20] and [25,30], and a new root has separator [25].
3. Insert 5, then 15. The left leaf overflows as [5,10,15,20] and splits into [5,10] and [15,20]. The root now has separators [15,25] and three children.
4. Insert 35, then 40. The right leaf splits into [25,30] and [35,40]. The root now has separators [15,25,35] and four children, still within its capacity.
5. Insert 45, then 50. The last leaf splits into [35,40] and [45,50]. The root would need five children, so split that internal level: the left internal node has the first three children with separators [15,25]; the right has two children with separator [45].
6. A new root [35] points to those two internal nodes. This is exactly the tree drawn in section 16.3. All ten inserted keys occur once at the leaves.

16.4.4 PLAIN — what is really happening inside#

1. Leaf splitting redistributes entries while preserving their order. The separator inserted into the parent describes the boundary between the resulting child ranges.
2. Internal splitting redistributes child references and their boundaries. A separator moves or is derived upward according to the chosen representation; it is not blindly copied as an extra record into a leaf.
3. Leaf-neighbour links must be updated as well. Range scans would otherwise skip the new leaf or follow an obsolete link even if point lookups through the root appeared correct.
4. A complete implementation must also handle deletion, borrowing, merging, root shrinking, duplicate keys and interrupted operations. This book’s insertion trace does not claim those mechanisms have been implemented merely because the drawing remains balanced.

16.4.5 TECHNICAL — the engineer’s version#

1. In the toy, an internal node with k separators has k+1 children. Splitting an overflowing five-child root into three-child and two-child internal nodes satisfies the chosen minimum of two children for non-root internal nodes.
2. Validate ordering, child-count relationships, equal leaf depth, separator-to-range consistency, leaf-chain order and complete key conservation after every insertion. A successful lookup for the last inserted key alone is weak evidence.
3. Real B-tree implementations use engine-specific split, concurrency and recovery protocols. PostgreSQL documents details including sibling links and page management. These do not follow automatically from the sequential in-memory toy. [S105]
4. A split can increase write and log work. Predicting its latency requires the actual page state, storage and concurrent workload; counting one logical INSERT is not a physical-write count.

16.4.6 WORDS — remember these#

1. Page split: divide an overfull region — redistribution into two nodes with updated parent boundaries and relevant sibling links. Split propagation: a full parent also needs room — upward restructuring triggered when adding a child exceeds an internal node’s capacity. Key conservation: no entry disappears or is invented — equality between the intended inserted entries and those represented after restructuring.

16.5.1 PLAIN — in simple words#

1. A range question asks for several nearby keys rather than one exact key. An ordered tree can first locate the beginning, then continue through neighbouring leaves.
2. The ordering tells the scan when it can stop. Once it reaches a key beyond the upper boundary, later ordered keys cannot belong to the requested range.
3. Boundaries must be explicit. “From 17 to 37” may include or exclude either endpoint. Dates and timestamps make this especially important.
4. A range scan returning many records still performs work proportional to the results and visited pages. A fast start does not make a million-row answer free.

16.5.2 PLAIN — a picture in your head#

1. Find the first shelf containing numbers at least 17, then walk along shelves until numbers exceed 37. You use the archive guide once to find the starting region, not again for every neighbouring folder.
2. If the shelf labels and links are correct, no return to the entrance is needed between adjacent folders.
3. Where the comparison breaks: physical leaf pages may not be adjacent on a device even when they are neighbours in key order. Following logical links is not a guarantee of perfectly sequential physical input-output.

16.5.3 PLAIN — a worked example#

1. Query the toy tree for the closed interval [17,37]. The starting lookup reaches leaf [15,20]. Skip 15 because it is below 17 and emit 20.
2. Follow the next-leaf link to [25,30]; emit 25 and 30. Continue to [35,40]; emit 35, then stop at 40 because it exceeds 37.
3. The result is [20,25,30,35]. Neither 17 nor 37 needs to exist as a stored key for the range to be meaningful.
4. For time windows, an often useful convention is a half-open interval: timestamp >= start AND timestamp < end. Adjacent windows then share a boundary without counting an event at that boundary twice. The convention must match the metric’s intended timezone and instant representation.

16.5.4 PLAIN — what is really happening inside#

1. The initial search identifies a leaf and an insertion position for the lower boundary. The scan emits qualifying entries from there and follows ordered successor information.
2. Inclusive and exclusive tests decide whether boundary-equal entries belong. A duplicate-key range must include every qualifying entry, not only the first occurrence.
3. The query may still need full-row retrieval and visibility checks for each candidate. If only indexed values are needed and the engine permits an index-only route, some of that work may be avoided.
4. Concurrent changes require a specified visibility contract. A stable ordered structure and a stable transaction snapshot are different properties. The former alone does not explain which newly inserted or deleted rows a long-running reader observes.

16.5.5 TECHNICAL — the engineer’s version#

1. A simplified B+ tree range cost is an initial tree descent plus traversal of relevant leaf pages and output processing. Writing this as O(log_B N + K/B) page-scale work assumes a particular layout and occupancy, with K qualifying entries; record fetching and CPU work are additional.
2. Ordered B-tree methods support equality and range comparisons under their operator families. Whether an SQL query uses that route depends on its expressions, collation, predicates and selected plan. [S104] [S106]
3. Logical leaf order, physical page placement and final result order are not synonyms. Keep the query’s ORDER BY explicit, even when an ordered access path currently supplies the desired sequence.

16.5.6 WORDS — remember these#

1. Range scan: walk entries between boundaries — ordered traversal beginning near a lower bound and stopping when an upper condition fails. Half-open interval: include the start but not the end — an interval [a,b) useful for adjoining non-overlapping ranges. Successor link: the route to the next ordered region — a reference or traversal mechanism connecting neighbouring entries or leaf nodes.

16.6.1 PLAIN — in simple words#

1. The toy explains ordered navigation and splitting. A production database must solve additional problems: several readers and writers, crashes, damaged pages, space reuse and transaction visibility.
2. A tree that passes a sequential insertion test is not automatically safe to use from several threads. A saved tree file is not automatically durable after sudden power loss.
3. Database products also make different choices about what leaves contain, how duplicates are represented and where the actual row lives.
4. Use the common idea to understand documentation, then read the particular engine’s promises before depending on an implementation detail.

16.6.2 PLAIN — a picture in your head#

1. A scale model bridge shows how beams connect. It does not certify a full-size bridge’s foundations, materials, wind response or inspection schedule.
2. The model is valuable when it teaches the load path and clearly states what it omits.
3. Where the comparison breaks: software correctness depends on discrete invariants and failure schedules as well as physical hardware. A database tree cannot be certified merely by making the toy larger or running the same happy path many times.

16.6.3 PLAIN — a worked example#

1. Suppose an insertion updates the new leaf but crashes before the parent’s separator is saved. A restarted reader following only the old root may miss the inserted region.
2. Alternatively, suppose the parent becomes visible before the new leaf is valid. A reader may follow a reference to incomplete data. These are hypothetical failure schedules, not observations from the toy lab.
3. Logging, ordered persistence and engine-specific recovery protocols address such states. Chapters 28 and 30 explain why “write all the files eventually” does not establish safe acknowledgement.
4. A concurrency test must also control a reader’s interleaving with a split. A sequential test that inserts everything and only then reads cannot expose every intermediate-state defect.

16.6.4 PLAIN — what is really happening inside#

1. Real implementations protect short structural operations and coordinate transaction-level behaviour. A latch protecting an in-memory page is not automatically the same thing as a transaction lock governing a business record.
2. Page checksums can detect some corruption but do not establish correct business values. Recovery needs a defined relationship between persisted pages and recovery records.
3. Versioned entries can remain after a logical update or deletion until no relevant reader needs them and cleanup is safe. The visible row count may therefore differ from physical entry and page counts.
4. Operational evidence must name the engine, version, access method and observation tool. A generic B-tree diagram cannot establish what a specific production index contains at a particular moment.

16.6.5 TECHNICAL — the engineer’s version#

1. The chapter’s toy specification covers unique integer keys, sequential insertions, point membership, range traversal and structural validation. It intentionally omits concurrent mutation, deletion rebalancing, crash recovery, disk formats and transaction isolation.
2. SQLite’s query-planning description and PostgreSQL’s B-tree implementation documentation illustrate related but different storage organisations. Treat their details as product contracts, not interchangeable definitions. [S89] [S105]
3. Structural validation and model-based tests are useful: compare every operation with a simple sorted-set oracle and verify all invariants after each mutation. They establish the tested toy behaviour, not a proof for untested mechanisms.
4. This distinction will recur throughout the book. An explanatory model can be correct within its boundary without constituting a deployable system.

16.6.6 WORDS — remember these#

1. Latch: short-lived protection of an internal structure — a synchronisation mechanism distinct from a transaction’s logical locking policy. Oracle: an independent expected-result mechanism — a simpler model used to compare the behaviour of a tested implementation. Structural validation: check that the representation obeys its rules — inspection of ordering, ranges, links, occupancy and depth invariants.