B+ trees

Why it exists

The B tree of the previous page is balanced and flat, but a database needs two more things: range queries (all records with keys between $a$ and $b$) and the highest possible fan-out of the inner nodes. The B+ tree keeps all keys and record pointers in the leaves, uses the inner nodes only as signposts (so more of them fit in a block) and links the leaves into a sorted chain. It is the standard index of nearly every database system, and GATE asks for its orders, its capacity and the result of insertions and deletions.

Prerequisites

You need the B tree: order, splitting and merging (B trees).

Precise definitions

A B+ tree with internal order $m$ and leaf capacity $L$:

• Inner nodes hold up to $m - 1$ keys $k_1 < \cdots < k_{j}$ and $j + 1$ children; the subtree of child $i$ contains the keys $k_{i} \le x < k_{i+1}$ (with $k_0 = -\infty$, $k_{j+1} = +\infty$): a key equal to a separator is in the right subtree. Non-root inner nodes have at least $\lceil m/2 \rceil$ children; the root has at least $2$ (unless it is a leaf).
• Leaves hold up to $L$ keys, each with a record pointer (or the record), and a pointer to the next leaf. Non-root leaves hold at least $\lceil L/2 \rceil$ keys.
• Every key of the file appears in a leaf; the keys in inner nodes are copies (separators) and some of them may no longer exist in the file.
• All leaves are at the same depth.

Orders from the block size ($B$ block size, $V$ key, $P$ block pointer, $P_r$ record pointer):

• inner node: $p$ pointers and $p - 1$ keys: $p P + (p - 1) V \le B$, so $p = \lfloor (B + V)/(P + V) \rfloor$;
• leaf: $L$ pairs (key, record pointer) and one next-leaf pointer: $L (V + P_r) + P \le B$, so $L = \lfloor (B - P)/(V + P_r) \rfloor$.

Example: $B = 512$, $V = 9$, $P = 6$, $P_r = 7$: $p = \lfloor 521/15 \rfloor = 34$ and $L = \lfloor 506/16 \rfloor = 31$. (Compare the B tree order $24$ for the same sizes: the signposts are smaller, so more of them fit.)

How it works

Search and range queries

An exact search always descends to a leaf: with $h$ levels it reads exactly $h$ nodes (blocks), plus one block for the data record if the leaf holds a record pointer. A B tree may find a key higher up; the B+ tree's cost is the same for every key, which makes performance predictable.

A range query $[a, b]$: search for $a$ (reaches the leaf where $a$ belongs), then follow the leaf chain, collecting keys, until a key $> b$ is met.

The tree of the animation has internal order $4$ and leaves of up to $3$ keys. The query $20..55$ reads $2$ nodes (the root and the first leaf $[5, 15, 20]$), then follows the chain to the leaves $[25, 30, 35]$, $[45, 55]$ and $[65, 75]$ ($3$ more reads) and stops there because $65 > 55$: the answer is $20, 25, 30, 35, 45, 55$. No inner node is read twice. In a B tree the keys of a range are scattered over inner nodes and leaves, so the query would climb up and down repeatedly.

Insertion

1. Search down to the leaf where the key belongs; insert it in sorted order.
2. If the leaf has more than $L$ keys, split it: the left leaf keeps the first $\lceil (L+1)/2 \rceil$ keys, the right leaf the rest; the smallest key of the right leaf is copied up into the parent as a separator (it stays in the leaf), and the leaf chain is updated.
3. If the parent now has $m$ keys it overflows: split it around its median key, which is moved up (not kept below). Repeat toward the root; a root split adds a level.

Inserting $5, 15, 25, 35, 45, 55, 65, 75, 20, 30$ with $m = 4$, $L = 3$: the leaf $[5, 15, 25]$ overflows at $35$; the split gives $[5, 15]$ and $[25, 35]$ and $25$ is copied up to a new root. Later splits copy $45$ and $65$ up. The final root is $[25, 45, 65]$ over the leaves $[5, 15, 20]$, $[25, 30, 35]$, $[45, 55]$, $[65, 75]$. Note that the copied key $25$ is both in the root and in a leaf.

Deletion

1. Search down to the leaf and remove the key. A copy in an inner node may stay: it is still a valid separator.
2. If the leaf has fewer than $\lceil L/2 \rceil$ keys, borrow one key from a neighbouring sibling that has more than the minimum (and update the separator in the parent), or merge with a sibling (and remove the separator from the parent).
3. If an inner node underflows (fewer than $\lceil m/2 \rceil$ children), borrow through the parent (rotate a separator) or merge with a sibling together with the separator that comes down. A root left with one child is removed.

From the tree above, deleting $15$ is harmless. Deleting $5$ leaves the first leaf with one key (minimum $2$): it borrows $25$ from its right sibling. Deleting $35$ leaves a leaf that cannot borrow, so two leaves merge and the parent loses a separator. Deleting $45$ ends with a borrow from the left sibling.

Capacity and height

With $c = \lceil m/2 \rceil$ and $h$ levels (the last one the leaves):

