About: how pages are checked

tests/sims/btree.test.ts

The automated tests for the /simulators/btree simulator. They run the model on its own, outside the browser, and compare it with a reference that doesn't depend on the model being right. They run on every change to the simulator's code.

  1. Proactive splitting gives the same tree as the CLRS algorithm after every insert and delete.
  2. B-tree and B+ tree invariants hold after random inserts and deletes, for every split setting.
// /simulators/btree
import { test } from 'node:test';
import { BTree, validate } from '../../src/lib/sims/btreeModel.ts';
import { checker, lcg } from './check.ts';

// The CLRS insert (split full nodes on the way down) and delete (make sure a child has a spare key
// before descending), written independently of the model, for comparing tree shapes step by step.
type N = { keys: number[]; children: N[]; leaf: boolean };
function clrsTree(order: number) {
	let root: N = { keys: [], children: [], leaf: true };
	const copy = (n: N): N => ({ keys: [...n.keys], children: n.children.map(copy), leaf: n.leaf });
	const lower = (arr: number[], k: number) => {
		let lo = 0, hi = arr.length;
		while (lo < hi) {
			const mid = (lo + hi) >> 1;
			if (arr[mid] < k) lo = mid + 1;
			else hi = mid;
		}
		return lo;
	};
	function splitChild(parent: N, i: number) {
		const y = parent.children[i];
		const mid = Math.floor(order / 2);
		const z: N = { keys: y.keys.slice(mid + 1), children: y.leaf ? [] : y.children.slice(mid + 1), leaf: y.leaf };
		const median = y.keys[mid];
		y.keys = y.keys.slice(0, mid);
		if (!y.leaf) y.children = y.children.slice(0, mid + 1);
		parent.children.splice(i + 1, 0, z);
		parent.keys.splice(i, 0, median);
		return median;
	}
	function insertNonFull(n: N, k: number) {
		if (n.leaf) {
			const i = lower(n.keys, k);
			if (n.keys[i] !== k) n.keys.splice(i, 0, k);
			return;
		}
		let i = lower(n.keys, k);
		if (n.children[i].keys.length >= order) {
			const median = splitChild(n, i);
			if (k > median) i++;
			else if (k === median) return;
		}
		insertNonFull(n.children[i], k);
	}
	function insert(k: number) {
		const next = copy(root);
		if (next.keys.length >= order) {
			const nr: N = { keys: [], children: [next], leaf: false };
			splitChild(nr, 0);
			insertNonFull(nr, k);
			root = nr;
		} else {
			insertNonFull(next, k);
			root = next;
		}
	}
	const minKey = (n: N) => { while (!n.leaf) n = n.children[0]; return n.keys[0]; };
	const maxKey = (n: N) => { while (!n.leaf) n = n.children[n.children.length - 1]; return n.keys[n.keys.length - 1]; };
	const minKeys = () => Math.ceil(order / 2) - 1;
	function merge(p: N, i: number) {
		const l = p.children[i], rr = p.children[i + 1];
		l.keys = [...l.keys, p.keys[i], ...rr.keys];
		if (!l.leaf) l.children = [...l.children, ...rr.children];
		p.keys.splice(i, 1);
		p.children.splice(i + 1, 1);
	}
	function ensureRich(p: N, i: number) {
		const c = p.children[i];
		if (c.keys.length > minKeys()) return;
		const l = i > 0 ? p.children[i - 1] : null;
		const rr = i < p.children.length - 1 ? p.children[i + 1] : null;
		if (l && l.keys.length > minKeys()) {
			c.keys.unshift(p.keys[i - 1]);
			p.keys[i - 1] = l.keys.pop()!;
			if (!c.leaf) c.children.unshift(l.children.pop()!);
		} else if (rr && rr.keys.length > minKeys()) {
			c.keys.push(p.keys[i]);
			p.keys[i] = rr.keys.shift()!;
			if (!c.leaf) c.children.push(rr.children.shift()!);
		} else if (l) merge(p, i - 1);
		else if (rr) merge(p, i);
	}
	function deleteFrom(n: N, k: number) {
		const i = lower(n.keys, k);
		if (i < n.keys.length && n.keys[i] === k) {
			if (n.leaf) { n.keys.splice(i, 1); return; }
			const l = n.children[i], rr = n.children[i + 1];
			if (l.keys.length > minKeys()) { const pred = maxKey(l); deleteFrom(l, pred); n.keys[i] = pred; }
			else if (rr.keys.length > minKeys()) { const succ = minKey(rr); deleteFrom(rr, succ); n.keys[i] = succ; }
			else { merge(n, i); deleteFrom(n.children[i], k); }
			return;
		}
		if (n.leaf) return;
		ensureRich(n, i);
		deleteFrom(n.children[lower(n.keys, k)], k);
	}
	function del(k: number) {
		const next = copy(root);
		deleteFrom(next, k);
		root = !next.leaf && next.keys.length === 0 ? next.children[0] : next;
	}
	const shape = (n: N): unknown => (n.leaf ? n.keys : [n.keys, n.children.map(shape)]);
	return { insert, del, shape: () => JSON.stringify(shape(root)) };
}

const shapeOf = (t: BTree) => {
	const w = (n: { leaf: boolean; keys: number[]; children: unknown[] }): unknown => (n.leaf ? n.keys : [n.keys, n.children.map((c) => w(c as never))]);
	return JSON.stringify(w(t.root as never));
};

test('proactive splitting gives the same tree as the CLRS algorithm after every insert and delete', () => {
	const { ok, done } = checker();
	const r = lcg(9);
	for (const order of [3, 4, 5, 7]) for (let trial = 0; trial < 200; trial++) {
		const ref = clrsTree(order);
		const t = new BTree({ variant: 'b', maxKeys: order, split: 'proactive', bias: 'left' });
		const present = new Set<number>();
		for (let i = 0; i < 60; i++) {
			const k = Math.floor(r() * 80);
			if (r() < 0.3) {
				if (!present.has(k)) continue;
				ref.del(k); t.delete(k); present.delete(k);
			} else {
				if (present.has(k)) continue;
				ref.insert(k); t.insert(k); present.add(k);
			}
			ok(ref.shape() === shapeOf(t), `order ${order}: ${ref.shape()} vs ${shapeOf(t)}`);
		}
	}
	done();
});

test('B-tree and B+ tree invariants hold after random inserts and deletes, for every split setting', () => {
	const { ok, done } = checker();
	const r = lcg(10);
	for (const variant of ['b', 'bplus'] as const) for (const maxKeys of [2, 3, 4, 5, 6]) for (const bias of ['left', 'right'] as const) for (let trial = 0; trial < 60; trial++) {
		const t = new BTree({ variant, maxKeys, split: 'overflow', bias });
		const set = new Set<number>();
		for (let i = 0; i < 120; i++) {
			const k = Math.floor(r() * 150);
			if (r() < 0.4 && set.size) {
				const arr = [...set];
				const x = arr[Math.floor(r() * arr.length)];
				ok(t.delete(x), 'delete of a present key failed');
				set.delete(x);
			} else {
				t.insert(k);
				set.add(k);
			}
			const v = validate(t);
			ok(!v.length, `${variant} max ${maxKeys} ${bias}: ${v.join('; ')}`);
			ok(t.keys().join() === [...set].sort((a, b) => a - b).join(), `${variant} keys out of order or missing`);
		}
		for (const k of set) ok(t.has(k), 'present key not found');
		for (let k = 150; k < 160; k++) ok(!t.has(k), 'absent key found');
	}
	done();
});

Shared helpers: tests/sims/check.ts. The model under test is imported from src/lib/sims/.

Published