B-Tree and B+Tree Search

Definition & structure

B-Tree: multiway balanced search tree used in DBs and filesystems.
B+Tree: variant where all keys live in leaves (linked), great for range scans.

B-tree / B+ tree search demo

This placeholder can be extended with a visualisation of the B-tree / B+ tree structure and how a search walks through it.

  • Multi-way balanced tree structure
  • Node splitting and merging
  • Range search demo

B-Tree traits

  • Up to mm children per node (order mm)
  • Root has at least 2 children (unless single-node tree)
  • Non-root nodes have ⌈m/2⌉\lceil m/2 \rceil or more children
  • Keys in-node are ascending; subtrees are ordered intervals

B+Tree traits

  • All keys in leaves, leaves linked
  • Internal nodes store only indexes
  • Optimized for range queries

Search process

  1. From root, sequentially search keys in node
  2. If found, success
  3. Else follow child pointer
  4. Repeat until leaf or success

B+Tree search similar, but always ends at leaves.

Insertion (Using a 3-Order B-Tree as an Example)

  1. Starting from the root, follow the search path down to the leaf node where the key belongs
  2. Insert the key into the leaf node in key order
  3. Split: if the node then holds more than m−1m-1 keys (2 for a 3-order B-Tree), split it into two nodes and move the middle key up into the parent
  4. If the parent overflows as well, keep splitting upwards until the root is reached (the tree grows by one level)

Deletion

After a key is deleted, if the node holds fewer than ⌈m/2⌉−1\lceil m/2 \rceil - 1 keys, it has to be rebalanced:

  • Borrowing: if a sibling has a spare key, borrow one from it (through the parent)
  • Merging: if the sibling is short of keys as well, merge the node with the sibling and move the matching key of the parent down
  • If the parent becomes short after that move, keep adjusting upwards; if the root is merged away, the height of the tree decreases by one

B-Tree vs B+ Tree

AspectB-TreeB+ Tree
Where the keys liveSpread over all nodesAll concentrated in the leaves
Internal nodesStore keys and dataStore index information only
Leaf nodesNot connectedLinked together by pointers
SearchStops at the hitAlways goes down to the leaves
Range searchIn-order traversalScans the linked list in order, which is efficient
Typical useGeneral indexesRange queries in databases and filesystems

When to use

  • Large on-disk data; DB indexes
  • Heavy range queries (B+Tree)

Algorithm (pseudo)

node = root
while node != null:
    sequentially search the keys inside the node for x
    if found:
        return position
    else:
        follow child pointer
return -1

Complexity

  • Search: O(log⁡mn)O(\log_m n) where mm is order, nn keys
  • B+Tree similar, better for range scan

Exercises

Exercise 1

Differences between B-Tree and B+Tree? Scenarios?

B-TreeB+ TreeRange Query

Approach: Compare the structures and the scenarios they suit.

Steps:

  1. B-Tree keys across all nodes; B+Tree keys only in leaves
  2. B+Tree leaves linked—range-friendly

Answer: B-Tree serves general lookups; B+Tree is good at range searches.

Exercise 2

In a 4-way B-Tree, min children of non-root?

B-TreeTree OrderMinimum Children

Approach: The order of the tree and the number of children per node.

Steps:

  1. A non-root node has at least ⌈m/2⌉\lceil m/2 \rceil children
  2. With m=4m=4, that gives 2

Answer: 2 children.

Past exam

2019·408

Which of the following statements about B-trees is incorrect?

B-TreeNode PropertiesRoot Node

Approach: Check the properties one by one.

Steps:

  1. (A) correct; (B) correct
  2. (C) wrong: the root may have only 1 child (a special case)
  3. (D) not enough information, the height cannot be determined

Answer: (C) is wrong. The root may have 1 child.

Found an issue with this content?

Tell us what could be improved.