Building Blocks: IDs, Hashing and Probabilistic Structures

import { randomUUID, randomUUIDv7 } from "node:crypto";

// Seeded PRNG (mulberry32) so the "random" bytes are the same on every run.
const mulberry32 = (a) => () => {
  a = (a + 0x6d2b79f5) | 0;
  let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32;
};
const rand = mulberry32(42);
const randomBytes = (n) => Uint8Array.from({ length: n }, () => Math.floor(rand() * 256));
const hex = (b) => [...b].map((x) => x.toString(16).padStart(2, "0")).join("");
const format = (b) => hex(b).replace(/^(.{8})(.{4})(.{4})(.{4})(.{12})$/, "$1-$2-$3-$4-$5");

// RFC 9562, section 5.7: 48-bit unix_ts_ms | ver=0111 | 12-bit rand_a | var=10 | 62-bit rand_b
function uuidv7(ms) {
  const b = randomBytes(16);
  for (let i = 0; i < 6; i++) b[i] = Number((BigInt(ms) >> BigInt(8 * (5 - i))) & 0xffn);
  b[6] = (b[6] & 0x0f) | 0x70; // version 7 in the top 4 bits of octet 6
  b[8] = (b[8] & 0x3f) | 0x80; // variant 10 in the top 2 bits of octet 8
  return format(b);
}
// RFC 9562, section 5.4: 122 random bits, then the same version (0100) and variant bits
function uuidv4() {
  const b = randomBytes(16);
  b[6] = (b[6] & 0x0f) | 0x40;
  b[8] = (b[8] & 0x3f) | 0x80;
  return format(b);
}

const start = Date.UTC(2026, 9, 24, 12, 0, 0);
const v7 = [0, 1, 1, 2, 5].map((dt) => uuidv7(start + dt)); // created in this order
const v4 = Array.from({ length: 5 }, uuidv4);
console.log("v7, in creation order:");
v7.forEach((u) => console.log(" ", u));
console.log("v7 sorted as strings == creation order?", JSON.stringify([...v7].sort()) === JSON.stringify(v7));
console.log("v4, in creation order:");
v4.forEach((u) => console.log(" ", u));
console.log("v4 sorted as strings == creation order?", JSON.stringify([...v4].sort()) === JSON.stringify(v4));

const ms = parseInt(v7[0].replace(/-/g, "").slice(0, 12), 16); // the first 48 bits
console.log("timestamp read back from v7[0]:", new Date(ms).toISOString());
console.log("version nibble:", v7[0][14], "| variant bits of", v7[0][19], "=", parseInt(v7[0][19], 16).toString(2).slice(0, 2));

// 100 IDs inside ONE millisecond: the timestamp ties, so order falls to the random bits.
const burst = Array.from({ length: 100 }, () => uuidv7(start + 9));
const outOfOrder = burst.filter((u, i) => i > 0 && u < burst[i - 1]).length;
console.log("same-millisecond burst: out of order", outOfOrder, "of 99 neighbours");

// Node's own generators (randomUUIDv7 needs Node 26.1+ or 24.16+): only print what is stable between runs.
const a = randomUUIDv7(), b = randomUUID();
console.log("node randomUUIDv7 version:", a[14], "| node randomUUID version:", b[14]);
console.log("random bits: v4 =", 128 - 4 - 2, "| v7 =", 128 - 48 - 4 - 2);

v7, in creation order:
  01a16dc8-3600-759f-9d78-3fe1be4e3280
  01a16dc8-3601-7708-840f-2fc887062cd7
  01a16dc8-3601-7e98-bea5-354dbddb8234
  01a16dc8-3602-7d16-b16e-f1231c045c7b
  01a16dc8-3605-742d-85d2-1efe90ea6f94
v7 sorted as strings == creation order? true
v4, in creation order:
  569852ba-4b73-47b1-bee3-6e8b4b19b250
  c9e71779-d221-492d-b5b3-396929a75534
  a0e353ca-6421-4d5e-82bc-a2e0e8359a7d
  2f0cb4b5-4a46-4607-b8fe-92fd292b8f4a
  656f6baf-6656-4553-be9c-8b963c534c52
v4 sorted as strings == creation order? false
timestamp read back from v7[0]: 2026-10-24T12:00:00.000Z
version nibble: 7 | variant bits of 9 = 10
same-millisecond burst: out of order 45 of 99 neighbours
node randomUUIDv7 version: 7 | node randomUUID version: 4
random bits: v4 = 122 | v7 = 74

