Document Lifecycle

The previous two lessons took in documents once and let them go: a record arrived, a mapping was built, the index was written. The catalog, however, does not stand still. A book’s summary gets corrected, a subject tag changes, a lost book is removed from the catalog. This lesson measures what these three operations do to the index.

The inverted index’s structure imposes a constraint. Posting lists are kept per term and sorted by document id; when a document’s text changes, that document’s entries sit scattered across dozens of separate lists. Correcting these entries in place would mean finding every list and removing one record out of each. Instead, the index does the cheaper thing: it marks the old record dead and appends the new text as a new record at the end. An update is therefore not a separate operation, it is a delete plus an add.

Internal Id and the Delete Marker

This mechanism requires two ids. The external id is the catalog’s book number and never changes. The internal id is the document’s entry order in the index, and a new one is given on every write. Posting lists carry the internal id; the mapping between external id and internal id is kept separately. When a document is updated, the mapping turns to the new internal id, and the old one enters the delete marker.

IA1: the corpus is unchanged — 600 records, seed 20250317; the operation sequence is generated from seed 20250318. IA2: the byte constants are the same as the previous lessons, and position is not kept. IA3: the delete marker is counted as 1 bit per internal id. IA4: every round applies 60 updates, 20 deletes, and 20 adds; once the dead-entry ratio exceeds 20 percent, the index is rewritten from live documents. IA5: dead entries are eliminated from the query result, but they are included in the scanned entries.

// search/catalog.mjs — corpus shared by three topics: generated from a library catalog,
// 600 book records, seed 20250317. Fields: title, summary, subjects, author, year, language, shelf.
export const SEED = 20250317, DOC_COUNT = 600;
let state = SEED;
const random = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;
const pick = (d) => d[Math.floor(random() * d.length)];
const pickSkewed = (d) => d[Math.floor(random() ** 2 * d.length)];   // frequency is skewed in real text
const splitBar = (s) => s.split("|");

// stem forms: base, genitive, plural, dative, ablative, locative
export const STEMS = splitBar("deniz denizin denizler denize denizden denizde|kitap kitabın kitaplar kitaba \
kitaptan kitapta|çocuk çocuğun çocuklar çocuğa çocuktan çocukta|şehir şehrin şehirler şehre \
şehirden şehirde|yol yolun yollar yola yoldan yolda|ada adanın adalar adaya adadan adada|bahçe \
bahçenin bahçeler bahçeye bahçeden bahçede|mektup mektubun mektuplar mektuba mektuptan mektupta|\
gemi geminin gemiler gemiye gemiden gemide|köprü köprünün köprüler köprüye köprüden köprüde|\
okul okulun okullar okula okuldan okulda|kuş kuşun kuşlar kuşa kuştan kuşta").map((s) => s.split(" "));
const PATTERNS = splitBar("0 {} ve gündelik hayat üzerine notlar sunar|0 {} bu derlemenin ana izleğidir|\
1 {} tarihine geniş yer ayırır|1 {} çevresinde gelişen olayları anlatır|2 {} üzerine derlenmiş \
yazılar içerir|2 {} hakkında kısa öyküler toplar|3 {} açılan bir yolculuğu izler|4 {} toplanmış \
belgeleri sıralar|5 {} tutulan günlüklerden seçmeler verir|5 {} geçen bölümleri İstanbul'un eski \
mahallelerine bağlar").map((s) => [Number(s[0]), s.slice(2)]);
const PATTERNS2 = splitBar("{Y} kütüphanesinde tutulan {N} üzerine kuruludur|{N} arasından seçilmiş \
örnekler taşır|{Y} ve çevresindeki {N} listesini verir|{Y} basımı bir {N} derlemesine dayanır");
const EXTRA = splitBar("denizci gelenekleri üzerine bir ek bölüm bulunur|Karadeniz kıyısındaki kasabaları \
anlatır|çocukluk anılarına yer verir|kitapçı raflarındaki dağılımı tartışır|yolculuk notlarıyla \
kapanır|adacıklardaki kuş türlerini sayar");
const PLACES = splitBar("Ankara|İzmir|Trabzon|Kars|Bursa|Edirne|Sinop|Antakya");
const OBJECTS = splitBar("harita|fotoğraf|söyleşi|günlük|arşiv belgesi|liman kaydı|kasaba adı|el yazması|gazete kupürü|şarkı sözü");
const PREFIXES = splitBar("Uzak|Kayıp|Sessiz|Eski|Kısa|Büyük|Küçük|Unutulmuş|Beyaz|Yedi");
const SUFFIXES = splitBar("Günleri|Öyküleri|Üzerine Notlar|Anıları|Sözlüğü|Rehberi|Yılları|Defteri");
const SUBJECTS = splitBar("çocuk edebiyatı|roman|kısa öykü|şiir|deniz tarihi|coğrafya|biyografi|gezi yazısı|halk bilimi|mimarlık|müzik|felsefe");
const FIRST_NAMES = splitBar("Ahmet|Ayşe|Zeynep|Cemal|Nuran|Selim|Elif|Kerem|Hatice|Bedri|Sevgi|Nazlı");
const LAST_NAMES = splitBar("Yılmaz|Kaya|Demir|Şahin|Çelik|Aydın|Doğan|Arslan|Koç|Ertem");
const LANGUAGES = splitBar("Türkçe|Türkçe|Türkçe|İngilizce|Almanca|Fransızca");

