Explain database indexing and B-trees

// A small B+tree: every node is a "page" holding at most MAX keys.
// Leaves hold the keys (and would hold row pointers); internal nodes hold separators.
function newNode(leaf) { return { leaf, keys: [], kids: [], next: null }; }

function insert(node, key, max) {
  // Returns null, or [separator, newRightNode] when this node split.
  let i = 0;
  while (i < node.keys.length && node.keys[i] < key) i++;
  if (node.leaf) {
    node.keys.splice(i, 0, key);
  } else {
    if (i < node.keys.length && node.keys[i] === key) i++;
    const split = insert(node.kids[i], key, max);
    if (split === null) return null;
    node.keys.splice(i, 0, split[0]);
    node.kids.splice(i + 1, 0, split[1]);
  }
  if (node.keys.length <= max) return null;
  const mid = Math.floor(node.keys.length / 2);
  const right = newNode(node.leaf);
  if (node.leaf) {
    right.keys = node.keys.slice(mid);
    node.keys = node.keys.slice(0, mid);
    right.next = node.next;
    node.next = right;
    return [right.keys[0], right];
  }
  const sep = node.keys[mid];
  right.keys = node.keys.slice(mid + 1);
  right.kids = node.kids.slice(mid + 1);
  node.keys = node.keys.slice(0, mid);
  node.kids = node.kids.slice(0, mid + 1);
  return [sep, right];
}

function build(keys, max) {
  let root = newNode(true);
  for (const k of keys) {
    const split = insert(root, k, max);
    if (split !== null) {
      const r = newNode(false);
      r.keys = [split[0]];
      r.kids = [root, split[1]];
      root = r;
    }
  }
  return root;
}

function stats(root, max) {
  let height = 0, internal = 0, leaves = 0, leafKeys = 0;
  let level = [root];
  while (level.length > 0) {
    height++;
    const nextLevel = [];
    for (const n of level) {
      if (n.leaf) { leaves++; leafKeys += n.keys.length; } else { internal++; nextLevel.push(...n.kids); }
    }
    level = nextLevel;
  }
  const fill = Math.floor((leafKeys * 100) / (leaves * max));
  return `height=${height} internal=${internal} leaves=${leaves} leaf_fill=${fill}%`;
}

function descend(root, key) {
  let node = root, pages = 1;
  while (!node.leaf) {
    let i = 0;
    while (i < node.keys.length && key >= node.keys[i]) i++;
    node = node.kids[i];
    pages++;
  }
  return [node, pages];
}

function lookup(root, key) {
  const [leaf, pages] = descend(root, key);
  return `lookup ${key}: found=${leaf.keys.includes(key)} pages_read=${pages}`;
}

function range(root, lo, hi) {
  let [leaf, pages] = descend(root, lo);
  let rows = 0;
  while (leaf !== null) {
    let past = false;
    for (const k of leaf.keys) {
      if (k > hi) { past = true; break; }
      if (k >= lo) rows++;
    }
    if (past || leaf.next === null) break;
    leaf = leaf.next;
    pages++;
  }
  return `range ${lo}..${hi}: rows=${rows} pages_read=${pages}`;
}

function firstKeys(root, n) {
  let node = root;
  while (!node.leaf) node = node.kids[0];
  const out = [];
  while (node !== null && out.length < n) { for (const k of node.keys) if (out.length < n) out.push(k); node = node.next; }
  return out.join(",");
}

const N = 10007; // prime, so (i * 7919) % N visits every key 0..N-1 once, in scrambled order
const scrambled = [];
for (let i = 0; i < N; i++) scrambled.push((i * 7919) % N);
const sequential = [];
for (let i = 0; i < N; i++) sequential.push(i);

for (const max of [4, 64]) {
  const t = build(scrambled, max);
  console.log(`B+tree, ${N} keys inserted in scrambled order, max ${max} keys per page`);
  console.log("  " + stats(t, max));
  console.log("  " + lookup(t, 4242));
  console.log("  " + lookup(t, 20000));
  console.log("  " + range(t, 5000, 5049));
  console.log("  ORDER BY key LIMIT 5, walked from the leftmost leaf: " + firstKeys(t, 5));
}
console.log(`Full table scan for the same lookup: rows_read=${N}`);

const seq = build(sequential, 64);
console.log("Sequential inserts (like an auto-increment id), max 64 keys per page");
console.log("  " + stats(seq, 64));

console.log("Levels needed for 1,000,000,000 keys (fan-out ^ levels >= keys)");
for (const fanout of [4, 64, 400]) {
  let levels = 0, reach = 1;
  while (reach < 1000000000) { reach *= fanout; levels++; }
  console.log(`  fan-out ${fanout}: ${levels} levels`);
}