Algorithms and data structures · Intermediate

B-trees: examine many keys per page access

Understand how broad nodes and balanced height reduce page accesses in ordered indexes.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Place several separators in one node
  2. Trace a search for 35
  3. Maintain occupancy as keys change
  4. Distinguish the abstraction from a database implementation
  5. Ask Logeia about this articleCheck your understanding

Place several separators in one node

A B-tree is a balanced search tree whose nodes hold several sorted keys and child references. A node with separators [20, 50] can route a query into three key ranges: below 20, between the separators, or above 50. Fitting many separators into a storage page lets one page access select among many children. A high branching factor reduces tree height and therefore the number of pages along a root-to-leaf search path. This is particularly useful when accessing another page is expensive compared with comparing keys already in memory.

Trace a search for 35

Suppose the root contains [20, 50] and its middle child contains [28, 40]. A query for 35 chooses the middle child at the root and then the child between 28 and 40 at the next node. Key comparisons still occur within each page, but counting only comparisons misses the reason for broad nodes. The expensive event can be fetching a different page. Conversely, a logical page visit is not necessarily a physical device read: the root and other frequently used pages may already reside in a cache.

Maintain occupancy as keys change

When an insertion overflows a node, the implementation splits it and updates the parent’s separators. A full parent may also split, propagating the change upward. Splitting the root can add one level to the tree. Deletion may require redistribution from a neighboring node or merging nodes to restore occupancy requirements. Exact lower and upper bounds, and the meaning of the word “order,” vary between conventions. State the convention before calculating capacities. The essential idea is to maintain bounded occupancy and balanced leaf depth instead of allowing a long, skewed chain.

Distinguish the abstraction from a database implementation

Database indexes commonly use variants, including B+-tree-like layouts that keep records or record references at linked leaves. Ordered leaves help range scans, but the existence of an index does not guarantee that every query should use it. Returning a large fraction of a table, or using predicates poorly matched to key order, can favor a different plan. Maintaining indexes also consumes space and adds write work. Learn the broad-node principle, then inspect the actual database’s index format and execution plan. Avoid equating theoretical height, buffer-cache misses, and measured storage I/O.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 12

Choose a learning path