const capitalize = (s) => s[0].toLocaleUpperCase("tr") + s.slice(1);
function generateSummary() {
  const parts = [];
  for (let i = 0; i < 3; i += 1) { const [d, k] = pickSkewed(PATTERNS); parts.push(k.replace("{}", pickSkewed(STEMS)[d])); }
  parts.push(pick(PATTERNS2).replace("{Y}", pick(PLACES)).replace("{N}", pick(OBJECTS)));
  if (random() < 0.45) parts.push(pick(EXTRA));
  return capitalize(parts.join(", ")) + ".";
}
function generateTitle() {
  const k = pickSkewed(STEMS), o = pick(PREFIXES), s = pick(SUFFIXES), t = random();
  if (t < 0.25) return `${o} ${capitalize(k[2])}`;
  if (t < 0.5) return `${capitalize(k[0])} ${s}`;
  if (t < 0.75) return `${o} ${capitalize(k[0])} ${s}`;
  return `${capitalize(k[1])} ${s}`;
}
export const corpus = [];
for (let i = 1; i <= DOC_COUNT; i += 1) {
  const subjects = [pick(SUBJECTS)];
  if (random() < 0.55) subjects.push(pick(SUBJECTS));
  if (random() < 0.2) subjects.push(pick(SUBJECTS));
  corpus.push({
    id: i, title: generateTitle(), summary: generateSummary(), subjects: [...new Set(subjects)], author: `${pick(FIRST_NAMES)} ${pick(LAST_NAMES)}`,
    year: 1968 + Math.floor(random() * 57), language: pick(LANGUAGES),
    shelf: `${pick(splitBar("TR|EN|DE|FR"))}-${800 + Math.floor(random() * 99)}.${Math.floor(random() * 9)}`,
  });
}

// search/index.mjs — a hand-written inverted index: dictionary, posting list (document id, term
// frequency, position) and byte accounting. The analyzer is supplied from outside; later lessons use it.
export const SIMPLE = (s) => s.toLocaleLowerCase("tr").split(/[^\p{L}\p{N}]+/u).filter(Boolean);
export const DOC_ID_BYTES = 4, FREQ_BYTES = 4, POSITION_BYTES = 4, DICTIONARY_OVERHEAD = 8;   // IA2: byte constants

export class InvertedIndex {
  dictionary = new Map();                // term -> posting list
  documentCount = 0;
  constructor({ analyze = SIMPLE, frequency = true, position = true } = {}) { Object.assign(this, { analyze, frequency, position }); }

  add(id, text) {
    const local = new Map();
    this.analyze(text).forEach((t, i) => (local.get(t) ?? local.set(t, []).get(t)).push(i));
    for (const [t, k] of local) {
      if (!this.dictionary.has(t)) this.dictionary.set(t, []);
      this.dictionary.get(t).push({ id, tf: k.length, position: this.position ? k : [] });
    }
    this.documentCount += 1;
  }