// Insert 200,000 keys into a B-tree's leaf level (100 keys per page) with a 64-page buffer cache.
// Compare random keys (UUID v4) with time-ordered keys (UUID v7, Snowflake, auto-increment).
const mulberry32 = (a) => () => {
  a = (a + 0x6d2b79f5) | 0;
  let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32;
};
const PAGE = 100, CACHE = 64, N = 200_000;

function run(nextKey) {
  const pages = [[]]; // leaf pages in key order; each holds sorted keys
  const cache = new Map(); // LRU of page objects
  let misses = 0;
  const touch = (p) => {
    if (cache.has(p)) cache.delete(p); else misses++; // a miss = a page read from disk
    cache.set(p, true);
    if (cache.size > CACHE) cache.delete(cache.keys().next().value);
  };
  for (let i = 0; i < N; i++) {
    const key = nextKey(i);
    let lo = 0, hi = pages.length - 1; // last page whose first key <= key
    while (lo < hi) { const mid = (lo + hi + 1) >> 1; if (pages[mid][0] <= key) lo = mid; else hi = mid - 1; }
    const page = pages[lo];
    touch(page);
    let j = page.length; while (j > 0 && page[j - 1] > key) j--;
    page.splice(j, 0, key);
    if (page.length > PAGE) {
      // Appending at the far right: start a fresh page and leave this one full (what B-trees do).
      // Anywhere else: split the page in half.
      const rightmostAppend = lo === pages.length - 1 && j === page.length - 1;
      const cut = rightmostAppend ? PAGE : PAGE / 2;
      pages.splice(lo + 1, 0, page.splice(cut));
    }
  }
  const fill = N / (pages.length * PAGE);
  return `${pages.length} pages, ${(fill * 100).toFixed(0)}% full, ${misses} page reads (${((misses / N) * 100).toFixed(1)}% of inserts)`;
}

const rand = mulberry32(7);
console.log("random (v4)       :", run(() => rand()));
console.log("time-ordered (v7) :", run((i) => i + rand() * 0.5)); // increasing, a little jitter

random (v4)       : 2880 pages, 69% full, 178014 page reads (89.0% of inserts)
time-ordered (v7) : 2000 pages, 100% full, 2000 page reads (1.0% of inserts)

// What the choice of key type costs in index space, before page overhead.
// Assumptions: 1 billion rows; the primary key appears in the primary index and is copied into
// each of 3 secondary indexes (InnoDB secondary indexes store the primary key) and into 2 tables that reference it.
const rows = 1e9, copies = 1 + 3 + 2;
const types = { "BIGINT (Snowflake, auto-increment)": 8, "UUID as BINARY(16) / Postgres uuid": 16, "UUID as CHAR(36) text": 36 };
for (const [name, bytes] of Object.entries(types)) {
  const gib = (rows * copies * bytes) / 2 ** 30;
  console.log(`${name.padEnd(36)} ${String(bytes).padStart(2)} B x ${copies} copies -> ${gib.toFixed(0).padStart(4)} GiB of key bytes`);
}

BIGINT (Snowflake, auto-increment)    8 B x 6 copies ->   45 GiB of key bytes
UUID as BINARY(16) / Postgres uuid   16 B x 6 copies ->   89 GiB of key bytes
UUID as CHAR(36) text                36 B x 6 copies ->  201 GiB of key bytes

// A 64-bit ID sent as a JSON number loses digits in JavaScript: Number has 53 bits of integer precision.
const body = '{"id": 2113963715589509121, "id_str": "2113963715589509121"}';
const parsed = JSON.parse(body);
console.log("as number:", parsed.id, "| exact?", String(parsed.id) === parsed.id_str);
console.log("as string:", parsed.id_str, "-> BigInt", BigInt(parsed.id_str));
console.log("largest safe integer:", Number.MAX_SAFE_INTEGER, `(2^53 - 1, ${String(Number.MAX_SAFE_INTEGER).length} digits)`);
console.log("neighbours collapse:", 2113963715589509121 === 2113963715589509120);

// A recent JavaScript addition (TC39 "JSON.parse source text access"): the reviver sees the raw text.
const exact = JSON.parse(body, (key, value, ctx) => (key === "id" ? BigInt(ctx.source) : value));
console.log("reviver with source:", exact.id);

