Data Intensive Systems: Lecture 5

Access Methods and Data Entries

Access methods lead the engine to the right page instead of scanning all of them: a hash index computes a bucket and answers equality, a tree index keeps entries sorted and answers ranges and ordered scans as well. Whatever the family, the index must say how to reach the underlying record. That payload is the data entry.

Data entry ($k^*$). The information stored in the index for a search-key value $k$. It tells the DBMS how to reach the matching record or records. There are three classic forms, and the choice is orthogonal to whether the index is a hash or a tree.

Alternatives 2 and 3 cost less to maintain than Alternative 1, and a file with several indexes can give only one of them Alternative 1, because the data can be physically organized only one way at a time. Alternative 3 saves space under heavy duplication, but its entries become variable-sized: one long RID list can spread a single entry across several pages.

Example 1. Two access paths over one file.

An employee file is hashed on age, so its buckets hold the actual records: this is Alternative 1. A second index on salary should not duplicate those records, so it stores $\langle \texttt{salary}, \text{RID}\rangle$ pairs or $\langle \texttt{salary}, \text{RID list}\rangle$ entries instead.

Why Ordered Trees

Consider a range query:

SELECT *
FROM Student
WHERE gpa > 3.0

If the file were physically sorted on gpa, the DBMS could binary-search to the first match and then scan forward. The catch is that keeping the whole relation sorted is expensive: every insert and delete disturbs the order. The fix is to sort a smaller index file instead of the data, search the index first, and follow it to the data pages. Keeping the index ordered rather than the relation is exactly the idea behind the $B^+$-tree.

$B^+$-tree. A self-balancing, ordered, page-based tree. Search, insertion, deletion, and sequential access all run in $O(\log_F N)$, where $F$ is the fan-out and $N$ is the number of leaves.

Fan-out. The maximum number of child pointers an internal node can hold. Large fan-out is what keeps a disk-based tree shallow: one node is one page, each internal page packs many separator keys and pointers, and all leaves are chained in sorted order for range scans.

A $B^+$-tree is an $n$-way search tree, and its shape is pinned down by a few invariants.

• Balanced. Every leaf is at the same depth.
• Minimum occupancy. Every node except the root is at least half full.
• Inner node. Has between $\lceil n/2 \rceil$ and $n$ children; a node with $k$ children holds $k-1$ separator keys.
• Leaf node. Holds between $\lceil (n-1)/2 \rceil$ and $n-1$ keys.
• Root exception. The root alone may hold fewer entries than an ordinary internal node.

Internal nodes store only separator keys and child pointers; leaves store the actual data entries and are connected left to right by sibling pointers. The tree decides how to find an entry; the chosen alternative decides what the entry contains.

At implementation level a node is a sorted array of entries inside one page. An internal node with child pointers $P_1, \dots, P_q$ stores separator keys $K_1, \dots, K_{q-1}$, where $K_i$ separates the subtree under $P_i$ from the subtree under $P_{i+1}$. In a leaf, the value beside each key is a record pointer, a RID list, or the record itself, by the data-entry alternative, and prev/next links chain the leaves in key order.

Search

Search always starts at the root. At each internal node, key comparisons select one child pointer, and the descent stops at a leaf. The leaf then settles the query: the key is present, the key is absent (it would have to sit between two stored neighbors), or it is the first of a range that the sibling pointers continue. A lookup therefore returns either the matching entry or the exact leaf position where the key would belong, and this lower-bound behavior is what insertion and range scans reuse.

Insertion

Leaf split. When the target leaf is full, the DBMS allocates a new leaf, redistributes the entries evenly, and inserts a separator into the parent. If the parent also overflows, the split propagates upward.

Example 2. Insert 8.

