$sloprun.dev

B-Tree Visualizer

demo sandbox: allow-scripts · csp: default-src 'none'

sandboxed and isolated in your browser · never enter a real password in a demo

▶ 7 ran · ✓ 0 worked
i ran it — no login needed:
share: preview embed ↗
post it anywhere:
email the card:

0 reported it broke · the ▶ count is distinct visitors who ran it, counted once each, anonymously

Every index in Postgres, SQLite, and MySQL is a B-tree, and this is one you can poke at: an order-4 tree drawn as SVG, preloaded with 12 keys, narrating each step in mono as it goes — 45 → reached leaf [41 43 50] → leaf [41 43 45 50] holds 4 keys > 3 → split → median 43 promoted → parent now [43 64 78]. The part textbooks gloss over is that split: an overfull node doesn't grow, it breaks in half and shoves its middle key up to the parent, which is exactly why the tree stays three levels deep instead of degenerating into a linked list. Insert 43, then 45, to watch one leaf fill up and burst — or hit Autoplay and let it churn through random keys at whatever speed you like. Deletes are the harder half and they're here too: take enough keys out of a node and it borrows from a sibling, or merges with one and pulls a key down from the parent, until the whole tree loses a level.

Embed this demo — put a runnable demo in your blog post

Paste this where you write. It renders a live, runnable demo inline anywhere raw HTML / iframes are allowed — Ghost, WordPress, Notion, Discourse, your own site.

<iframe src="https://sloprun.dev/embed/btree" width="100%" height="640" loading="lazy" allow="" style="border:1px solid #E3E2DC;border-radius:10px" title="B-Tree Visualizer — a runnable demo on sloprun.dev"></iframe>
preview ↗

On Medium and dev.to the plain link becomes a rich preview card that links back here — they don't run third-party iframes, so paste the URL there and the reader clicks through to run it. https://sloprun.dev/p/btree

Source

the code you see is the code that just ran raw ↗
Source — the code you see is the code that just ran 979 lines 40.2 KB index.html
demos/btree/index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>B-Tree Visualizer</title>
<style>
/* sloprun design tokens — inline this block into every demo (self-contained rule).
   Identity: instrument-panel. Machine facts in mono; human words in sans.
   Green is EARNED: only for "it ran / it worked" states, never decoration. */
:root {
  --bg: #F6F6F3;          /* neutral paper, not cream */
  --surface: #FFFFFF;
  --ink: #1A1D21;
  --muted: #5A6068;
  --line: #E3E2DC;
  --accent: #C05600;      /* phosphor amber, darkened for light bg */
  --accent-soft: #FFF3E6;
  --run: #1A7F37;         /* earned green */
  --run-soft: #E7F4EA;
  --danger: #C93C37;
  --radius: 10px;
  --font-sans: system-ui, -apple-system, "Segoe UI", sans-serif;
  --font-mono: ui-monospace, "SF Mono", "Cascadia Code", Menlo, Consolas, monospace;
}
@media (prefers-color-scheme: dark) {
  :root:not([data-theme="light"]) {
    --bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
    --line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
    --run: #3FB950; --run-soft: #16281B; --danger: #F47067;
  }
}
:root[data-theme="dark"] {
  --bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
  --line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
  --run: #3FB950; --run-soft: #16281B; --danger: #F47067;
}
body { background: var(--bg); color: var(--ink); font-family: var(--font-sans); }

