Sets and Sorted Sets

The hash structure separated a record’s fields, but every field still belonged to a single record. Some of the library’s questions do not belong to a single record. “Is this book currently among the ones on loan” is a membership question, and its answer is yes or no. “Where does this book rank among the most-borrowed” is a rank question, and its answer is a number, but one read off a sorted whole. Both questions require the same thing: holding in memory which members are present.

The complexity analysis of these structures has already been done elsewhere; what is measured here is bytes held and store semantics.

Membership: Yes or No

DS1: 38,000 books are on loan during the day, the member identifier is 6 bytes; half of the 10,000 membership queries ask about a book that is in the set, half about one that is not. DS2: an array slot is 8 bytes, structure overhead is 56 bytes, overhead per set entry is 48 bytes (bucket pointer, entry structure, hash value, alignment).

// memory/membership.mjs — "is this book currently on loan" in three structures. Steps
// are counted inside the implementation; the workload is deterministic.
const OVERHEAD = 56, SLOT = 8, SET_OVERHEAD = 48;          // DS2
const bl = (x) => Buffer.byteLength(String(x));
const ON_LOAN = 38_000, QUERIES = 10_000, BOOKS = 200_000;
const member = (i) => String(100_000 + (i * 4241) % BOOKS);
const members = [...new Set(Array.from({ length: ON_LOAN }, (_, i) => member(i)))];

