B-tree and B+ tree — motivation (disk storage), properties: Question bank

Before we start, a shared vocabulary reminder so no symbol appears un-earned on this page:

$t$ = the minimum degree. A node may hold between $t - 1$ and $2 t - 1$ keys.
$N$ = the total number of keys stored across the whole tree (e.g. a billion records → $N = 1 0^{9}$ ).
$h$ = the height of the tree: the number of levels you must descend from the root to a leaf. Height 4 means a lookup touches 4 nodes = 4 disk reads.
$k$ = the number of keys currently in one particular node.
A block / page = the chunk of bytes a disk hands you in one physical read. One node = one block.
A seek = the slow mechanical (or logical) act of jumping to a new block on disk.
Fanout = how many children a node points at; more fanout = fatter, shorter tree.

Two figures on this page make the moving parts visual — refer to them as you answer.

Figure A — the fat, short shape and a node's key/child layout:

Figure B — a node split (insert overflow) and a sibling borrow (delete underflow):

The height bound — where $h \leq lo g_{t} \frac{N + 1}{2}$ comes from

Intuition Why this formula, and why it's the

worst case WHAT we want: a promise that the tree is short, i.e. an upper limit on $h$ . HOW to get it: to make $h$ as large as possible for a given $N$ , make every node as empty as the rules allow — that spreads few keys over many levels. So we assume every non-root node holds its minimum $t - 1$ keys (invariant 2) and has its minimum $t$ children.

