B-Tree - Algorithms - ggcoder.com

Overview

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, insertions, and deletions in O(log n) time. Unlike binary trees, B-Trees can have many children per node, making them ideal for systems that read and write large blocks of data like databases and file systems.

Info

B-Trees minimize disk I/O by storing many keys per node. A single disk read can fetch an entire node with hundreds of keys, drastically reducing the number of reads needed compared to binary trees.

Complexity Analysis

Operation	Average	Worst	Disk I/O
Search	O(log n)	O(log n)	O(log_m n)
Insert	O(log n)	O(log n)	O(log_m n)
Delete	O(log n)	O(log n)	O(log_m n)
Range Query	O(log n + k)	O(log n + k)	O(log_m n + k/m)
Space	O(n) - each key stored once

n = number of keys, m = order (max children), k = number of results in range

B-Tree Properties

A B-Tree of order m (maximum children per node) has specific rules that keep it balanced and efficient for disk-based storage.

Every node has at most m children
Every non-leaf node (except root) has at least ⌈m/2⌉ children
Root has at least 2 children if it is not a leaf
All leaves appear at the same depth
A non-leaf node with k children contains k-1 keys

Structure Visualization

Search Operation

Searching in a B-Tree is similar to a binary search tree, but at each node you binary search among multiple keys to find which child to follow.

Step-by-Step Search

B-Tree Search

1function search(node: BTreeNode, key: number): Data | null {2  // Binary search within node's keys3  let i = 0;4  while (i < node.keys.length && key > node.keys[i]) {5    i++;6  }78  // Found exact match9  if (i < node.keys.length && key === node.keys[i]) {10    return node.data[i];11  }1213  // Reached a leaf without finding14  if (node.isLeaf) {15    return null;16  }1718  // Recurse into appropriate child19  return search(node.children[i], key);20}

Insertion

Insertion always happens at a leaf. If the leaf overflows (more than m-1 keys), it splits into two nodes and the middle key moves up to the parent. This split can cascade up to the root.

Step-by-Step Insertion with Split

Split Algorithm

B-Tree Split

1function split(node: BTreeNode): { left: BTreeNode; mid: number; right: BTreeNode } {2  const midIndex = Math.floor(node.keys.length / 2);3  const midKey = node.keys[midIndex];45  const left = new BTreeNode();6  left.keys = node.keys.slice(0, midIndex);7  left.children = node.children.slice(0, midIndex + 1);89  const right = new BTreeNode();10  right.keys = node.keys.slice(midIndex + 1);11  right.children = node.children.slice(midIndex + 1);12

Deletion

Deletion is more complex. If deleting from a leaf causes underflow (fewer than ⌈m/2⌉-1 keys), the node must borrow from a sibling or merge with it.

Deletion Scenarios

Leaf with enough keys: simply remove
Leaf underflow + sibling has extra: borrow through parent
Leaf underflow + sibling minimal: merge with sibling and parent key
Internal node: replace with predecessor/successor, then handle leaf

Warning

When two nodes merge, the parent loses a key. This can cause the parent to underflow, propagating the fix up the tree. In the worst case, the tree height decreases by 1.

B-Tree vs B+ Tree

B+ Trees are a variant where all data is stored in leaves and internal nodes only contain keys for navigation. Leaves are linked for efficient range queries.

B-Tree: Data in all nodes | B+ Tree: Data only in leaves
B-Tree: Fewer keys per level | B+ Tree: More keys (internal nodes smaller)
B-Tree: No leaf links | B+ Tree: Leaves linked for range scans

Disk I/O Optimization

B-Trees are designed for systems where disk reads are expensive. By fitting hundreds of keys in each node, a B-Tree with millions of records may only be 3-4 levels deep.

Concrete Example

With a B-Tree of order 500: each node holds up to 499 keys. With 1 million records, the tree only needs 3 levels. Each search requires only 3 disk reads instead of 20 with a binary tree.

Tip

Database systems typically size B-Tree nodes to match the disk block size (4KB-16KB). This ensures each disk read fetches exactly one complete node, maximizing efficiency.

Common Pitfalls

Choosing too small an order: Tree becomes deeper, more disk I/O
Choosing too large an order: Binary search within node slows down, wastes space
Forgetting cascading splits: Node splits can propagate to root
Forgetting cascading merges: Merges during deletion can also propagate up
Not considering B+ Tree for range queries: B+ Tree is better for range scans
Ignoring caching: Root and frequently accessed nodes should be cached

Performance Characteristics

Strengths

Optimized for disk-based storage with large block I/O
Low tree height even with billions of records
Consistent O(log n) search, insert, delete performance
Cache-friendly due to spatial locality
Self-balancing, no manual rebalancing needed

Weaknesses

More complex than BST for in-memory implementation
Higher overhead for small datasets
Split/merge operations have significant cost
Space utilization not optimal (nodes can be half empty)

Real-World Usage

MySQL InnoDB: B+ Tree indexes for primary and secondary keys
PostgreSQL: B-Tree is the default index type
SQLite: B-Tree for tables, B+ Tree for indexes
NTFS / ext4: File system directory indexing
MongoDB: B-Tree indexes (WiredTiger engine)
Oracle Database: B* Tree (variant with smarter splits)
CouchDB: B+ Tree for views and indexes
Btrfs: B-Tree filesystem for Linux

Tip

When designing database systems, consider: (1) Disk block size to choose optimal order, (2) Read/write ratio to decide B-Tree vs B+ Tree, (3) Most common query type (point vs range).