  postings(t) { return this.dictionary.get(t) ?? []; }

  search(...terms) {                     // intersection: lists are id-sorted, so one pass suffices
    const l = terms.map((t) => this.postings(t)), p = l.map(() => 0), results = [];
    let comparisons = 0;
    while (l.every((x, i) => p[i] < x.length)) {
      const maxId = Math.max(...l.map((x, i) => x[p[i]].id));
      let matched = true;
      for (let i = 0; i < l.length; i += 1) {
        while (p[i] < l[i].length && l[i][p[i]].id < maxId) { p[i] += 1; comparisons += 1; }
        comparisons += 1;
        if (p[i] >= l[i].length || l[i][p[i]].id !== maxId) { matched = false; break; }
      }
      if (matched) { results.push(maxId); p.forEach((_, i) => (p[i] += 1)); }
    }
    return { results, postings: l.reduce((t, x) => t + x.length, 0), comparisons };
  }

  bytes() {                              // dictionary + postings + positions
    let s = 0, g = 0, k = 0, postings = 0, positions = 0;
    for (const [t, list] of this.dictionary) {
      s += Buffer.byteLength(t) + DICTIONARY_OVERHEAD;
      for (const gr of list) {
        g += DOC_ID_BYTES + (this.frequency ? FREQ_BYTES : 0);
        k += gr.position.length * POSITION_BYTES;
        postings += 1; positions += gr.position.length;
      }
    }
    return { terms: this.dictionary.size, postings, positions, dictionary: s, postingBytes: g, positionBytes: k, total: s + g + k };
  }
}

// search/lifecycle.mjs — document lifecycle: add, update (delete + add), and delete. Dead posting
// entries, delete marker bytes, entries eliminated at query time, and cleanup rounds are counted.
import { corpus, DOC_COUNT, SEED } from "./catalog.mjs";
import { InvertedIndex, SIMPLE, DOC_ID_BYTES, FREQ_BYTES } from "./index.mjs";

let c = SEED + 1;
const random = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