The count (look at Figure A's level-by-level fan-out): the root has $\geq 1$ key → $\geq 2$ children. Every deeper node has $\geq t$ children, so node counts per level are $1, 2, 2 t, 2 t^{2}, \dots, 2 t^{h - 1}$ . Each non-root node carries $\geq t - 1$ keys, giving $N \geq 1 + (t - 1) \sum_{i = 1}^{h} 2 t^{i - 1} = 1 + 2 (t - 1) \frac{t ^{h} - 1}{t - 1} = 2 t^{h} - 1.$ Rearranging $N \geq 2 t^{h} - 1$ gives $t^{h} \leq \frac{N + 1}{2}$ , so $h \leq lo g_{t} \frac{N + 1}{2}$ . Because we used the minimum fill everywhere, this is the tallest the tree can ever be. Real trees are usually shorter. That is the whole payoff: logarithm in a huge base $t$ → tiny height.

True or false — justify

The bottleneck in disk-based search is the number of key comparisons the CPU does.

False. The CPU is fast; comparing 500 sorted keys inside a block is essentially free. The bottleneck is the number of block reads, because each read costs a slow seek. We minimise reads, not comparisons.

A balanced BST and a B-tree both have logarithmic height, so they perform equally on disk.

False. Both are logarithmic, but the base differs: BST is

lo g_{2} N

, B-tree is

lo g_{t} N

with

t

in the hundreds. Base 2 gives ~30 levels for a billion keys; base 500 gives ~4. Same big-O family, wildly different constant that decides real disk cost.

All leaves of a B-tree are at the same depth.

True. This is invariant 6, and it is forced by the "grow-from-the-top" split rule: height

h

only increases by splitting the root, which lifts every leaf by one level simultaneously.

The root of a B-tree must hold at least

t - 1

keys like every other node.

False. Invariant 3 exempts the root; it may hold just 1 key. Without this exemption a tiny tree of one or two keys couldn't legally exist.

In a B+ tree, if your search key equals a separator in an internal node, you can stop and return.

False. Internal separators are pure routers — the actual record lives only in a leaf. You must descend all the way to the leaf even when a separator matches exactly.

In a plain B-tree, a search can end at any node, not just a leaf.

True. B-tree internal nodes store real data, so a match can terminate at the root, an internal node, or a leaf — wherever the key sits.

Making

t

as large as possible always makes lookups faster.

False. Fanout helps only until one node exceeds one disk block. Beyond that, reading a single node costs multiple I/Os, which destroys the "one node = one read" guarantee. Optimal

t

fills exactly one block.

A B+ tree is always at least as short as the equivalent B-tree.

True. B+ internal nodes carry only keys and pointers (no data payload), so they pack more separators per block → higher fanout → equal or lower height

h

for the same

N

Range queries are equally fast in a B-tree and a B+ tree.

False. B+ trees link the leaves into a sorted list, so a range scan descends once then walks sideways. A B-tree has no leaf links and must do repeated in-order root-to-leaf traversals — much more seeking.

A B-tree with minimum degree

t = 2

is essentially a balanced binary tree.

False. With

t = 2

a node holds 1–3 keys and up to 4 children, so it is a 2-3-4 tree, not binary. It is

m

-ary with

m = 4

; the whole family is designed to escape binary branching.

On an SSD, B-trees give no benefit because there is no mechanical seek.

False. SSDs still read in whole blocks and a random read is still ~1000× slower than RAM. "Minimise block reads" logic is unchanged; only the constant per read shrinks.

The height bound

h \leq lo g_{t} \frac{N + 1}{2}

describes the best case (shortest tree).

False. It is the worst case (tallest tree). It was derived by assuming every node is minimally filled, which maximises

h

for a given

N

Spot the error

"A node with 5 keys has 5 children."

Wrong — by invariant 4 a node with

k

keys has exactly

k + 1

children. The keys are separators between subtrees, so 5 keys create 6 gaps. Correct answer: 6 children.

"For

t = 3

, a node may hold between 3 and 6 keys."

Wrong bounds. Range is

t - 1

2 t - 1

, i.e. 2 to 5 keys. The writer confused

t

with the minimum key count.

"B-trees grow by adding new leaves at the bottom, so leaf depths can differ."

Wrong on both counts. B-trees grow upward by splitting a full root; that lifts all leaves equally, so depths never differ (invariant 6).

"We split a full node only after descending into it and finding no room."

Wrong strategy for the standard top-down insert: we split a full node before descending into it (see Figure B). This guarantees the parent always has room to receive the pushed-up median, avoiding cascading fix-ups.

"Since internal B+ nodes hold no data, they store nothing useful."

Wrong — they store separator keys and child pointers, which are exactly the routing information that steers a search toward the correct leaf. They're the map, not the destination.

"Choosing node size is a pure CPU/cache-tuning decision."

Wrong — node size is dictated by the disk block size. The hardware's I/O granularity, not the CPU cache, sets the branching factor.

"A separator key that appears in an internal node cannot also appear in a leaf."

Wrong for B+ trees — a router key is a copy; the real key/record also lives in a leaf. Duplication between routers and leaves is normal and expected.

"After deleting a key, a node that drops to

t - 2

keys is still legal."

Wrong —

t - 2

is below the half-full floor (invariant 2). This is underflow and must be repaired by borrowing from a sibling or merging (see the Edge cases section and Figure B).

Why questions

Why do we force every non-root node to be at least half full (

\geq t - 1

keys)?

To keep fanout high and height

h

low. If nodes could be nearly empty the tree could grow tall, wasting disk reads. The half-full floor caps the worst-case height — it is the exact assumption used to derive

h \leq lo g_{t} \frac{N + 1}{2}

Why does reading 1 key cost the same as reading 200 keys from the same node?

Because the disk delivers a whole block per read regardless of how much of it you use. Once the block is in RAM, scanning its keys is free CPU work.

Why do databases and filesystems prefer B+ trees over plain B-trees?

Two reasons: (1) data-free internal nodes give higher fanout and shorter trees, and (2) linked leaves make range and sequential scans fast — exactly the access pattern queries like BETWEEN need. See Database Indexing and File Systems.

Why is the height bound logarithmic in base

t

rather than base 2?

Because each level multiplies the node count by (at least)

t

, not 2. High branching factor is the entire mechanism that collapses 30 levels down to ~4.

Why can't we just cache the whole disk index in RAM and skip B-trees?

For a billion+ keys the index is far larger than RAM. The tree must live on disk, so the design goal is minimising slow block reads, not eliminating disk. See Disk and Memory Hierarchy.

Why does the "grow from the top" rule keep all leaves at equal depth automatically?

Because the only operation that increases

h

is splitting the root, which inserts one new level above everything at once. No individual leaf ever gets deeper than its siblings.

Why does deletion first try to borrow from a sibling before it merges?

Borrowing keeps two nodes alive and half-full with a cheap key shuffle; merging destroys a node and shrinks the tree. We prefer the local, cheaper fix, and only merge when the sibling is itself at the minimum and has nothing to lend.

Edge cases

An empty B-tree — is the root rule violated?

No. Invariant 3 says the root has

\geq 1

key unless the tree is empty. Emptiness is the explicit exception.

A B-tree with a single key — legal?

Yes. The root alone holds 1 key and has no children. Because the root is exempt from the minimum-fill rule (invariant 3), this is the smallest legal tree.

You insert into a node that already has

2 t - 1

keys — what happens first?

It must split before the key can be placed (Figure B, left): the median moves up to the parent and the node breaks into two half-full nodes, restoring the

\leq 2 t - 1

limit (invariant 1).

What if a split pushes a median up into a root that is itself full?

The root splits too, creating a brand-new root above it — this is the one moment

h

increases, and it lifts every leaf by one level, preserving invariant 6.

You delete a key and a non-root node drops below

t - 1

keys — what must happen?

This is underflow, a violation of invariant 2. You repair it by borrowing a key from an adjacent sibling (through the parent separator) if that sibling has more than

t - 1

keys; the parent separator rotates down and a sibling key rotates up (Figure B, right).

What if both neighbouring siblings are already at the minimum

t - 1

keys, so nobody can lend?

You merge: the underflowing node, the parent's separator key, and a sibling combine into one node of

2 t - 1

keys. This removes a key from the parent, which may then underflow too — the fix can cascade upward.

Can a delete-time merge shrink the tree's height?

Yes. If a merge empties the root (its last separator was pulled down into the merged child), the merged child becomes the new root and

h

decreases by 1 — the mirror image of a root split. All leaves rise together, so invariant 6 holds.

When deleting a key that sits in an internal B-tree node, why can't we just erase it in place?

Erasing would leave a subtree with no separator between two children (breaking invariant 5). Instead we replace it with its in-order predecessor or successor (the rightmost/leftmost key of a neighbouring subtree), then delete that key from the leaf, which is the simple case.

In a B+ tree, does deleting a leaf key ever change an internal separator?

It can. If the deleted key was also being used as a router copy and it was the leaf's boundary key, the internal separator is updated to the new boundary. The record only ever left a leaf, but the routing map must stay accurate.

For

t = 2

, what is the maximum number of children per node, and why does it matter for testing?

Max children

= 2 t = 4

(max keys

= 2 t - 1 = 3

). It matters because

t = 2

is the smallest legal degree, so it exercises every split/merge/borrow edge case with tiny, hand-checkable nodes.

The disk block is smaller than one full node — is that allowed?

It defeats the purpose. Reading such a node needs multiple I/Os, breaking "one node = one read". The whole design assumes node size

\leq

block size, ideally equal.

A range query in a B+ tree where the whole range fits in one leaf — do we still touch the linked list?

No sideways walk is needed; we descend to that leaf and read the range in place. The leaf-link walk only kicks in when the range spills past a leaf's boundary.

Recall One-line self-test before you leave

Cover the answers and re-explain: why comparisons don't matter, why the root is special, why B+ leaves are linked, why $t$ is capped by block size, and how borrow-vs-merge repairs underflow after a delete. If all five flow easily, you own this topic.