/* --- demo-local supplements (derived, same three theme states) --- */
:root { --danger-soft: #FCEBEA; --canvas: #FBFBF8; --shadow: 0 1px 2px rgba(20,22,26,.05); }
@media (prefers-color-scheme: dark) {
  :root:not([data-theme="light"]) { --danger-soft: #2B1A18; --canvas: #171A20; --shadow: 0 1px 2px rgba(0,0,0,.3); }
}
:root[data-theme="dark"] { --danger-soft: #2B1A18; --canvas: #171A20; --shadow: 0 1px 2px rgba(0,0,0,.3); }

* { box-sizing: border-box; }
html, body { margin: 0; padding: 0; }
body { -webkit-text-size-adjust: 100%; line-height: 1.45; overflow-x: hidden; }

.wrap { max-width: 1000px; margin: 0 auto; padding: 22px 16px 30px; }

header h1 { font-size: 21px; margin: 0 0 4px; letter-spacing: -.01em; }
header p.lede { margin: 0; color: var(--muted); font-size: 14.5px; max-width: 62ch; }
.chip {
  display: inline-block; font-family: var(--font-mono); font-size: 10.5px; letter-spacing: .06em;
  text-transform: uppercase; color: var(--accent); background: var(--accent-soft);
  border: 1px solid var(--line); border-radius: 999px; padding: 3px 9px; margin-bottom: 10px;
}

.panel {
  margin-top: 16px; background: var(--surface); border: 1px solid var(--line);
  border-radius: var(--radius); box-shadow: var(--shadow); overflow: hidden;
}

/* controls */
.controls {
  display: flex; flex-wrap: wrap; gap: 8px; align-items: center;
  padding: 12px; border-bottom: 1px solid var(--line);
}
.field { display: flex; align-items: center; gap: 6px; }
.field label { font-family: var(--font-mono); font-size: 11px; color: var(--muted); letter-spacing: .04em; text-transform: uppercase; }
input[type=number], select {
  font-family: var(--font-mono); font-size: 13.5px; color: var(--ink); background: var(--bg);
  border: 1px solid var(--line); border-radius: 8px; padding: 7px 8px; min-height: 36px;
}
input[type=number] { width: 78px; text-align: center; }
select { padding-right: 6px; }
button {
  font-family: var(--font-sans); font-size: 13.5px; color: var(--ink); background: var(--surface);
  border: 1px solid var(--line); border-radius: 8px; padding: 7px 12px; min-height: 36px;
  cursor: pointer; white-space: nowrap;
}
button:hover:not(:disabled) { border-color: var(--muted); }
button:disabled { opacity: .5; cursor: not-allowed; }
button.primary { background: var(--accent); border-color: var(--accent); color: var(--surface); font-weight: 600; }
button.primary:hover:not(:disabled) { filter: brightness(1.08); }
button[aria-pressed="true"] { background: var(--accent-soft); border-color: var(--accent); color: var(--accent); font-weight: 600; }
.spacer { flex: 1 1 auto; }
:focus-visible { outline: 2px solid var(--accent); outline-offset: 2px; border-radius: 8px; }

/* stats */
.stats { display: grid; grid-template-columns: repeat(5, 1fr); gap: 1px; background: var(--line); border-bottom: 1px solid var(--line); }
.stat { background: var(--surface); padding: 9px 12px; }
.stat .lab { font-family: var(--font-mono); font-size: 10px; letter-spacing: .07em; text-transform: uppercase; color: var(--muted); }
.stat .val { font-family: var(--font-mono); font-size: 17px; font-variant-numeric: tabular-nums; line-height: 1.25; }

/* commentary */
.note {
  display: flex; align-items: flex-start; gap: 9px; padding: 10px 12px;
  font-family: var(--font-mono); font-size: 12.5px; line-height: 1.5;
  border-bottom: 1px solid var(--line); border-left: 3px solid var(--line);
  background: var(--bg); min-height: 42px; word-break: break-word;
}
.note .dot { width: 8px; height: 8px; border-radius: 50%; background: var(--muted); flex: 0 0 auto; margin-top: 6px; }
.note.info { border-left-color: var(--accent); background: var(--accent-soft); }
.note.info .dot { background: var(--accent); }
.note.ok { border-left-color: var(--run); background: var(--run-soft); }
.note.ok .dot { background: var(--run); }
.note.warn { border-left-color: var(--danger); background: var(--danger-soft); }
.note.warn .dot { background: var(--danger); }

/* canvas */
.canvas-wrap {
  background: var(--canvas); overflow-x: auto; overflow-y: hidden; padding: 10px 0 6px; min-height: 210px;
  display: flex; align-items: flex-start;
  justify-content: center;
  justify-content: safe center; /* overflowing trees stay scrollable from the left edge */
}
svg.tree { display: block; flex: 0 0 auto; }
/* a wide tree scrolls sideways — fade the edges so it is obvious there is more */
.canvas-shell { position: relative; }
.fade {
  position: absolute; top: 0; bottom: 0; width: 28px; pointer-events: none;
  opacity: 0; transition: opacity .18s linear;
}
.fade-l { left: 0; background: linear-gradient(to right, var(--canvas), transparent); }
.fade-r { right: 0; background: linear-gradient(to left, var(--canvas), transparent); }
.canvas-shell.can-l .fade-l, .canvas-shell.can-r .fade-r { opacity: 1; }
.node .box { fill: var(--surface); stroke: var(--line); stroke-width: 1.25; }
.node .sep { stroke: var(--line); stroke-width: 1; }
.node .ptr { fill: var(--muted); fill-opacity: .5; }
.node text.k { fill: var(--ink); font-family: var(--font-mono); font-size: 13px; font-variant-numeric: tabular-nums; cursor: pointer; }
.node text.k.empty { fill: var(--muted); cursor: default; }
.node text.rootlab { fill: var(--muted); font-family: var(--font-mono); font-size: 8.5px; letter-spacing: .1em; cursor: default; }
.node.visit .box { stroke: var(--accent); stroke-width: 2; fill: var(--accent-soft); }
.node.visit .ptr { fill: var(--accent); }
.node.ins .box { stroke: var(--accent); stroke-width: 2; }
.node.over .box { stroke: var(--danger); stroke-width: 2.4; fill: var(--danger-soft); }
.node.over { animation: pulse .5s ease-in-out infinite alternate; }
.node.under .box { stroke: var(--danger); stroke-width: 2; stroke-dasharray: 4 3; fill: var(--danger-soft); }
.node.gone .box { stroke: var(--danger); stroke-width: 2; }
@keyframes pulse { from { opacity: 1; } to { opacity: .62; } }
.cell.new { fill: var(--run-soft); stroke: var(--run); stroke-width: 1.4; }
.cell.up { fill: var(--accent-soft); stroke: var(--accent); stroke-width: 1.4; }
.cell.kill { fill: var(--danger-soft); stroke: var(--danger); stroke-width: 1.4; }
.edge { stroke: var(--muted); stroke-opacity: .38; stroke-width: 1.4; fill: none; }

/* log */
.logwrap { border-top: 1px solid var(--line); }
.logwrap h2 { margin: 0; padding: 8px 12px 4px; font-family: var(--font-mono); font-size: 10px; letter-spacing: .08em; text-transform: uppercase; color: var(--muted); font-weight: 500; }
.log { height: 104px; overflow-y: auto; padding: 0 12px 10px; font-family: var(--font-mono); font-size: 11.5px; line-height: 1.65; color: var(--muted); }
.log div { display: flex; gap: 7px; }
.log b { flex: 0 0 auto; font-weight: 400; color: var(--muted); opacity: .8; }
.log .t-ok { color: var(--run); }
.log .t-warn { color: var(--danger); }
.log .t-info { color: var(--ink); }

.legend { display: flex; flex-wrap: wrap; gap: 12px; padding: 9px 12px; border-top: 1px solid var(--line); font-family: var(--font-mono); font-size: 11px; color: var(--muted); }
.legend span { display: inline-flex; align-items: center; gap: 6px; }
.legend i { width: 12px; height: 12px; border-radius: 3px; display: inline-block; border: 2px solid var(--line); }
.legend i.l-visit { border-color: var(--accent); background: var(--accent-soft); }
.legend i.l-split { border-color: var(--danger); background: var(--danger-soft); }
.legend i.l-new { border-color: var(--run); background: var(--run-soft); }

.hint { margin: 10px 2px 0; font-size: 12.5px; color: var(--muted); }
.hint b { font-family: var(--font-mono); font-weight: 600; color: var(--ink); }
.hint kbd { font-family: var(--font-mono); font-size: 11px; border: 1px solid var(--line); border-bottom-width: 2px; border-radius: 5px; padding: 1px 5px; background: var(--surface); color: var(--ink); }
footer { margin-top: 18px; font-family: var(--font-mono); font-size: 11px; color: var(--muted); letter-spacing: .04em; }
.sr { position: absolute; width: 1px; height: 1px; overflow: hidden; clip: rect(0 0 0 0); white-space: nowrap; }

@media (max-width: 560px) {
  .wrap { padding: 16px 10px 24px; }
  header h1 { font-size: 19px; }
  .controls { gap: 6px; }
  .controls .spacer { display: none; }
  button, input[type=number], select { font-size: 13px; }
  .stats { grid-template-columns: repeat(3, 1fr); }
  .stat { padding: 8px 10px; }
  .stat:last-child { grid-column: span 2; }
  .stat .val { font-size: 15px; }
  .canvas-wrap { min-height: 168px; }
  .log { height: 92px; }
}
@media (prefers-reduced-motion: reduce) {
  .node.over { animation: none; }
  .fade { transition: none; }
  * { scroll-behavior: auto !important; }
}
</style>
</head>
<body>
<div class="wrap">
  <header>
    <div class="chip">B-tree · order 4 · max 3 keys per node</div>
    <h1>B-Tree Visualizer</h1>
    <p class="lede">A B-tree is how databases keep millions of sorted keys shallow enough to reach in three hops. Nodes hold up to 3 keys here — the 4th forces a split, and the middle key gets promoted to the parent. Watch it happen, key by key.</p>
  </header>

  <div class="panel">
    <form class="controls" id="controls" autocomplete="off" novalidate>
      <div class="field">
        <label for="keyIn">Key</label>
        <input type="number" id="keyIn" min="1" max="999" step="1" value="43" inputmode="numeric" aria-describedby="hint">
      </div>
      <button type="submit" class="primary" id="btnIns">Insert</button>
      <button type="button" id="btnDel">Delete</button>
      <button type="button" id="btnRand">Random key</button>
      <span class="spacer"></span>
      <button type="button" id="btnAuto" aria-pressed="false">▶ Autoplay</button>
      <div class="field">
        <label for="speed">Speed</label>
        <select id="speed">
          <option value="720">Slow</option>
          <option value="440" selected>Normal</option>
          <option value="250">Fast</option>
        </select>
      </div>
      <button type="button" id="btnReset">Reset</button>
    </form>

    <div class="stats">
      <div class="stat"><div class="lab">keys</div><div class="val" id="sKeys">0</div></div>
      <div class="stat"><div class="lab">nodes</div><div class="val" id="sNodes">0</div></div>
      <div class="stat"><div class="lab">height</div><div class="val" id="sHeight">0</div></div>
      <div class="stat"><div class="lab">splits</div><div class="val" id="sSplits">0</div></div>
      <div class="stat"><div class="lab">merges</div><div class="val" id="sMerges">0</div></div>
    </div>

    <p class="note" id="note"><span class="dot"></span><span id="noteText">ready</span></p>

    <div class="canvas-shell" id="canvasShell">
    <div class="canvas-wrap" id="canvasWrap">
      <svg class="tree" id="svg" viewBox="0 0 400 200" preserveAspectRatio="xMidYMid meet" role="img" aria-labelledby="svgTitle" aria-describedby="svgDesc">
        <title id="svgTitle">B-tree structure</title>
        <desc id="svgDesc">An empty B-tree.</desc>
        <g id="edgeLayer"></g>
        <g id="nodeLayer"></g>
      </svg>
    </div>
      <div class="fade fade-l" aria-hidden="true"></div>
      <div class="fade fade-r" aria-hidden="true"></div>
    </div>

    <div class="legend">
      <span><i class="l-visit"></i> on the search path</span>
      <span><i class="l-split"></i> overfull — splitting</span>
      <span><i class="l-new"></i> key landed</span>
    </div>

    <div class="logwrap">
      <h2>Operation log</h2>
      <div class="log" id="log"></div>
    </div>
  </div>

  <p class="hint" id="hint"><kbd>Enter</kbd> inserts the key in the box. Try <b>43</b>, then <b>45</b> — the second one overfills a leaf and splits it. Click any key in the tree to load it into the box, then Delete.</p>
  <p class="sr" id="sr" aria-live="polite" role="status"></p>
  <footer>demo · sloprun.dev</footer>
</div>

<script>
(function () {
  "use strict";

  /* ---------- theme bridge (platform postMessage + standalone media query) ---------- */
  window.addEventListener("message", function (e) {
    var d = e && e.data;
    if (d && d.type === "sloprun:theme" && (d.theme === "light" || d.theme === "dark")) {
      document.documentElement.setAttribute("data-theme", d.theme);
    }
  });

  /* ---------- geometry ---------- */
  // GAP must stay >= CELL_W: a node can only ever grow by one cell per frame,
  // and its neighbours reach their new x over the tween rather than instantly,
  // so a smaller gap makes the widening node overlap them mid-animation.
  var CELL_W = 32, NODE_H = 30, GAP = 34, LEVEL_H = 76, MARGIN = 18;
  var MAXK = 3, MINK = 1, CAP = 40;

  var SVG_NS = "http://www.w3.org/2000/svg";
  var svg = document.getElementById("svg");
  var nodeLayer = document.getElementById("nodeLayer");
  var edgeLayer = document.getElementById("edgeLayer");
  var canvasWrap = document.getElementById("canvasWrap");
  var canvasShell = document.getElementById("canvasShell");
  var noteEl = document.getElementById("note");
  var noteText = document.getElementById("noteText");
  var logEl = document.getElementById("log");
  var srEl = document.getElementById("sr");
  var keyIn = document.getElementById("keyIn");
  var speedEl = document.getElementById("speed");
  var btnAuto = document.getElementById("btnAuto");

  function svgEl(tag, attrs) {
    var n = document.createElementNS(SVG_NS, tag);
    if (attrs) for (var k in attrs) n.setAttribute(k, attrs[k]);
    return n;
  }
  function reduced() {
    return window.matchMedia && window.matchMedia("(prefers-reduced-motion: reduce)").matches;
  }

  /* ---------- tree model ---------- */
  var uid = 0;
  function nid() { return ++uid; }
  var root = { id: nid(), keys: [], children: [] };
  var splits = 0, merges = 0;

  function isLeaf(n) { return n.children.length === 0; }
  function clone(n) { return { id: n.id, keys: n.keys.slice(), children: n.children.map(clone) }; }
  function has(n, k) {
    var i = 0;
    while (i < n.keys.length && k > n.keys[i]) i++;
    if (i < n.keys.length && n.keys[i] === k) return true;
    return isLeaf(n) ? false : has(n.children[i], k);
  }
  function allKeys(n, out) {
    out = out || [];
    for (var i = 0; i < n.keys.length; i++) {
      if (!isLeaf(n)) allKeys(n.children[i], out);
      out.push(n.keys[i]);
    }
    if (!isLeaf(n)) allKeys(n.children[n.children.length - 1], out);
    return out;
  }
  function countKeys(n) {
    var c = n.keys.length;
    for (var i = 0; i < n.children.length; i++) c += countKeys(n.children[i]);
    return c;
  }
  function countNodes(n) {
    var c = 1;
    for (var i = 0; i < n.children.length; i++) c += countNodes(n.children[i]);
    return c;
  }
  function height(n) { return n.children.length ? 1 + height(n.children[0]) : 0; }
  function fmt(arr) { return arr.length ? "[" + arr.join(" ") + "]" : "[ ]"; }
  function plur(n, word) { return n + " " + word + (n === 1 ? "" : "s"); }
  function summary() {
    return plur(countKeys(root), "key") + " · height " + height(root) + " · " + plur(countNodes(root), "node");
  }

  /* ---------- frame recorder ---------- */
  var FR = [];
  function snap(hi, hk, note, tone, origin) {
    FR.push({
      tree: clone(root), hi: hi || {}, hk: hk || {},
      note: note, tone: tone || "info", origin: origin || {},
      sp: splits, mg: merges
    });
  }

  /* ---------- insert ---------- */
  function opInsert(key) {
    if (countKeys(root) >= CAP && !has(root, key)) {
      snap({}, {}, "tree is full for this demo (" + CAP + " keys) — delete some or reset", "warn");
      return;
    }
    if (has(root, key)) {
      snap({}, {}, key + " → already in the tree, nothing to do", "warn");
      return;
    }
    var path = [], n = root, i;
    while (!isLeaf(n)) {
      i = 0;
      while (i < n.keys.length && key > n.keys[i]) i++;
      snap(mk(n.id, "visit"), {}, key + " → at " + fmt(n.keys) + " → follow child " + i, "info");
      path.push({ node: n, i: i });
      n = n.children[i];
    }
    snap(mk(n.id, "visit"), {}, key + " → reached leaf " + fmt(n.keys), "info");

    var at = 0;
    while (at < n.keys.length && key > n.keys[at]) at++;
    n.keys.splice(at, 0, key);
    var hk = {}; hk[n.id + ":" + at] = "new";
    snap(mk(n.id, "ins"), hk, key + " → placed in leaf " + fmt(n.keys), "info");

    while (n.keys.length > MAXK) {
      var leafy = isLeaf(n);
      snap(mk(n.id, "over"), {}, (leafy ? "leaf" : "node") + " " + fmt(n.keys) + " holds 4 keys > 3 → split", "warn");

      var mid = 1, med = n.keys[mid];
      var left = n;
      var right = { id: nid(), keys: n.keys.slice(mid + 1), children: n.children.slice(mid + 1) };
      left.keys = n.keys.slice(0, mid);
      left.children = n.children.slice(0, mid + 1);
      splits++;

      var p = path.pop(), hi = {}, hk2 = {}, org = {};
      org[right.id] = left.id;
      hi[left.id] = "ins"; hi[right.id] = "ins";
      if (!p) {
        var nr = { id: nid(), keys: [med], children: [left, right] };
        org[nr.id] = left.id;
        root = nr;
        hi[nr.id] = "visit"; hk2[nr.id + ":0"] = "up";
        snap(hi, hk2, "median " + med + " promoted → new root " + fmt([med]) + ", tree grew to height " + height(root), "info", org);
        n = nr;
      } else {
        p.node.keys.splice(p.i, 0, med);
        p.node.children.splice(p.i + 1, 0, right);
        hi[p.node.id] = "visit"; hk2[p.node.id + ":" + p.i] = "up";
        snap(hi, hk2, "median " + med + " promoted → parent now " + fmt(p.node.keys), "info", org);
        n = p.node;
      }
    }
    snap({}, {}, "✓ inserted " + key + " · " + summary(), "ok");
  }

  function mk(id, kind) { var o = {}; o[id] = kind; return o; }

  /* ---------- delete ---------- */
  function opDelete(key) {
    if (!has(root, key)) {
      snap({}, {}, key + " → not in the tree", "warn");
      return;
    }
    delRec(root, key);
    if (root.keys.length === 0 && root.children.length === 1) {
      root = root.children[0];
      snap(mk(root.id, "visit"), {}, "root emptied → old root dropped, height now " + height(root), "info");
    }
    snap({}, {}, "✓ deleted " + key + " · " + summary(), "ok");
  }

  function delRec(node, key) {
    var i = 0;
    while (i < node.keys.length && key > node.keys[i]) i++;
    if (i < node.keys.length && node.keys[i] === key) {
      if (isLeaf(node)) {
        var hk = {}; hk[node.id + ":" + i] = "kill";
        snap(mk(node.id, "gone"), hk, key + " → found in leaf " + fmt(node.keys) + " → remove", "info");
        node.keys.splice(i, 1);
        snap(mk(node.id, "ins"), {}, "leaf is now " + fmt(node.keys), "info");
      } else {
        var pred = node.children[i];
        while (!isLeaf(pred)) pred = pred.children[pred.children.length - 1];
        var pk = pred.keys[pred.keys.length - 1];
        var h1 = {}; h1[node.id] = "gone"; h1[pred.id] = "visit";
        var k1 = {}; k1[node.id + ":" + i] = "kill";
        snap(h1, k1, key + " sits in an internal node → swap in predecessor " + pk, "info");
        node.keys[i] = pk;
        var k2 = {}; k2[node.id + ":" + i] = "up";
        snap(mk(node.id, "ins"), k2, pk + " moved up → now delete " + pk + " from its leaf", "info");
        delRec(node.children[i], pk);
        fix(node, i);
      }
    } else {
      snap(mk(node.id, "visit"), {}, key + " → at " + fmt(node.keys) + " → follow child " + i, "info");
      delRec(node.children[i], key);
      fix(node, i);
    }
  }

  function fix(parent, i) {
    var c = parent.children[i];
    if (c.keys.length >= MINK) return;
    var L = i > 0 ? parent.children[i - 1] : null;
    var R = i < parent.children.length - 1 ? parent.children[i + 1] : null;

    if (L && L.keys.length > MINK) {
      var h = {}; h[c.id] = "under"; h[L.id] = "visit";
      snap(h, {}, "node " + fmt(c.keys) + " underflows → borrow from left sibling " + fmt(L.keys), "warn");
      var down = parent.keys[i - 1], up = L.keys[L.keys.length - 1];
      c.keys.unshift(down);
      parent.keys[i - 1] = L.keys.pop();
      if (L.children.length) c.children.unshift(L.children.pop());
      var k = {}; k[c.id + ":0"] = "new";
      snap(mk(c.id, "ins"), k, "rotated: " + down + " came down, " + up + " went up → " + fmt(c.keys), "info");
      return;
    }
    if (R && R.keys.length > MINK) {
      var h2 = {}; h2[c.id] = "under"; h2[R.id] = "visit";
      snap(h2, {}, "node " + fmt(c.keys) + " underflows → borrow from right sibling " + fmt(R.keys), "warn");
      var down2 = parent.keys[i], up2 = R.keys[0];
      c.keys.push(down2);
      parent.keys[i] = R.keys.shift();
      if (R.children.length) c.children.push(R.children.shift());
      var k2 = {}; k2[c.id + ":" + (c.keys.length - 1)] = "new";
      snap(mk(c.id, "ins"), k2, "rotated: " + down2 + " came down, " + up2 + " went up → " + fmt(c.keys), "info");
      return;
    }

    if (L) {
      var h3 = {}; h3[c.id] = "under"; h3[L.id] = "under";
      snap(h3, {}, "no sibling to spare a key → merge " + fmt(L.keys) + " + " + parent.keys[i - 1] + " + " + fmt(c.keys), "warn");
      L.keys = L.keys.concat([parent.keys[i - 1]], c.keys);
      L.children = L.children.concat(c.children);
      parent.keys.splice(i - 1, 1);
      parent.children.splice(i, 1);
      merges++;
      snap(mk(L.id, "ins"), {}, "merged into " + fmt(L.keys) + " · parent now " + fmt(parent.keys), "info");
    } else if (R) {
      var h4 = {}; h4[c.id] = "under"; h4[R.id] = "under";
      snap(h4, {}, "no sibling to spare a key → merge " + fmt(c.keys) + " + " + parent.keys[i] + " + " + fmt(R.keys), "warn");
      c.keys = c.keys.concat([parent.keys[i]], R.keys);
      c.children = c.children.concat(R.children);
      parent.keys.splice(i, 1);
      parent.children.splice(i + 1, 1);
      merges++;
      snap(mk(c.id, "ins"), {}, "merged into " + fmt(c.keys) + " · parent now " + fmt(parent.keys), "info");
    }
  }

  /* ---------- layout ---------- */
  function layout(tree) {
    var cursor = MARGIN, nodes = [], edges = [];
    (function walk(n, depth) {
      n._w = Math.max(1, n.keys.length) * CELL_W;
      n._y = MARGIN + depth * LEVEL_H;
      if (!n.children.length) {
        n._x = cursor;
        cursor += n._w + GAP;
      } else {
        for (var i = 0; i < n.children.length; i++) walk(n.children[i], depth + 1);
        var f = n.children[0], l = n.children[n.children.length - 1];
        n._x = ((f._x + f._w / 2) + (l._x + l._w / 2)) / 2 - n._w / 2;
      }
    })(tree, 0);

    (function collect(n) {
      nodes.push(n);
      for (var i = 0; i < n.children.length; i++) {
        edges.push({ pid: n.id, cid: n.children[i].id, slot: i * CELL_W, cw: n.children[i]._w });
        collect(n.children[i]);
      }
    })(tree);

    var minX = Infinity, maxX = -Infinity, maxY = 0;
    nodes.forEach(function (n) {
      if (n._x < minX) minX = n._x;
      if (n._x + n._w > maxX) maxX = n._x + n._w;
      if (n._y > maxY) maxY = n._y;
    });
    var shift = MARGIN - minX;
    nodes.forEach(function (n) { n._x += shift; });
    return {
      nodes: nodes, edges: edges,
      W: Math.max(120, (maxX - minX) + MARGIN * 2),
      H: maxY + NODE_H + MARGIN
    };
  }

  /* ---------- painting ---------- */
  var gNodes = new Map(), gEdges = new Map(), curPos = new Map();
  var curVB = { w: 400, h: 200 }, raf = null, lastL = null, finishFrame = null, settleTimer = null;

  function paintNode(g, n, frame) {
    while (g.firstChild) g.removeChild(g.firstChild);
    var w = Math.max(1, n.keys.length) * CELL_W, i;
    g.appendChild(svgEl("rect", { "class": "box", x: 0, y: 0, width: w, height: NODE_H, rx: 7 }));
    for (i = 0; i < n.keys.length; i++) {
      var kind = frame.hk[n.id + ":" + i];
      if (kind) {
        g.appendChild(svgEl("rect", {
          "class": "cell " + kind, x: i * CELL_W + 2.5, y: 2.5,
          width: CELL_W - 5, height: NODE_H - 5, rx: 5
        }));
      }
      var t = svgEl("text", {
        "class": "k", x: i * CELL_W + CELL_W / 2, y: NODE_H / 2,
        "dominant-baseline": "central", "text-anchor": "middle"
      });
      t.textContent = String(n.keys[i]);
      t.setAttribute("data-key", String(n.keys[i]));
      g.appendChild(t);
      if (i > 0) g.appendChild(svgEl("line", { "class": "sep", x1: i * CELL_W, y1: 5, x2: i * CELL_W, y2: NODE_H - 5 }));
    }
    if (!n.keys.length) {
      var e = svgEl("text", { "class": "k empty", x: w / 2, y: NODE_H / 2, "dominant-baseline": "central", "text-anchor": "middle" });
      e.textContent = "empty";
      e.setAttribute("font-size", "8");
      g.appendChild(e);
    }
    for (i = 0; i < n.children.length; i++) {
      g.appendChild(svgEl("circle", { "class": "ptr", cx: i * CELL_W, cy: NODE_H, r: 2.4 }));
    }
    if (n.id === frame.tree.id && n.keys.length) {
      var rl = svgEl("text", { "class": "rootlab", x: w / 2, y: -7, "text-anchor": "middle" });
      rl.textContent = "ROOT";
      g.appendChild(rl);
    }
  }

  function dstr(x1, y1, x2, y2) {
    var m = (y1 + y2) / 2;
    return "M" + x1.toFixed(1) + " " + y1.toFixed(1) +
           " C" + x1.toFixed(1) + " " + m.toFixed(1) + " " + x2.toFixed(1) + " " + m.toFixed(1) +
           " " + x2.toFixed(1) + " " + y2.toFixed(1);
  }

  var curScale = 1;
  function applySize(W, H) {
    var cw = canvasWrap.clientWidth || 320;
    var maxH = window.innerWidth < 560 ? 292 : 380;
    // fill the width when the tree is small, shrink to fit when it is big — but
    // never below 70%, past which the keys stop being readable and we scroll instead.
    var s = Math.min(cw / W, maxH / H, 2);
    if (s < 0.7) s = 0.7;
    curScale = s;
    svg.style.width = Math.round(W * s) + "px";
    svg.style.height = Math.round(H * s) + "px";
  }

  function updateFades() {
    var over = canvasWrap.scrollWidth - canvasWrap.clientWidth;
    canvasShell.classList.toggle("can-l", over > 1 && canvasWrap.scrollLeft > 2);
    canvasShell.classList.toggle("can-r", over > 1 && canvasWrap.scrollLeft < over - 2);
  }
  canvasWrap.addEventListener("scroll", updateFades, { passive: true });

  // when the tree is wider than the canvas, follow the action instead of letting
  // the interesting node happen off-screen (matters most on phones).
  function keepInView(L, frame) {
    if (canvasWrap.scrollWidth <= canvasWrap.clientWidth + 1) return;
    var target = null;
    for (var i = 0; i < L.nodes.length; i++) {
      if (frame.hi[L.nodes[i].id]) { target = L.nodes[i]; break; }
    }
    if (!target) return;
    var pad = 20;
    var x0 = target._x * curScale - pad;
    var x1 = (target._x + target._w) * curScale + pad;
    if (x0 < canvasWrap.scrollLeft) canvasWrap.scrollLeft = Math.max(0, x0);
    else if (x1 > canvasWrap.scrollLeft + canvasWrap.clientWidth) {
      canvasWrap.scrollLeft = x1 - canvasWrap.clientWidth;
    }
  }

  function render(frame, dur) {
    // An animation still in flight would leave its exiting <g> nodes stranded on
    // screen (they are only removed on completion) and would leave curPos holding
    // positions from two frames back, so the next step would jump. Snap the
    // previous frame to its end state first. This also keeps a backgrounded tab
    // — where requestAnimationFrame stops but setTimeout keeps firing — coherent.
    if (finishFrame) finishFrame();
    var L = layout(frame.tree);
    lastL = L;

    var seen = new Set();
    L.nodes.forEach(function (n) {
      seen.add(n.id);
      var g = gNodes.get(n.id);
      if (!g) { g = svgEl("g", { "class": "node", opacity: "0" }); gNodes.set(n.id, g); nodeLayer.appendChild(g); }
      var cls = "node";
      if (frame.hi[n.id]) cls += " " + frame.hi[n.id];
      g.setAttribute("class", cls);
      paintNode(g, n, frame);
    });

    var items = L.nodes.map(function (n) {
      var to = { x: n._x, y: n._y };
      var from = curPos.get(n.id), entering = false;
      if (!from) {
        entering = true;
        var src = frame.origin[n.id];
        var sp = src != null ? curPos.get(src) : null;
        from = sp ? { x: sp.x, y: sp.y } : { x: to.x, y: to.y };
      }
      return { id: n.id, g: gNodes.get(n.id), from: from, to: to, entering: entering };
    });

    var exits = [];
    gNodes.forEach(function (g, id) { if (!seen.has(id)) exits.push({ g: g, id: id }); });

    var ekeys = new Set();
    var edgeItems = L.edges.map(function (e) {
      var k = e.pid + "-" + e.cid;
      ekeys.add(k);
      var p = gEdges.get(k), entering = false;
      if (!p) { entering = true; p = svgEl("path", { "class": "edge", opacity: "0" }); gEdges.set(k, p); edgeLayer.appendChild(p); }
      return { pid: e.pid, cid: e.cid, slot: e.slot, cw: e.cw, path: p, entering: entering };
    });
    var eexits = [];
    gEdges.forEach(function (p, k) { if (!ekeys.has(k)) eexits.push({ p: p, k: k }); });

    var fromVB = { w: curVB.w, h: curVB.h };
    applySize(L.W, L.H);
    keepInView(L, frame);
    updateFades();

    var t0 = null;
    function step(ts) {
      if (t0 === null) t0 = ts;
      var p = dur <= 0 ? 1 : Math.min(1, (ts - t0) / dur);
      var e = 1 - Math.pow(1 - p, 3);
      var pos = new Map();
      items.forEach(function (it) {
        var x = it.from.x + (it.to.x - it.from.x) * e;
        var y = it.from.y + (it.to.y - it.from.y) * e;
        pos.set(it.id, { x: x, y: y });
        it.g.setAttribute("transform", "translate(" + x.toFixed(2) + "," + y.toFixed(2) + ")");
        it.g.setAttribute("opacity", it.entering ? e.toFixed(3) : "1");
      });
      exits.forEach(function (x) { x.g.setAttribute("opacity", (1 - e).toFixed(3)); });
      edgeItems.forEach(function (ed) {
        var a = pos.get(ed.pid), b = pos.get(ed.cid);
        if (!a || !b) return;
        ed.path.setAttribute("d", dstr(a.x + ed.slot, a.y + NODE_H, b.x + ed.cw / 2, b.y));
        ed.path.setAttribute("opacity", ed.entering ? e.toFixed(3) : "1");
      });
      eexits.forEach(function (x) { x.p.setAttribute("opacity", (1 - e).toFixed(3)); });
      var vw = fromVB.w + (L.W - fromVB.w) * e, vh = fromVB.h + (L.H - fromVB.h) * e;
      svg.setAttribute("viewBox", "0 0 " + vw.toFixed(1) + " " + vh.toFixed(1));

      if (p < 1) { raf = requestAnimationFrame(step); return; }
      settle(pos);
    }
    function settle(pos) {
      if (raf) { cancelAnimationFrame(raf); raf = null; }
      clearTimeout(settleTimer); settleTimer = null;
      finishFrame = null;
      curPos = pos;
      curVB = { w: L.W, h: L.H };
      exits.forEach(function (x) { if (x.g.parentNode) x.g.parentNode.removeChild(x.g); gNodes.delete(x.id); });
      eexits.forEach(function (x) { if (x.p.parentNode) x.p.parentNode.removeChild(x.p); gEdges.delete(x.k); });
    }
    // force the tween to its final values, wherever it currently is
    var mine = function () { t0 = 0; step(dur > 0 ? dur + 1 : 1); };
    finishFrame = mine;
    if (dur <= 0) {
      mine();
    } else {
      raf = requestAnimationFrame(step);
      // backstop: if rAF never runs (hidden tab, throttled webview) the frame must
      // still land on its real geometry rather than freeze half-way
      clearTimeout(settleTimer);
      settleTimer = setTimeout(function () { if (finishFrame === mine) mine(); }, dur + 80);
    }

    describe(frame.tree);
    updateStats(frame);
  }

  function describe(tree) {
    var levels = [], q = [{ n: tree, d: 0 }];
    while (q.length) {
      var it = q.shift();
      (levels[it.d] = levels[it.d] || []).push(fmt(it.n.keys));
      it.n.children.forEach(function (c) { q.push({ n: c, d: it.d + 1 }); });
    }
    var txt = levels.map(function (l, i) {
      return (i === 0 ? "root " : "level " + i + " ") + l.join(" ");
    }).join(". ");
    document.getElementById("svgDesc").textContent =
      countKeys(tree) + " keys in " + countNodes(tree) + " nodes, height " + height(tree) + ". " + txt + ".";
  }

  // counters come off the frame, not the live tree, so a replayed step never
  // shows a split that has not been drawn yet.
  function updateStats(frame) {
    var tree = frame.tree;
    document.getElementById("sKeys").textContent = countKeys(tree);
    document.getElementById("sNodes").textContent = countNodes(tree);
    document.getElementById("sHeight").textContent = height(tree);
    document.getElementById("sSplits").textContent = frame.sp != null ? frame.sp : splits;
    document.getElementById("sMerges").textContent = frame.mg != null ? frame.mg : merges;
  }

  /* ---------- commentary + log ---------- */
  function setNote(note, tone) {
    noteText.textContent = note;
    noteEl.className = "note " + tone;
  }
  var logN = 0;
  function log(note, tone) {
    var row = document.createElement("div");
    var b = document.createElement("b");
    b.textContent = String(++logN).padStart(3, "0");
    var s = document.createElement("span");
    s.className = "t-" + tone;
    s.textContent = note;
    row.appendChild(b); row.appendChild(s);
    logEl.appendChild(row);
    while (logEl.childNodes.length > 80) logEl.removeChild(logEl.firstChild);
    logEl.scrollTop = logEl.scrollHeight;
  }

  /* ---------- player ---------- */
  var queue = [], playing = false, stepTimer = null, autoTimer = null, auto = false;

  function frameMs() { return parseInt(speedEl.value, 10) || 440; }

  var QMAX = 6;
  function enqueue(fn) {
    if (queue.length >= QMAX) {              // held-down Enter must not bury the demo
      srEl.textContent = "Queue is full — wait for the current run to finish.";
      return false;
    }
    queue.push(fn);
    if (!playing) drain();
    return true;
  }

  function drain() {
    if (queue.length === 0) {
      playing = false;
      setBusy(false);
      if (auto) {
        clearTimeout(autoTimer);
        autoTimer = setTimeout(autoStep, Math.max(220, frameMs() * 0.7));
      }
      return;
    }
    playing = true;
    setBusy(true);
    var fn = queue.shift();
    FR = [];
    // if an op ever throws mid-mutation, roll the tree back rather than leaving a
    // half-split structure on screen (clone keeps node ids, so the view stays put)
    var undo = clone(root), undoSp = splits, undoMg = merges;
    try { fn(); } catch (err) {
      root = undo; splits = undoSp; merges = undoMg;
      FR = [];
      snap({}, {}, "operation aborted — tree restored", "warn");
    }
    var frames = FR.slice();
    FR = [];
    if (!frames.length) { drain(); return; }

    // reduced motion: the story is still told step by step, the tree just cuts
    // between states instead of sliding between them.
    var soft = reduced();
    var i = 0, ms = soft ? Math.max(240, frameMs() * 0.8) : frameMs();
    var dur = soft ? 0 : Math.min(ms - 70, 380);
    (function play() {
      if (i >= frames.length) { drain(); return; }
      var f = frames[i++];
      render(f, dur);
      setNote(f.note, f.tone);
      log(f.note, f.tone);
      if (i >= frames.length) srEl.textContent = f.note;
      stepTimer = setTimeout(play, ms);
    })();
  }

  function setBusy(b) {
    document.getElementById("btnIns").disabled = b;
    document.getElementById("btnDel").disabled = b;
    document.getElementById("btnRand").disabled = b;
  }

  /* ---------- actions ---------- */
  function readKey() {
    var v = parseInt(keyIn.value, 10);
    if (!isFinite(v) || v < 1 || v > 999) {
      setNote("enter a whole number between 1 and 999", "warn");
      log("enter a whole number between 1 and 999", "warn");
      srEl.textContent = "Invalid key.";
      keyIn.focus();
      return null;
    }
    return v;
  }
  function randomFree() {
    var taken = {}, ks = allKeys(root);
    ks.forEach(function (k) { taken[k] = 1; });
    for (var t = 0; t < 400; t++) {
      var v = 1 + Math.floor(Math.random() * 99);
      if (!taken[v]) return v;
    }
    return null;
  }

  document.getElementById("controls").addEventListener("submit", function (e) {
    e.preventDefault();
    var k = readKey();
    if (k === null) return;
    enqueue(function () { opInsert(k); });
  });
  document.getElementById("btnDel").addEventListener("click", function () {
    var k = readKey();
    if (k === null) return;
    enqueue(function () { opDelete(k); });
  });
  document.getElementById("btnRand").addEventListener("click", function () {
    var k = randomFree();
    if (k === null) return;
    keyIn.value = k;
    enqueue(function () { opInsert(k); });
  });

  function autoStep() {
    if (!auto) return;
    // the visitor may have queued ops by hand; wait for room rather than dropping
    // this tick on the floor, which would leave autoplay stuck showing "Pause"
    if (queue.length >= QMAX) { autoTimer = setTimeout(autoStep, 300); return; }
    var n = countKeys(root);
    var doDelete = n >= 18 && Math.random() < 0.5;
    if (n >= CAP) doDelete = true;
    if (doDelete && n > 0) {
      var ks = allKeys(root);
      var k = ks[Math.floor(Math.random() * ks.length)];
      keyIn.value = k;
      enqueue(function () { opDelete(k); });
    } else {
      var r = randomFree();
      if (r === null) {                       // no free key left: fall back to a delete
        if (n === 0) { autoTimer = setTimeout(autoStep, 400); return; }
        var kk = allKeys(root)[Math.floor(Math.random() * n)];
        keyIn.value = kk;
        enqueue(function () { opDelete(kk); });
        return;
      }
      keyIn.value = r;
      enqueue(function () { opInsert(r); });
    }
  }

  btnAuto.addEventListener("click", function () {
    auto = !auto;
    btnAuto.setAttribute("aria-pressed", auto ? "true" : "false");
    btnAuto.textContent = auto ? "⏸ Pause" : "▶ Autoplay";
    clearTimeout(autoTimer);
    if (auto) {
      srEl.textContent = "Autoplay started.";
      if (!playing) autoStep();
    } else {
      srEl.textContent = "Autoplay paused.";
    }
  });

  document.getElementById("btnReset").addEventListener("click", function () {
    clearTimeout(stepTimer); clearTimeout(autoTimer);
    if (raf) { cancelAnimationFrame(raf); raf = null; }
    clearTimeout(settleTimer); settleTimer = null;
    finishFrame = null;                        // its closure points at nodes we are about to wipe
    queue = []; playing = false; setBusy(false);
    nodeLayer.textContent = ""; edgeLayer.textContent = "";
    gNodes = new Map(); gEdges = new Map(); curPos = new Map();
    logEl.textContent = ""; logN = 0;
    boot(true);
    if (auto) autoTimer = setTimeout(autoStep, 500);
  });

  nodeLayer.addEventListener("click", function (e) {
    var t = e.target;
    if (!t || !t.getAttribute) return;
    var k = t.getAttribute("data-key");
    if (!k) return;
    keyIn.value = k;
    if (!playing) {
      setNote("picked " + k + " — press Insert or Delete", "info");
      srEl.textContent = "Key " + k + " loaded into the box.";
    }
  });

  var rzTimer = null;
  window.addEventListener("resize", function () {
    clearTimeout(rzTimer);
    rzTimer = setTimeout(function () {
      if (lastL) { applySize(lastL.W, lastL.H); updateFades(); }
    }, 120);
  });

  /* ---------- boot ---------- */
  var SEED = [50, 12, 78, 33, 91, 5, 64, 27, 85, 41, 19, 70];
  function boot(isReset) {
    uid = 0; splits = 0; merges = 0;
    root = { id: nid(), keys: [], children: [] };
    SEED.forEach(function (k) { FR = []; opInsert(k); FR = []; });
    var frame = { tree: clone(root), hi: {}, hk: {}, origin: {}, note: "", tone: "info" };
    curVB = { w: 400, h: 200 };
    render(frame, 0);
    var msg = "preloaded " + summary() + " · " + plur(splits, "split") + " along the way";
    setNote(msg, "ok");
    log(msg, "ok");
    srEl.textContent = isReset ? "Tree reset. " + msg : msg;
  }

  boot(false);
  setTimeout(function () { if (lastL) { applySize(lastL.W, lastL.H); updateFades(); } }, 0);
})();
</script>
</body>
</html>

source-visible by construction · nothing is published here without its code

Comments

0 total

No comments yet. If you ran it, say what happened.

Report this post

Goes straight to the moderation queue. Enough independent reports and the post is suspended automatically until a human looks.

what is wrong