b-tree-index-from-scratch

A disk-style B-Tree index implemented from scratch in TypeScript with a clean CLI for inserts, deletes, searches, level-order visualization, and Graphviz export. This is the core indexing structure databases use to keep lookups logarithmic even when data outgrows memory.

Why a B-Tree?

• Models how real database indexes stay balanced on disk: every node holds a key range (t‒1..2t‒1 keys) to minimize height.
• Demonstrates non-trivial algorithms: split/merge, borrow/redistribute, predecessor/successor replacement, and invariant preservation.
• Perfect for FAANG-style interviews: shows you know when to use branching factors over binary trees to optimize IO.

Features

• Full B-Tree operations: search, insert (with node splitting), delete (borrow/merge), and in-order traversal.
• Interactive REPL (npm start) + script mode (--script commands.txt) for reproducible scenarios.
• Graphviz export (export tree.dot) to visualize the current structure.
• ASCII level renderer for quick console inspection.
• Zero runtime deps beyond Node; strict TypeScript with tests using the built-in node:test runner.

Architecture

• src/core/BTree.ts — Pure data structure implementation (no IO).
• src/lib/visualize.ts — Helpers for ASCII level rendering and stats formatting.
• src/cli/index.ts — REPL + script runner that wires the tree to the console.
• src/tests/btree.test.ts — Edge-case coverage for split/merge, search, and Graphviz output.

The B-Tree maintains the invariant that each non-root node stores t-1 .. 2t-1 keys (here t = minDegree). Height is O(log_t n), and every operation touches at most one node per level, which is why B-Trees dominate on-page/disk layouts.

Quickstart

npm install
npm run build
npm start -- --degree 3 --key-type number

CLI Commands

• insert <k1> [k2 ...] — Insert one or many keys (duplicates are ignored).
• delete <k1> [k2 ...] — Remove keys if present.
• find <k> — Membership test.
• levels / print — ASCII level-order view.
• array — In-order keys.
• stats — Size, height, and node key bounds.
• export [file] — Write Graphviz .dot to a file (default btree.dot).
• reset — Start with a fresh empty tree.
• quit — Exit the REPL.

Demo

$ npm start -- --degree 3 --key-type number
B-Tree (minDegree=3, keyType=number)
bti> insert 10 20 5 6 12 30 7 17
added 8: 10, 20, 5, 6, 12, 30, 7, 17
bti> levels
L0  [10]
L1  [5 6 7]  [12 17 20 30]
bti> delete 6 12
removed 2: 6, 12
bti> levels
L0  [10]
L1  [5 7]  [17 20 30]
bti> export docs/demo.dot
Graphviz saved to /Users/mo/Downloads/b-tree-index-from-scratch/docs/demo.dot

Data-structure choices

• B-Tree over AVL/Red-Black: higher branching factor reduces height → fewer disk/page fetches; ideal for index-like workloads.
• Borrow/merge deletion keeps nodes ≥ t-1 keys, demonstrating careful invariant maintenance rather than lazy tombstones.
• Graphviz export + ASCII levels make the balancing behavior auditable.

Complexity

• Search / insert / delete: O(log_t n)
• Traversal: O(n)
• Space: O(n)

Testing

npm test

Uses Node's built-in node:test (no extra dependencies).

Author

Mo Shirmohammadi — GitHub · CS @ USC

License

MIT — see LICENSE for details.