--- title: 'Document Lifecycle' source: 'https://academia.sh/en/courses/search-engines/document-lifecycle' course: 'Search Engines and Text Retrieval' language: en updated: '2026-08-23T07:00:49+00:00' license: 'CC BY-SA 4.0' --- # Document Lifecycle A document entering, changing, and leaving the index: an update happening as a delete plus an add, old posting entries staying in place, the room a delete marker takes per internal id, dead entries being filtered out at query time while adding to the scanned count, an updated document moving to the end of the result order, and how bloated the index gets before a cleanup round. 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. ```js // 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)}`, }); } ``` ```js // 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 }; } } ``` ```js // 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.