The search reaches the first leaf because $8 < 13$, but $[2,3,5,7]$ is full. A new leaf is allocated, the values are split into $[2,3]$ and $[5,7,8]$, and separator $5$ (the new right leaf's first key) is copied into the parent. The parent has room, so the insertion stops there.

Root split. When an insertion reaches an overflowing root, the DBMS splits it and creates a new root above. This is the only case where the height of a $B^+$-tree grows.

Leaf splits and internal splits move keys upward in different ways, and this distinction is worth holding onto.

A leaf split copies up; an internal split pushes up.

Example 3. Insert 21 and split to the root.

Inserting $21$ into the full leaf $[19,20,22,23]$ splits it into $[19,20]$ and $[21,22,23]$, copying $21$ into the parent. The parent now overflows, so an internal split pushes $17$ up into a brand-new root. The tree is one level taller.

Redistributing entries differently could sometimes delay a root split, but most implementations use the local split rule because it is predictable and has low maintenance cost. The recurring lesson is that insertions begin locally at one leaf, yet their structural effect may travel all the way up.

Example 4. Insert 28, 6, and 25.

Inserting $28$ fits the rightmost leaf with no split. Inserting $6$ overflows $[5,7,8,11]$ into $[5,6]$ and $[7,8,11]$, copying $7$ up. Inserting $25$ overflows $[21,22,23,28]$ into $[21,22]$ and $[23,25,28]$, copying $23$ up; the parent then overflows and an internal split pushes $13$ up, giving the final two-level tree.

Deletion

Deletion. Remove a key from its leaf. If the leaf still meets the minimum-occupancy rule, the work is done. Otherwise the tree rebalances by redistribution or merge.

The standard pattern descends to the leaf $L$ holding the entry and removes it. If $L$ is still at least half full, stop. If not, try redistribution: borrow an entry from a sibling under the same parent. If no sibling can spare one, merge $L$ with a sibling and delete the corresponding separator from the parent. An underflowing parent triggers the same logic one level up, and if the root is left with a single child, that root is removed and the tree shrinks by one level.

Example 5. Delete 19, then 20.

Removing $19$ leaves $[20,22]$, which is legal. Removing $20$ leaves $[22]$, which underflows, so the leaf borrows from its right sibling $[24,27,29]$: the boundary shifts to give $[22,24]$ and $[27,29]$, and the parent separator updates from $24$ to $27$. A leaf-level boundary key is copied up, because leaves keep the actual entries.

Example 6. Delete 24 and shrink the tree.

Removing $24$ turns $[22,24]$ into $[22]$. Its sibling $[27,29]$ is already at minimum, so borrowing fails and the two merge into $[22,27,29]$. The parent loses a separator and underflows, so the merge propagates up, the old root is removed, and the tree height drops by one. Deletion can do the opposite of insertion: insertion may raise the height, deletion may lower it.

Redistribution is not only for leaves; internal nodes can redistribute too, but the mechanics differ. At the non-leaf level the move goes through the parent: one separator from the parent drops into the underfull node, one separator from the fuller sibling rises into the parent, and the child pointer travels with that separator. It is a push-through-parent rotation, not a direct sideways shift.

Example 7. Non-leaf redistribution.

The underfull internal node receives a separator pushed down from the parent, while a separator from the richer sibling is pushed up to replace it, carrying its child pointer along.

Range Scans and Clustering

A $B^+$-tree shines on ordered scans because the leaf chain already holds keys in order. To read many records in key order, the DBMS descends to the leftmost relevant leaf and then follows leaf links rightward. The traversal is identical regardless of how the data sits on disk; what changes is how leaf entries map to table pages.

Clustered index. An index whose logical order matches the physical order of the table data, so nearby entries point to nearby records. The table is stored in the sort order of one chosen key, either heap-organized but kept in that order or index-organized with the rows in the leaves. Because a file has only one physical order, a table has at most one clustered organization.

With a clustered index, consecutive leaf entries land on nearby table pages, so a scan reads data pages in mostly sequential order. With an unclustered index, consecutive entries point to tuples scattered across the file, so following the leaf order can trigger many random reads.

Design Choices

Real systems share the core $B^+$-tree but make many low-level choices, starting with node size. A larger node raises fan-out and shrinks the tree, but takes longer to search once loaded. As a rule, the slower the device, the larger the best node.

These are only guidelines: long leaf scans favor larger nodes, while repeated root-to-leaf lookups favor smaller nodes that fit caches.

The half-full rule is likewise a guarantee about the ideal structure, not always a strict policy after every delete. Many systems delay merging because inserts usually outnumber deletes (a sparse page may soon refill), eager merging causes extra page movement and separator churn, and average occupancy settles near $67\%$. Some prefer periodic rebuilding over aggressive merge-on-delete.

Variable-length keys raise the question of how to pack them into fixed-size pages.

• Pointer-based keys. Store a pointer to the real value instead of the value.
• Variable-length nodes. Manage free space inside the page, like a slotted page.
• Padding. Pad every key to its type maximum: direct but wasteful.
• Key indirection. A small array of offsets into a key area inside the node.

The trade-off is the usual one: a fixed-width layout wastes more space, while a compact layout complicates memory management.

Once a node is in memory, the DBMS still has to find the right entry inside it.

Interpolation search estimates the landing spot rather than always probing the middle:

where $x$ is the search key. It works best when key values are spread fairly evenly.

Concurrent Access

Concurrency is harder in a tree than in isolated heap pages, because pages depend on one another structurally. Latching one page protects it against concurrent modification, but a split or merge also rewires parent-child relationships, so several pages must be synchronized together.

Lock coupling (latch crabbing). During a top-down traversal, a thread latches a parent, then latches the child it is about to enter, and only then releases the parent. The traversal keeps a short, overlapping chain of latches as it descends.

Shape in Practice

In practice, $B^+$-trees are shallow. Textbooks often parameterize a tree by $d$, where an internal node has between $d$ and $2d$ children. With $d = 100$ and an average fill of about $67\%$, the average fan-out is

which already gives enormous capacity.

So in practice the root is almost always in memory, often one or more upper levels too, and only the lower levels need regular I/O.