• maximum number of keys: every node full: $L \cdot m^{h-1}$;
• minimum number of keys ($h \ge 2$): root with $2$ children, other inner nodes with $c$ children, every leaf with $\lceil L/2 \rceil$ keys: $2\,c^{h-2} \lceil L/2 \rceil$.

For $p = 34$, $L = 31$: a $3$-level tree holds between $2 \cdot 17 \cdot 16 = 544$ and $31 \cdot 34^2 = 35\,836$ keys. A tree with $n$ keys has $\lceil \log_m (n / L) \rceil + 1 \le h \le \lfloor \log_c (n / (2 \lceil L/2 \rceil)) \rfloor + 2$ levels approximately; the exact levels for the block of the earlier pages ($B = 1024$, $V = 9$, $P = 6$, $P_r = 7$):

A B+ tree with $68$ pointers per inner node and $63$ keys per leaf indexes a million keys in $4$ levels; a search reads $4$ blocks (and one more for the record). The B tree with the same block size has order $47$ and needs $4$ to $5$ levels.

B tree against B+ tree

Worked examples

Cheat box

Traps and GATE patterns

Connections

The B+ tree refines the B tree (B trees) and replaces the static multilevel index (ordered indexes); hashing is the alternative for equality searches (hash-based file organisation).

PYQs

In a B+ tree where each node can hold at most four
key values, a root to leaf path consists of the
following nodes:
A = (49, 77, 83, ), B = (7, 19, 33, 44), C = (20*,
22*, 25*, 26*)
The *-marked keys signify that these are data
entries in a leaf.
Assume that a pointer between keys k1 and k2 points
to a subtree containing keys in [k1, k2), and that when
a leaf is created, the smallest key in it is copied up
into its parent.
A record with key value 23 is inserted into the B+
tree.
The smallest key value in the parent of the leaf that
contains 25* is ______
(Answer in integer)

Consider the following B + tree with 5 nodes, in which a
node can store at most 3 key values. The value 23 is now
inserted in the B + tree. Which of the following options(s)
is/are CORRECT?

In a B+Tree , the requirement of atleast half-full(50%)
node occupancy is relaxed for which one of the
following cases?

Consider a database implemented using B+ tree for file
indexing and installed on a disk drive with block size of 4
KB. The size of search key is 12 bytes and the size of
tree/disk pointer is 8 bytes. Assume that the database has
one million records. Also assume that no node of the B+
tree and no records are present initially in main memory.
Consider that each record fits into one disk block. The
minimum number of disk accesses required to retrieve any
record in the database is ______?

Which one of the following statements is NOT
correct  about the B+ tree data structure used for creating
an index of a relational database table?

In a B+ tree, if the search-key value is 8 bytes long, the
block size is 512 bytes and the block pointer size is 2 bytes,
then the maximum order of the B+ tree is ______.

DATABASE MANAGEMENT  SYSTEM

B+ Trees are considered BALANCED because ...

Consider a B+ tree in which the search key is 12 bytes
long, block size is 1024 bytes, recorder pointer is 10
bytes long and the block pointer is 8 bytes long. The
maximum number of keys that can be accommodated in
each non-leaf node of the tree is ______.

With reference to the B+ tree index of order 1 shown
below, the minimum number of nodes (including the
Root node) that must be fetched in order to satisfy the
following query:"Get all records with a search key
greater than or equal to 7 and less than 15" is
___________

Consider a B+-tree in which the maximum number of
keys in a node is 5. What is the minimum number of keys
in any non-root node?

The following key values are inserted into a B+-tree in
which the order of the internal nodes is 3, and that of the
leaf nodes is 2, in the sequence given below. The order of
internal nodes is the maximum number of tree pointers in
each node, and the order of leaf nodes is the maximum
number of data items that can be stored in it. The B+-tree is
initially empty.

10, 3, 6, 8, 4, 2, 1

The maximum number of times leaf nodes would get split
up as a result of these insertions is

The order of a leaf node in a B+-tree is the maximum
number of (value, data record pointer) pairs it can hold.
Given that the block size is 1K bytes, data record pointer
is 7 bytes long, the value field is 9 bytes long and a block
pointer is 6 bytes long, what is the order of the leaf
node?

Consider the B+tree in the adjoining figure, where each
node has at most two keys and three links.

Keys K'15 and then K25 are inserted into this tree in that
order. Exactly how many of the following nodes
(disregarding the links) will be present in the tree after the
two insertions?

Consider the B+tree in the adjoining figure, where each
node has at most two keys and three links.

Now the key K50 is deleted from the B+tree resulting
after the two insertions made earlier. Consider the
following statements about the B+tree resulting after this
deletion.
i. The height of the tree remains the same.
ii. The node

(disregarding the links) is present in the tree.

DATABASE MANAGEMENT  SYSTEM
iii. The root node remains unchanged (disregarding the
links).

Which one of the following options is true?

In a database file structure, the search key field is 9
bytes long, the block size is 512 bytes, a record pointer
is 7 bytes and a block pointer is 6 bytes. The largest
possible order of a non-leaf node in a B+ tree
implementing this file structure is.

Which of the following is a key factor for preferring B+-
trees to binary search trees for indexing database
relations?

Self-check

Revision card

References