class ListMembership {                          // order is preserved, membership is a scan
  #items = []; steps = 0; insertSteps = 0;
  insert(v) { this.insertSteps += 1; this.#items.push(v); }
  has(v) { for (const x of this.#items) { this.steps += 1; if (x === v) return true; } return false; }
  bytes() { return OVERHEAD + this.#items.reduce((t, v) => t + bl(v) + SLOT, 0); }
  get size() { return this.#items.length; }
}
class SortedArrayMembership {                   // binary search; insertion needs shifting
  #items = []; steps = 0; insertSteps = 0;
  #locate(v) { let lo = 0, hi = this.#items.length;
    while (lo < hi) { this.steps += 1; const mid = (lo + hi) >> 1; if (this.#items[mid] < v) lo = mid + 1; else hi = mid; }
    return lo; }
  insert(v) { const i = this.#locate(v); this.insertSteps += this.#items.length - i + 1; this.#items.splice(i, 0, v); }
  has(v) { const i = this.#locate(v); return this.#items[i] === v; }
  bytes() { return OVERHEAD + this.#items.reduce((t, x) => t + bl(x) + SLOT, 0); }
  get size() { return this.#items.length; }
}
class SetMembership {                           // hash: a single step, extra overhead per entry
  #set = new Set(); steps = 0; insertSteps = 0;
  insert(v) { this.insertSteps += 1; this.#set.add(v); }
  has(v) { this.steps += 1; return this.#set.has(v); }
  bytes() { let b = OVERHEAD; for (const v of this.#set) b += bl(v) + SET_OVERHEAD; return b; }
  get size() { return this.#set.size; }
}

const structures = [["list", new ListMembership()], ["sorted array", new SortedArrayMembership()],
  ["set", new SetMembership()]];
for (const [, impl] of structures) for (const v of members) impl.insert(v);

// half the queries ask about a book that is in the set, half about one that is not
const queries = Array.from({ length: QUERIES }, (_, j) =>
  j % 2 === 0 ? members[(j * 7919) % members.length] : String(100_000 + BOOKS + j));
let found = 0;
for (const [, impl] of structures) { let f = 0; for (const q of queries) if (impl.has(q)) f += 1; found = f; }

console.log(`${members.length} books on loan (member ${bl(members[0])} bytes), ${QUERIES} membership queries, ` +
  `${found} found`);
console.log(`${"structure".padEnd(13)}${"bytes held".padStart(14)}${"per entry".padStart(13)}` +
  `${"query steps".padStart(13)}${"per query".padStart(14)}${"insert steps".padStart(14)}`);
for (const [name, impl] of structures)
  console.log(name.padEnd(13) + String(impl.bytes()).padStart(14) + (impl.bytes() / impl.size).toFixed(1).padStart(13) +
    String(impl.steps).padStart(13) + (impl.steps / QUERIES).toFixed(1).padStart(14) +
    String(impl.insertSteps).padStart(14));

38000 books on loan (member 6 bytes), 10000 membership queries, 5000 found
structure        bytes held    per entry  query steps     per query  insert steps
list                 532056         14.0    284642000       28464.2         38000
sorted array         532056         14.0       676550          67.7     360742025
set                 2052056         54.0        10000           1.0         38000

The list and the sorted array hold the same 532,056 bytes, 14.0 per entry. The set demands 2,052,056 bytes for the same 38,000 members — 54.0 per entry, that is, 3.86 times. The difference is a single line item: 40 bytes per member for the bucket pointer and the entry structure. Holding a six-byte book identifier in a set costs nine times the identifier’s own size.

The payoff is in the query column: the list answers each question in an average of 28,464.2 steps, the set in 1. The sorted array looks like an interesting middle ground — 67.7 steps at the list’s memory cost — but the insert column finishes it off. In a sorted array, every insertion shifts the remaining entries: 38,000 insertions cost 360,742,025 steps, 9,493 per insertion. The set of books on loan is not static; during the day, every loan is an insertion and every return is a removal. In this workload, the sorted array gives back what it gains on queries a hundred times over on insertion.

The 1,520,000 extra bytes the set holds bring both the query and the insertion down to a single step. What it loses does not show up in any column: the set does not preserve order. The list carried the 38,000 books in insertion order; the set carries the same books, but there is no information about which was loaned out first. Order is abandoned in exchange for the membership answer.

Rank: Where in the Order

A leaderboard asks two questions at once: what is a book’s score, and where does that score rank. A member-score hash is enough for the first question and is common to all three approaches; the second needs a rank index. DS3: 50,000 books have a popularity score, 10,000 loans increment a score, 2,000 rank queries and 200 “top 20” queries arrive. DS4: the skip list’s node levels come from a generator with a visible seed; the node header is 24 bytes, the pointer pair per level is 16 bytes. The ranks given by all three approaches are checked against brute force.

// memory/ranking.mjs — popular-book ranking: three rank indexes over a member->score
// hash. Skip list levels come from a seeded generator; ranks are checked by brute force.
const OVERHEAD = 56, SLOT = 8, SET_OVERHEAD = 48, NODE = 24, POINTER = 16;   // DS2
const BOOKS = 50_000, UPDATES = 10_000, QUERIES = 2_000, TOP = 20, SEED = 20240115;
const bl = (x) => Buffer.byteLength(String(x));
let c = SEED;
const rand = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

const member = (i) => String(100_000 + i);
const score0 = (i) => 1 + (i * 7919) % 4096;
const before = (score1, member1, score2, member2) => score1 > score2 || (score1 === score2 && member1 < member2);   // score descending, member ascending

class SkipList {
  #head; #level = 1; #n = 0; #maxLevel; steps = 0; pointers = 0;
  constructor(maxLevel = 16) { this.#maxLevel = maxLevel;
    this.#head = { member: "", score: 0, forward: new Array(maxLevel).fill(null), span: new Array(maxLevel).fill(0) }; }
  #pickLevel() { let lvl = 1; while (rand() < 0.5 && lvl < this.#maxLevel) lvl += 1; return lvl; }
  #path(score, member) {
    const update = new Array(this.#maxLevel), rankSum = new Array(this.#maxLevel).fill(0);
    let node = this.#head;
    for (let i = this.#level - 1; i >= 0; i -= 1) {
      rankSum[i] = i === this.#level - 1 ? 0 : rankSum[i + 1];
      while (node.forward[i] && before(node.forward[i].score, node.forward[i].member, score, member)) {
        this.steps += 1; rankSum[i] += node.span[i]; node = node.forward[i]; }
      update[i] = node;
    }
    return [update, rankSum, node.forward[0]];
  }
  insert(member, score) {
    const [update, rankSum] = this.#path(score, member);
    const lvl = this.#pickLevel();
    if (lvl > this.#level) { for (let i = this.#level; i < lvl; i += 1) {
      rankSum[i] = 0; update[i] = this.#head; this.#head.span[i] = this.#n; } this.#level = lvl; }
    const newNode = { member, score, forward: new Array(lvl), span: new Array(lvl) };
    this.pointers += lvl;
    for (let i = 0; i < lvl; i += 1) {
      newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode;
      newNode.span[i] = update[i].span[i] - (rankSum[0] - rankSum[i]); update[i].span[i] = (rankSum[0] - rankSum[i]) + 1;
    }
    for (let i = lvl; i < this.#level; i += 1) update[i].span[i] += 1;
    this.#n += 1;
  }
  remove(member, score) {
    const [update, , node] = this.#path(score, member);
    if (!node || node.member !== member || node.score !== score) return false;
    for (let i = 0; i < this.#level; i += 1) {
      if (update[i].forward[i] === node) { update[i].span[i] += node.span[i] - 1; update[i].forward[i] = node.forward[i]; }
      else update[i].span[i] -= 1;
    }
    this.pointers -= node.forward.length;
    while (this.#level > 1 && this.#head.forward[this.#level - 1] === null) this.#level -= 1;
    this.#n -= 1; return true;
  }
  rank(member, score) { const [, rankSum, node] = this.#path(score, member); return node && node.member === member ? rankSum[0] + 1 : -1; }
  top(k) { const r = []; let node = this.#head.forward[0];
    while (node && r.length < k) { this.steps += 1; r.push(node.member); node = node.forward[0]; } return r; }
  bytes() { let b = OVERHEAD; let node = this.#head.forward[0];
    while (node) { b += bl(node.member) + NODE + node.forward.length * POINTER; node = node.forward[0]; } return b; }
  get level() { return this.#level; }
}

const scores = new Map();                        // member -> score; common to all three approaches
for (let i = 1; i <= BOOKS; i += 1) scores.set(member(i), score0(i));
const scoresBytes = [...scores].reduce((t, [m]) => t + bl(m) + SLOT + SET_OVERHEAD, OVERHEAD);

const sorted = [...scores].map(([m, s]) => [s, m]).sort((a, b) => (before(a[0], a[1], b[0], b[1]) ? -1 : 1));
const skip = new SkipList();
for (const [m, s] of scores) skip.insert(m, s);
let sortedSteps = 0, noIndexSteps = 0;
const locate = (score, m) => { let lo = 0, hi = sorted.length;
  while (lo < hi) { sortedSteps += 1; const mid = (lo + hi) >> 1;
    if (before(sorted[mid][0], sorted[mid][1], score, m)) lo = mid + 1; else hi = mid; } return lo; };

// daily load: score increments, rank queries, top K
const events = Array.from({ length: UPDATES }, (_, j) => member(1 + (j * 4241) % BOOKS));
for (const m of events) {
  const oldScore = scores.get(m), newScore = oldScore + 1;
  const oldPos = locate(oldScore, m); sortedSteps += sorted.length - oldPos; sorted.splice(oldPos, 1);        // shift
  const newPos = locate(newScore, m); sortedSteps += sorted.length - newPos; sorted.splice(newPos, 0, [newScore, m]);
  skip.remove(m, oldScore); skip.insert(m, newScore); scores.set(m, newScore);
}
const queries = Array.from({ length: QUERIES }, (_, j) => member(1 + (j * 7919) % BOOKS));
let matches = 0;
for (const m of queries) {
  const score = scores.get(m);
  let rankNoIndex = 1; for (const [otherMember, otherScore] of scores) { noIndexSteps += 1; if (before(otherScore, otherMember, score, m)) rankNoIndex += 1; }
  const rankSorted = locate(score, m) + 1, rankSkip = skip.rank(m, score);
  if (rankNoIndex === rankSorted && rankSorted === rankSkip) matches += 1;
}
for (let j = 0; j < 200; j += 1) {
  [...scores].sort((a, b) => { noIndexSteps += 1; return before(a[1], a[0], b[1], b[0]) ? -1 : 1; }).slice(0, TOP);
  sortedSteps += TOP; sorted.slice(0, TOP); skip.top(TOP);
}

console.log(`${BOOKS} books, ${UPDATES} score increments, ${QUERIES} rank queries, 200 "top ${TOP}"`);
console.log(`${matches}/${QUERIES} queries: all three approaches gave the same rank; skip list level ${skip.level}, ` +
  `pointers ${skip.pointers} (${(skip.pointers / BOOKS).toFixed(2)} per node), seed ${SEED}`);
const paths = [
  ["no rank index", scoresBytes, noIndexSteps],
  ["sorted array", scoresBytes + OVERHEAD + sorted.reduce((t, [, m]) => t + bl(m) + SLOT + SLOT, 0), sortedSteps],
  ["skip list", scoresBytes + skip.bytes(), skip.steps],
];
console.log(`\n${"rank index".padEnd(17)}${"bytes held".padStart(14)}${"index share".padStart(12)}` +
  `${"per entry".padStart(13)}${"total steps".padStart(13)}`);
for (const [name, b, steps] of paths)
  console.log(name.padEnd(17) + String(b).padStart(14) + String(b - scoresBytes).padStart(12) +
    (b / BOOKS).toFixed(1).padStart(13) + String(steps).padStart(13));

50000 books, 10000 score increments, 2000 rank queries, 200 "top 20"
2000/2000 queries: all three approaches gave the same rank; skip list level 13, pointers 102228 (2.04 per node), seed 20240115

rank index           bytes held index share    per entry  total steps
no rank index           3100056           0         62.0    212473400
sorted array            4200112     1100056         84.0    500247667
skip list               6235760     3135704        124.7      1336074

All three approaches give the same rank in all 2,000 queries; the difference is only in price. If no rank index is held, the hash is 3,100,056 bytes, and every rank query walks every entry while every “top 20” query sorts the entire table: 212,473,400 steps.

The sorted array buys nothing in this workload. It holds 1,100,056 extra bytes and pushes the total step count to 500,247,667 — worse than the no-index path. The reason is the same as in the previous section: while a rank query is cheap with binary search, every score increment shifts an average of twenty-five thousand entries to move the entry out of its old position and into its new one. A sorted array is good for a static table and the wrong choice for a leaderboard that keeps changing.

The skip list holds 3,135,704 extra bytes — 124.7 bytes per entry, more than double the membership set — and brings the total step count down to 1,336,074. Every extra byte it holds prevents 67.3 steps. More than half of those bytes are neither score nor identifier: 102,228 pointer pairs, 2.04 levels per node, 1,635,648 bytes. The rank index’s cost is not the data itself, it is the way of reaching the data in order. In exchange, both the rank query and the “top 20” query become independent of table size, and so does the score update.

Summary

• The membership question is answered correctly by all three structures: the list in 28,464.2 steps, the sorted array in 67.7, the set in 1.0.
• The set holds the same 38,000 members in 2,052,056 bytes; the list and the sorted array in 532,056 bytes. The difference is 40 bytes per member of bucket and entry overhead — nine times the six-byte identifier.
• The sorted array is deceptive for membership: the query is cheap, but 38,000 insertions cost 360,742,025 steps (9,493 per insertion). It is the worst choice for a membership set that keeps changing.
• What the set loses is order: there is no information in the set about which book was loaned out first.
• Holding no rank index for the leaderboard means 3,100,056 bytes and 212,473,400 steps; the sorted array holds 1,100,056 extra bytes and pushes the step count up to 500,247,667, because every score increment requires a shift.
• The skip list holds 3,135,704 extra bytes and brings the step count down to 1,336,074: 67.3 steps per byte. 1,635,648 of those bytes are pure pointers — 2.04 levels per node.

Next Step

Both structures in this lesson gave the correct answer, and both did the same thing: they held exactly what they counted. The set carried the identity of 38,000 books one by one; the sorted set carried the identity, the score, and the rank position of 50,000 books. The same held true in earlier lessons — the hash structure held every field, the list held every entry, the counter held every key, each one individually.

Yet part of the library’s questions do not want the members themselves. “How many distinct members logged in today,” “has anyone ever borrowed this book before,” “on which days was anything loaned out” — the answer to these is a number or a yes-no, not a list of members. While a number is enough for the answer, the cost of holding every member in memory has not been asked in any of these lessons. The next lesson opens that question.