as number: 2113963715589509000 | exact? false
as string: 2113963715589509121 -> BigInt 2113963715589509121n
largest safe integer: 9007199254740991 (2^53 - 1, 16 digits)
neighbours collapse: true
reviver with source: 2113963715589509121n

import { createHash } from "node:crypto";

const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const encode = (n, len = 7) => {
  let out = "";
  for (let i = 0; i < len; i++, n /= 62n) out = ALPHABET[Number(n % 62n)] + out; // fixed width
  return out;
};
const decode = (s) => [...s].reduce((n, ch) => n * 62n + BigInt(ALPHABET.indexOf(ch)), 0n);
const SPACE = 62n ** 7n; // 3.5 trillion 7-char codes
const ids = [1_000_000_000n, 1_000_000_001n, 1_000_000_002n];

// 1. Plain counter: short and collision-free, but it leaks volume and is easy to enumerate.
console.log("counter:    ", ids.map((n) => encode(n)).join(" "));

// 2. Naive scramble: multiply by a constant mod 62^7. A bijection, but the low digits still count up.
console.log("multiply:   ", ids.map((n) => encode((n * 2_654_435_761n) % SPACE)).join(" "));

// 3. Feistel permutation on 42 bits (2^42 > 62^7), "cycle-walking" until the result fits in 62^7.
const KEYS = [0x2f1a3, 0x1b7e9, 0x0c4d5, 0x3a961]; // the secret
const MASK = (1n << 21n) - 1n;
const round = (half, key) => BigInt(Math.imul(Number(half) ^ key, 0x45d9f3b) >>> 11) & MASK;
const feistel = (x, keys) => {
  let L = x >> 21n, R = x & MASK;
  for (const k of keys) [L, R] = [R, L ^ round(R, k)];
  return (R << 21n) | L; // swap halves at the end so the same code with reversed keys inverts it
};
const permute = (x, keys) => { do x = feistel(x, keys); while (x >= SPACE); return x; };
const toCode = (id) => encode(permute(id, KEYS));
const toId = (code) => permute(decode(code), [...KEYS].reverse());
const codes = ids.map(toCode);
console.log("feistel:    ", codes.join(" "), "-> ids", codes.map(toId).join(", "));

const sample = Array.from({ length: 100_000 }, (_, i) => toCode(BigInt(i)));
console.log("feistel on ids 0..99,999: distinct codes", new Set(sample).size, "| all decode back:", sample.every((c, i) => toId(c) === BigInt(i)));

// 4. Hash of the URL: the same URL always gets the same code, but two URLs can share one.
const hashCode = (url) => encode(BigInt("0x" + createHash("sha256").update(url).digest("hex")) % SPACE);
console.log("hash:       ", hashCode("https://example.com/a"), hashCode("https://example.com/a"), hashCode("https://example.com/b"));

counter:     015ftgG 015ftgH 015ftgI
multiply:    K8B5lgG KB4jVgH KDyNFgI
feistel:     c9Zl8kL nvw5BpY kk2mpWe -> ids 1000000000, 1000000001, 1000000002
feistel on ids 0..99,999: distinct codes 100000 | all decode back: true
hash:        4B9m7rA 4B9m7rA pv1bEGR

// Birthday maths for random (or hashed) short codes: n codes drawn uniformly from N possible.
const fmt = (x) => (x >= 1e7 ? x.toExponential(2) : x.toLocaleString("en-US", { maximumFractionDigits: x < 10 ? 3 : 0 }));

function report(chars, n) {
  const N = 62 ** chars;
  const pairs = (n * (n - 1)) / (2 * N); // expected number of colliding pairs
  const pAny = -Math.expm1(-pairs); // P(at least one collision) ~ 1 - e^(-n^2 / 2N)
  const pNext = n / N; // chance the next new code hits one already taken
  const half = Math.sqrt(2 * N * Math.LN2); // n at which P(any collision) = 50%
  console.log(`${chars} chars, ${fmt(n)} codes in a space of ${fmt(N)}:`);
  console.log(`  expected colliding pairs ${fmt(pairs)} | P(at least one) ${pAny.toFixed(6)}`);
  console.log(`  the next new code is already taken: 1 in ${fmt(Math.round(1 / pNext))} | P(any) reaches 50% at ${fmt(Math.round(half))} codes`);
}
report(7, 1e9);
report(8, 1e9);
report(7, 1e6);