class Store {                                  // document lifecycle layered on top of the inverted index
  #index = new InvertedIndex({ position: false });
  #internal = new Map();                       // external id -> internal id (index entry order)
  #text = new Map();
  #deleted = new Set();                        // delete marker: dead internal ids
  counter = 0;
  add(external, text) {                        // this is also how an update works: the old internal id is marked dead
    this.counter += 1;
    if (this.#internal.has(external)) this.#deleted.add(this.#internal.get(external));
    this.#internal.set(external, this.counter); this.#text.set(external, text);
    this.#index.add(this.counter, text);
  }
  delete(external) { this.#deleted.add(this.#internal.get(external)); this.#internal.delete(external); this.#text.delete(external); }
  search(term) {                               // dead internal ids are eliminated from the result
    const l = this.#index.postings(term), reverse = new Map([...this.#internal].map(([d, i]) => [i, d]));
    const live = l.filter((g) => reverse.has(g.id));
    return { results: live.map((g) => reverse.get(g.id)), postings: l.length, eliminated: l.length - live.length };
  }
  rank(external, term) { const k = this.search(term).results.indexOf(external); return k < 0 ? "-" : `${k + 1}`; }
  measure() {
    const b = this.#index.bytes();
    const dead = [...this.#index.dictionary.values()].flat().filter((g) => this.#deleted.has(g.id)).length;
    return { live: this.#internal.size, terms: b.terms, postings: b.postings, dead, index: b.total,
      marker: Math.ceil(this.counter / 8), share: Math.round(dead * 100 / b.postings) };
  }
  cleanup() {                                 // the index is rewritten from live documents only
    const live = [...this.#text];
    this.#index = new InvertedIndex({ position: false }); this.#internal = new Map(); this.#deleted = new Set();
    this.counter = 0;
    for (const [d, m] of live) this.add(d, m);
  }
}

const text = (b) => `${b.title} ${b.summary}`;
const store = new Store();
for (const b of corpus) store.add(b.id, text(b));
const initial = store.measure();
console.log(`seed ${SEED}; ${DOC_COUNT} docs added to the index: ${initial.terms} terms, ${initial.postings} posting ` +
  `entries, ${initial.index} bytes, delete marker ${initial.marker} bytes (1 bit per internal id)`);

// --- the mechanics of updating a single document ---
const target = corpus.find((b) => SIMPLE(text(b)).includes("kuş"));
const df = (t) => store.search(t).results.length;
const shared = [...new Set(SIMPLE(text(target)))].filter((t) => t !== "kuş").sort((a, b) => df(b) - df(a))[0];
console.log(`\n#${target.id} "${target.title}": the summary's "kuş" token is being replaced with "martı"`);
console.log(`  before: "kuş" ${df("kuş")} docs (this doc ranks ${store.rank(target.id, "kuş")}), ` +
  `"martı" ${df("martı")} docs, ranks ${store.rank(target.id, shared)} in the "${shared}" query`);
store.add(target.id, SIMPLE(text(target)).map((t) => (t === "kuş" ? "martı" : t)).join(" "));
console.log(`  after : "kuş" ${df("kuş")} docs (this doc ranks ${store.rank(target.id, "kuş")}), ` +
  `"martı" ${df("martı")} docs, ranks ${store.rank(target.id, shared)} in the "${shared}" query`);
const k = store.search("kuş"), o = store.search(shared);
console.log(`  "kuş" posting list carries ${k.postings} entries, ${k.eliminated} of them eliminated and dropped; ` +
  `"${shared}" list has ${o.eliminated} eliminated entries`);

// --- rounds: each round applies 60 updates, 20 deletes, 20 adds; cleanup once the dead share passes 20% ---
console.log(`\n${"round".padStart(5)}${"ops".padStart(7)}${"live docs".padStart(13)}${"postings".padStart(9)}` +
  `${"dead entries".padStart(13)}${"dead %".padStart(7)}${"index bytes".padStart(12)}${"marker".padStart(8)}${"after cleanup".padStart(18)}`);
let next = DOC_COUNT + 1, ops = 0;
for (let round = 1; round <= 6; round += 1) {
  for (let i = 0; i < 60; i += 1) {
    const b = corpus[Math.floor(random() * DOC_COUNT)];
    store.add(b.id, `${text(b)} correction ${round}`);
  }
  for (let i = 0; i < 20; i += 1) store.delete(1 + Math.floor(random() * DOC_COUNT));
  for (let i = 0; i < 20; i += 1) { const b = corpus[Math.floor(random() * DOC_COUNT)]; store.add(next, text(b)); next += 1; }
  ops += 100;
  const s = store.measure(), clean = s.share > 20;
  if (clean) store.cleanup();
  console.log(String(round).padStart(5) + String(ops).padStart(7) + String(s.live).padStart(13) +
    String(s.postings).padStart(9) + String(s.dead).padStart(13) + `%${s.share}`.padStart(7) +
    String(s.index).padStart(12) + String(s.marker).padStart(8) +
    (clean ? `${store.measure().index} bytes` : "-").padStart(18));
}
const final = store.measure();
console.log(`\nfinal state: ${final.live} live docs, ${final.postings} posting entries, ${final.dead} dead entries, ` +
  `${final.index} bytes; started at ${DOC_COUNT} docs holding ${initial.index} bytes`);

seed 20250317; 600 docs added to the index: 185 terms, 14609 posting entries, 119722 bytes, delete marker 75 bytes (1 bit per internal id)

#10 "Denizin Günleri": the summary's "kuş" token is being replaced with "martı"
  before: "kuş" 92 docs (this doc ranks 1), "martı" 0 docs, ranks 7 in the "üzerine" query
  after : "kuş" 91 docs (this doc ranks -), "martı" 1 docs, ranks 509 in the "üzerine" query
  "kuş" posting list carries 92 entries, 1 of them eliminated and dropped; "üzerine" list has 1 eliminated entries

round    ops    live docs postings dead entries dead % index bytes  marker     after cleanup
    1    100          600    16679         1996    %12      136323      86                 -
    2    200          603    18729         3856    %21      152732      96      121884 bytes
    3    300          607    16961         1926    %11      138597      86                 -
    4    400          616    19029         3699    %19      155150      96                 -
    5    500          625    21052         5451    %26      171343     106      127721 bytes
    6    600          635    17733         1758    %10      144786      89                 -

final state: 635 live docs, 17733 posting entries, 1758 dead entries, 144786 bytes; started at 600 docs holding 119722 bytes

The Trace a Single Update Leaves

The second section follows a single document. The token kuş in record #10’s summary is replaced with martı, and three numbers move at once. The kuş query drops from 92 documents to 91; this document is no longer in the set. The martı query rises from 0 documents to 1. Up to this point, this is the expected behavior.

The third number is unexpected. In the üzerine query, a term of the document that did not change, the record drops from rank 7 to rank 509. Nothing about that term changed in its text, and the reason it moves to the end of the order is the internal id: an update gives a new internal id, the new id is the largest one, and because posting lists are kept in id order, the new entry is appended to the end of the list. Correcting a single typo changes that document’s place in every one of its result lists.

The last line shows the price of the dead entry. The kuş posting list still carries 92 entries; the query reads all 92 of them, eliminates 1, and returns 91 documents. The deleted document does not leave the index, it is only eliminated from the result. The delete marker is very cheap in return: 75 bytes for 600 documents, one bit per internal id.

Rounds and Cleanup

The third section follows what the same store does over six rounds. Every round applies 60 updates, 20 deletes, and 20 adds; that is, 80 of the round’s operations leave a dead entry in the index. By the end of the first round, the index carries 1,996 of 16,679 entries dead (12 percent) and has grown from 119,722 bytes to 136,323 bytes. The live document count is still 600 — the entire growth is waste.

In the second round the ratio rises to 21 percent, and because the threshold is exceeded, the index is rewritten from live documents: 152,732 bytes drops to 121,884 bytes, recovering 30,848 bytes. The same cycle repeats in the fifth round; there the ratio reaches 26 percent, the index climbs to 171,343 bytes, and cleanup brings it down to 127,721 bytes. In the fourth round the ratio stays at 19 percent, so no cleanup runs, and 3,699 dead entries carry over for another round: the threshold is a decision about how much waste gets allowed to accumulate.

By the end of the six rounds the store holds 635 live documents and takes up 144,786 bytes. The initial 600 documents held 119,722 bytes; while the document count grew 6 percent, the index grew 21 percent. The gap is the 1,758 dead entries that will carry over to the next cleanup. Delete and update are not free in the index: their cost is not paid instantly, it is paid accumulating across rounds.

Summary

• In the inverted index, an update is not an in-place correction: the old internal id is marked dead, and the new text is appended as a new record with a new internal id at the end. A delete only places a marker.
• The delete marker is cheap — 75 bytes for 600 documents, one bit per internal id — but the entries it marks stay in the index: the kuş query reads 92 entries and returns 91 documents.
• An update changes both the set and the order: record #10 leaves the kuş set, enters the martı set, and drops from rank 7 to rank 509 in the üzerine query, which never changed at all.
• Dead entries accumulate round by round: over 100 operations the index grows from 119,722 bytes to 136,323 bytes and 12 percent of its entries are dead; once the threshold is exceeded, a rewrite brings 152,732 bytes down to 121,884 bytes.
• By the end of six rounds the document count grew 6 percent while the index grew 21 percent; the gap is the 1,758 dead entries carried over to the next cleanup.

Next Step

This topic built the index from the ground up: text was turned into terms, the structure mapping term to document was written, field types were decided, and a document became able to enter and leave the index. On the query side, though, only a single pattern was used. Every question in this topic consisted of bare terms, combined by a single rule — that all of them must be present. Whether a condition was optional, whether a condition excluded a document, whether two words were searched for side by side, or whether a year range was given — none of this was asked. Which order the result came back in was never chosen either: the order was, every time, the posting list’s own layout, and this lesson’s last measurement showed how arbitrary that layout is. The next topic starts from here — how conditions combine, which measure the result is sorted by, and how both decisions change the set and the order.