Index concurrency: protect structure separately from transactions

Database literature often distinguishes latches, which protect short-lived in-memory structural operations, from transaction locks, which protect logical data access under an isolation protocol. Terminology varies, so identify the actual mechanism's duration and purpose. A page latch may prevent another worker from observing a partly rewritten slot array. A row or predicate lock may control a conflicting logical operation until transaction end. Releasing the page latch does not imply committing the transaction, and a row lock does not automatically protect every structural byte of the tree.

A buffer pin commonly keeps a page frame available while a worker references it; it is distinct from excluding concurrent content changes. Reclamation also needs to ensure that no active reader will interpret reused storage as an old page. Correct algorithms coordinate page lifetime, structural visibility, and recovery information. When analyzing a contention report, distinguish waiting for a buffer's I/O, waiting for a content latch, and waiting for another transaction. Those waits can have different remedies even when the query text is identical.

In a basic latch-coupling descent, acquire suitable protection for the child before releasing the parent. This prevents a gap in which the child relationship could be invalidated before the reader safely reaches it. Insertions may need stronger or retained ancestor protection if a child is unsafe for the intended structural change, such as lacking room for an insertion. Exact safety tests and restart rules depend on the algorithm. Holding every ancestor until transaction completion is not the definition of latch coupling and can unnecessarily serialize independent work.

The B-link approach adds fence information and right-sibling links so a reader following an older parent reference can move right after a split. In our distinct-key convention, a page's upper fence h excludes keys k≥h; such a key follows the right link. A parent update can then be coordinated without requiring every reader to have observed the newest separator first. The original Lehman–Yao algorithm establishes its result under a particular model. It does not imply that all B-trees use no reader latches or that publication ordering and memory reclamation can be omitted.

Write a schedule where a reader chooses a child, a writer splits that child, and the reader resumes. Show exactly which old reference remains valid and which fence directs recovery. Then consider a second split before the reader catches up, deletion of an empty page, and a crash between logged steps. A correctness argument must account for every permitted state, not merely the final balanced drawing. Optimistic methods can validate version counters and restart, but require their own rules for reading consistent state and preventing unsafe access during validation.

The queue lab illustrates contention pressure without implementing latches. Reset, set λ=4 and μ=4, predict the fluid backlog remains at four, then Play or Step. This is balance in a deterministic model, not a stable stochastic queue claim. For a separate run, Reset, set λ=5 and μ=4, predict growth of one waiting operation per second, then Play or Step. Increasing worker count cannot raise the service rate of an unchanged serial critical section indefinitely. Use an actual latch profile and a critical-section schedule to test whether that mechanism limits the real index.