// Check the formula by simulation (seeded): 100,000 random 4-char codes, count draws that hit a taken code.
const mulberry32 = (a) => () => {
  a = (a + 0x6d2b79f5) | 0;
  let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32;
};
const rand = mulberry32(2026);
const N4 = 62 ** 4, n = 100_000, seen = new Set();
let hits = 0;
for (let i = 0; i < n; i++) {
  const code = Math.floor(rand() * N4);
  if (seen.has(code)) hits++; else seen.add(code);
}
console.log(`simulated 4 chars: ${hits} collisions | formula n^2/2N = ${((n * n) / (2 * N4)).toFixed(1)}`);

7 chars, 1.00e+9 codes in a space of 3.52e+12:
  expected colliding pairs 141,980 | P(at least one) 1.000000
  the next new code is already taken: 1 in 3,522 | P(any) reaches 50% at 2,209,524 codes
8 chars, 1.00e+9 codes in a space of 2.18e+14:
  expected colliding pairs 2,290 | P(at least one) 1.000000
  the next new code is already taken: 1 in 218,340 | P(any) reaches 50% at 1.74e+7 codes
7 chars, 1,000,000 codes in a space of 3.52e+12:
  expected colliding pairs 0.142 | P(at least one) 0.132362
  the next new code is already taken: 1 in 3,521,615 | P(any) reaches 50% at 2,209,524 codes
simulated 4 chars: 347 collisions | formula n^2/2N = 338.4

// Sizing a Bloom filter: m = -n ln(p) / (ln 2)^2 bits, k = (m/n) ln 2 hash functions.
const size = (n, p) => {
  const m = Math.ceil((-n * Math.log(p)) / Math.LN2 ** 2);
  const k = Math.round((m / n) * Math.LN2);
  return { bitsPerItem: (m / n).toFixed(2), k, memory: m / 8 };
};
const human = (bytes) => (bytes >= 2 ** 30 ? `${(bytes / 2 ** 30).toFixed(2)} GiB` : `${(bytes / 2 ** 20).toFixed(1)} MiB`);

for (const [what, n] of [["URLs a crawler has seen", 1e9], ["usernames taken", 5e8], ["keys in one SSTable", 1e7]]) {
  for (const p of [0.1, 0.01, 0.001]) {
    const s = size(n, p);
    console.log(`${what.padEnd(23)} n=${n.toExponential(0)} p=${String(p).padEnd(5)} -> ${s.bitsPerItem} bits/item, k=${s.k}, ${human(s.memory)}`);
  }
}
const avgUrl = 80; // bytes per URL if you stored them in a hash set instead (rule of thumb, before overhead)
console.log(`exact set of 1e9 URLs at ${avgUrl} bytes each: ${human(1e9 * avgUrl)} before any hash-table overhead`);

URLs a crawler has seen n=1e+9 p=0.1   -> 4.79 bits/item, k=3, 571.3 MiB
URLs a crawler has seen n=1e+9 p=0.01  -> 9.59 bits/item, k=7, 1.12 GiB
URLs a crawler has seen n=1e+9 p=0.001 -> 14.38 bits/item, k=10, 1.67 GiB
usernames taken         n=5e+8 p=0.1   -> 4.79 bits/item, k=3, 285.7 MiB
usernames taken         n=5e+8 p=0.01  -> 9.59 bits/item, k=7, 571.3 MiB
usernames taken         n=5e+8 p=0.001 -> 14.38 bits/item, k=10, 857.0 MiB
keys in one SSTable     n=1e+7 p=0.1   -> 4.79 bits/item, k=3, 5.7 MiB
keys in one SSTable     n=1e+7 p=0.01  -> 9.59 bits/item, k=7, 11.4 MiB
keys in one SSTable     n=1e+7 p=0.001 -> 14.38 bits/item, k=10, 17.1 MiB
exact set of 1e9 URLs at 80 bytes each: 74.51 GiB before any hash-table overhead

> BF.RESERVE seen:urls 0.01 1000000
OK
> BF.ADD seen:urls https://example.com/a
(integer) 1
> BF.EXISTS seen:urls https://example.com/a
(integer) 1
> BF.EXISTS seen:urls https://example.com/zzz
(integer) 0
> BF.INFO seen:urls
Capacity: 1000000 | Size: 1378568 | Number of filters: 1 | Number of items inserted: 1 | Expansion rate: 2

