jsschools

B-Tree

A self-balancing multi-way search tree where nodes can hold multiple keys and children, designed to minimise disk I/O by keeping the tree shallow.

Spec ↗

Syntax

// A B-Tree of order t (minimum degree):
// - Every non-root node has ≥ t-1 and ≤ 2t-1 keys.
// - Every non-leaf node with k keys has k+1 children.
// - All leaves are at the same depth.
class BTreeNode { constructor(leaf) { this.keys=[]; this.children=[]; this.leaf=leaf; } }

Parameters

NameTypeRequiredDescription
t number Yes Minimum degree (order) of the B-Tree. Each node holds between t-1 and 2t-1 keys. t=2 gives a 2-3-4 tree.

Returns

BTree — A new B-Tree instance of the given minimum degree.

Examples

// Conceptual search in a B-Tree node
function search(node, key) {
  let i = 0;
  while (i < node.keys.length && key > node.keys[i]) i++;
  if (i < node.keys.length && key === node.keys[i]) return { node, i };
  if (node.leaf) return null;
  return search(node.children[i], key);
}

// Demonstration (3-node B-Tree of order 2, i.e., 2-3-4 tree)
const root = {
  keys: [10, 20],
  leaf: false,
  children: [
    { keys: [5],     leaf: true, children: [] },
    { keys: [15],    leaf: true, children: [] },
    { keys: [25, 30],leaf: true, children: [] },
  ]
};
const found = search(root, 15);
console.log(found ? `found at index ${found.i}` : 'not found');
console.log(search(root, 99));
Output 
found at index 0
null

// B-Trees are used in databases and file systems.
// SQLite uses a variant called B+ tree where all data rows
// are stored only in leaf nodes (internal nodes hold only keys).
console.log('B-Tree height for n=1,000,000, t=500:',
  Math.ceil(Math.log(1_000_000) / Math.log(500)));
Output 
B-Tree height for n=1,000,000, t=500: 4

Notes

| Operation | Time | Space | |----------|-------------|-------| | Search | O(log n) | O(t) | | Insert | O(t log n) | O(t log n) | | Delete | O(t log n) | O(t log n) | n = number of keys; t = minimum degree (branching factor). A tree of height h holds between t^h − 1 and (2t)^h − 1 keys, so h = O(log_t n). With t=500 a million-key tree has height ≤ 4, meaning at most 4 disk reads per lookup. B+ trees (used in most RDBMS and file systems) store data only at leaves, enabling efficient range scans via linked leaf nodes.

See also