> PFADD visitors:2026-10-24 alice bob carol alice
(integer) 1
> PFCOUNT visitors:2026-10-24
(integer) 3
> MEMORY USAGE visitors:2026-10-24
(integer) 86
(after PFADD of 100,000 distinct ids to another key)
> PFCOUNT big
(integer) 100420
> MEMORY USAGE big
(integer) 14358

// Count-min sketch (d rows x w counters) + a small top-k list for heavy hitters, on a skewed stream.
function hash32(str, seed) {
  let h = 0x811c9dc5 ^ seed;
  for (let i = 0; i < str.length; i++) h = Math.imul(h ^ str.charCodeAt(i), 0x01000193);
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
const mulberry32 = (a) => () => {
  a = (a + 0x6d2b79f5) | 0;
  let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32;
};

class CountMin {
  constructor(epsilon, delta) {
    this.w = Math.ceil(Math.E / epsilon); // error <= epsilon * N ...
    this.d = Math.ceil(Math.log(1 / delta)); // ... with probability >= 1 - delta
    this.rows = Array.from({ length: this.d }, () => new Uint32Array(this.w));
  }
  add(item, c = 1) {
    for (let r = 0; r < this.d; r++) this.rows[r][hash32(item, r + 1) % this.w] += c;
  }
  estimate(item) { // every row over-counts (collisions only add), so the smallest is closest
    let min = Infinity;
    for (let r = 0; r < this.d; r++) min = Math.min(min, this.rows[r][hash32(item, r + 1) % this.w]);
    return min;
  }
}

// Stream: 1,000,000 search queries over 100,000 distinct terms, Zipf-like (term i has weight 1/i).
const rand = mulberry32(99), TERMS = 100_000, N = 1_000_000;
const cdf = []; let total = 0;
for (let i = 1; i <= TERMS; i++) cdf.push((total += 1 / i));
const pick = () => { const x = rand() * total; let lo = 0, hi = TERMS - 1; while (lo < hi) { const mid = (lo + hi) >> 1; if (cdf[mid] < x) lo = mid + 1; else hi = mid; } return `q${lo + 1}`; };

const cms = new CountMin(0.001, 0.01), exact = new Map(), K = 5;
let top = []; // [term, estimate] kept sorted, at most K long
for (let i = 0; i < N; i++) {
  const term = pick();
  cms.add(term);
  exact.set(term, (exact.get(term) || 0) + 1);
  const est = cms.estimate(term);
  top = top.filter(([t]) => t !== term);
  if (top.length < K || est > top[K - 1][1]) top = [...top, [term, est]].sort((a, b) => b[1] - a[1]).slice(0, K);
}
console.log(`sketch: ${cms.d} rows x ${cms.w} counters = ${(cms.d * cms.w * 4 / 1024).toFixed(0)} KiB | bound eps*N = ${0.001 * N}`);
console.log("top-5 by sketch:", top.map(([t, e]) => `${t}=${e} (true ${exact.get(t)})`).join(", "));
for (const t of ["q10", "q1000", "q50000"]) console.log(`${t.padEnd(6)} true ${String(exact.get(t) ?? 0).padStart(5)} | estimate ${cms.estimate(t)}`);
let worst = 0, sum = 0, under = 0;
for (const [t, c] of exact) { const err = cms.estimate(t) - c; worst = Math.max(worst, err); sum += err; if (err < 0) under++; }
console.log(`over all ${exact.size} terms seen: average over-count ${(sum / exact.size).toFixed(2)}, worst ${worst}, under-counted ${under}`);
console.log(`exact Map would hold ${exact.size} keys; the sketch stays ${cms.d * cms.w} counters whatever the stream`);

sketch: 5 rows x 2719 counters = 53 KiB | bound eps*N = 1000
top-5 by sketch: q1=82993 (true 82876), q2=41357 (true 41228), q3=27697 (true 27597), q4=20496 (true 20389), q5=16783 (true 16695)
q10    true  8307 | estimate 8398
q1000  true    79 | estimate 136
q50000 true     0 | estimate 56
over all 80786 terms seen: average over-count 98.07, worst 500, under-counted 0
exact Map would hold 80786 keys; the sketch stays 13595 counters whatever the stream

> GEOADD places 2.29451 48.85826 eiffel 2.33764 48.86061 louvre
(integer) 2
> GEOHASH places eiffel louvre
1) "u09tunqgcz0"
2) "u09tvny1wv0"
> GEOSEARCH places FROMLONLAT 2.2945 48.8583 BYRADIUS 4 km ASC WITHDIST
1) 1) "eiffel"
   2) "0.0045"
2) 1) "louvre"
   2) "3.1672"

// A point quadtree: a square splits into 4 children once it holds more than CAPACITY points.
const mulberry32 = (a) => () => {
  a = (a + 0x6d2b79f5) | 0;
  let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32;
};
const CAPACITY = 100;

class Quad {
  constructor(x, y, size, depth = 0) { Object.assign(this, { x, y, size, depth, points: [], kids: null }); }
  insert(p) {
    if (this.kids) return this.kids[this.childIndex(p)].insert(p);
    this.points.push(p);
    if (this.points.length > CAPACITY && this.size > 1e-6) { // split: hand every point to a child
      const h = this.size / 2;
      this.kids = [[0, 0], [h, 0], [0, h], [h, h]].map(([dx, dy]) => new Quad(this.x + dx, this.y + dy, h, this.depth + 1));
      for (const q of this.points) this.kids[this.childIndex(q)].insert(q);
      this.points = [];
    }
  }
  childIndex([px, py]) { const h = this.size / 2; return (px >= this.x + h ? 1 : 0) + (py >= this.y + h ? 2 : 0); }
  search(cx, cy, r, out, stats) { // all points within r of (cx, cy)
    const nx = Math.max(this.x, Math.min(cx, this.x + this.size)), ny = Math.max(this.y, Math.min(cy, this.y + this.size));
    if ((nx - cx) ** 2 + (ny - cy) ** 2 > r * r) return; // the circle misses this square: skip it all
    stats.nodes++;
    if (this.kids) for (const k of this.kids) k.search(cx, cy, r, out, stats);
    else for (const p of this.points) { stats.points++; if ((p[0] - cx) ** 2 + (p[1] - cy) ** 2 <= r * r) out.push(p); }
  }
  leaves(acc = []) { if (this.kids) this.kids.forEach((k) => k.leaves(acc)); else acc.push(this); return acc; }
}

// 100,000 places on a 100 km x 100 km map: 70% packed into a 10 km "downtown", the rest spread out.
const rand = mulberry32(5), root = new Quad(0, 0, 100), places = [];
for (let i = 0; i < 100_000; i++) {
  const p = rand() < 0.7 ? [40 + rand() * 10, 40 + rand() * 10] : [rand() * 100, rand() * 100];
  places.push(p);
  root.insert(p);
}
const leaves = root.leaves();
const byDepth = {};
for (const l of leaves) byDepth[l.depth] = (byDepth[l.depth] || 0) + 1;
console.log("leaves:", leaves.length, "| leaves per depth:", JSON.stringify(byDepth));
const cell = (x, y) => leaves.find((l) => x >= l.x && x < l.x + l.size && y >= l.y && y < l.y + l.size);
console.log("leaf downtown is", cell(45, 45).size.toFixed(3), "km wide; leaf in the suburbs is", cell(5, 5).size.toFixed(3), "km wide");

for (const [name, cx, cy] of [["downtown", 45, 45], ["suburbs", 5, 5]]) {
  const out = [], stats = { nodes: 0, points: 0 };
  root.search(cx, cy, 1, out, stats); // radius 1 km
  const brute = places.filter((p) => (p[0] - cx) ** 2 + (p[1] - cy) ** 2 <= 1).length;
  console.log(`${name}: ${out.length} places within 1 km (brute force ${brute}); checked ${stats.points} points in ${stats.nodes} nodes instead of 100,000`);
}

leaves: 3052 | leaves per depth: {"4":20,"5":928,"6":15,"7":27,"8":214,"9":1848}
leaf downtown is 0.195 km wide; leaf in the suburbs is 3.125 km wide
downtown: 2210 places within 1 km (brute force 2210); checked 2937 points in 122 nodes instead of 100,000
suburbs: 12 places within 1 km (brute force 12); checked 25 points in 6 nodes instead of 100,000