--- title: 'Inverted Index' source: 'https://academia.sh/en/courses/search-engines/inverted-index' course: 'Search Engines and Text Retrieval' language: en updated: '2026-08-23T07:00:49+00:00' license: 'CC BY-SA 4.0' --- # Inverted Index Building the structure that maps term to document and its byte accounting: the distinction between the dictionary and the posting list, pricing the document id, term frequency, and position information in a posting entry separately, measuring the index's ratio to the source text across three formats, the effect of keeping posting lists in document id order on intersection cost, and the adjacency distinction that position information buys. The previous lesson used the inverted index as a black box: a term went in, document ids came out. This lesson opens the box. The structure has two parts. The **dictionary** holds each distinct term in the corpus exactly once and places a pointer next to each term to that term's list. The **posting list** is the record of the documents the term appears in: each entry reports one document. In this course, a **posting** is an index record that reports a term's occurrence in a particular document. The same word names a message published in another curriculum; that usage is unrelated to this one. A posting entry carries at minimum the document id, and may optionally carry **how many times** the term occurs in that document (term frequency) and **where** it occurs (position). All three components carry a cost, and this lesson counts that cost. ## Dictionary, Postings, and Position A sorted index is built on the entire value and goes from a record to a value; the inverted index does the opposite, going from a term to a set of documents, which is why the same document appears in dozens of posting lists at once. That is the difference in one sentence, and it is also what determines index size: the index's size does not scale with the number of documents, it scales with **the number of distinct terms per document**. **IA1:** the corpus is the same corpus as the previous lesson — 600 book records, seed 20250317. **IA2:** the byte accounting uses the following constants — a dictionary entry costs the term's UTF-8 bytes plus 8 bytes (document frequency and a list pointer), a posting entry costs 4 bytes for the document id, 4 more bytes if term frequency is stored, and 4 bytes per position. **IA3:** the indexed text is the union of the `title` and `summary` fields; the previous lesson indexed only the `summary` field, so the term count differs there. ```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/index-measurement.mjs — the same corpus is built in three index formats: id only, // id+frequency, id+frequency+position. Term, posting entry, byte, scanned entry and comparisons are counted. import { corpus, DOC_COUNT, SEED } from "./catalog.mjs"; import { InvertedIndex } from "./index.mjs"; const text = (b) => `${b.title} ${b.summary}`; // IA3: indexed fields const source = corpus.reduce((t, b) => t + Buffer.byteLength(text(b)), 0); const build = (settings) => { const d = new InvertedIndex(settings); for (const b of corpus) d.add(b.id, text(b)); return d; }; const formats = [["id only", { frequency: false, position: false }], ["id + freq", { frequency: true, position: false }], ["id + freq + position", {}]]; console.log(`seed ${SEED}; corpus ${DOC_COUNT} docs, indexed text ${source} bytes`); console.log(`${"index format".padEnd(24)}${"terms".padStart(7)}${"postings".padStart(9)}${"positions".padStart(10)}` + `${"dictionary".padStart(11)}${"posting bytes".padStart(15)}${"position bytes".padStart(15)}${"total".padStart(9)}${"share of text".padStart(14)}`); let full; for (const [label, settings] of formats) { const d = build(settings), b = d.bytes(); full = d; console.log(label.padEnd(24) + String(b.terms).padStart(7) + String(b.postings).padStart(9) + String(b.positions).padStart(10) + String(b.dictionary).padStart(11) + String(b.postingBytes).padStart(15) + String(b.positionBytes).padStart(15) + String(b.total).padStart(9) + `%${(b.total * 100 / source).toFixed(1)}`.padStart(14)); } const first = full.postings("deniz").slice(0, 3).map((g) => `(#${g.id}, tf ${g.tf}, position ${g.position.join("-")})`); console.log(`\n"deniz" posting list ${full.postings("deniz").length} entries; first three: ${first.join(" ")}`); const tfDistribution = new Map(); for (const g of full.postings("deniz")) tfDistribution.set(g.tf, (tfDistribution.get(g.tf) ?? 0) + 1); console.log(`term frequency distribution: ${[...tfDistribution].sort().map(([t, n]) => `tf ${t} -> ${n} docs`).join(", ")}`); // comparison with an unsorted list: for each entry, a linear search through the other list const unsorted = (...t) => { const lists = t.map((x) => full.postings(x)), shortest = lists.reduce((a, x) => (x.length < a.length ? x : a)); let comparisons = 0; const matches = shortest.filter((g) => lists.every((x) => { for (const y of x) { comparisons += 1; if (y.id === g.id) return true; } return false; })); return { n: matches.length, comparisons }; }; console.log(`\n${"query".padEnd(20)}${"entries scanned".padStart(16)}${"id-sorted".padStart(12)}` + `${"unsorted".padStart(10)}${"docs returned".padStart(15)}${"first three ids".padStart(18)}`); for (const terms of [["deniz"], ["çocuk"], ["deniz", "çocuk"], ["deniz", "çocuk", "kitap"]]) { const result = full.search(...terms), unsortedComparisons = terms.length > 1 ? String(unsorted(...terms).comparisons) : "-"; console.log(terms.join("+").padEnd(20) + String(result.postings).padStart(16) + String(result.comparisons).padStart(12) + unsortedComparisons.padStart(10) + String(result.results.length).padStart(15) + result.results.slice(0, 3).join(",").padStart(18)); } // what position information buys: appearing in the same document versus appearing side by side const [termA, termB] = ["deniz", "günleri"]; const secondPositions = new Map(full.postings(termB).map((g) => [g.id, g.position])); const adjacent = full.postings(termA).filter((g) => secondPositions.has(g.id) && g.position.some((x) => secondPositions.get(g.id).some((y) => y - x === 1))).map((g) => g.id); console.log(`\n"${termA} ${termB}": same document ${full.search(termA, termB).results.length}, adjacent ${adjacent.length} docs ` + `(${adjacent.slice(0, 3).map((i) => `#${i} ${corpus[i - 1].title}`).join(", ")})`); ``` ``` seed 20250317; corpus 600 docs, indexed text 135824 bytes index format terms postings positions dictionary posting bytes position bytes total share of text id only 185 14609 0 2850 58436 0 61286 %45.1 id + freq 185 14609 0 2850 116872 0 119722 %88.1 id + freq + position 185 14609 16565 2850 116872 66260 185982 %136.9 "deniz" posting list 261 entries; first three: (#3, tf 1, position 0) (#4, tf 1, position 14) (#7, tf 1, position 14) term frequency distribution: tf 1 -> 206 docs, tf 2 -> 52 docs, tf 3 -> 3 docs query entries scanned id-sorted unsorted docs returned first three ids deniz 261 261 - 261 3,4,7 çocuk 84 84 - 84 5,6,8 deniz+çocuk 345 470 19622 25 8,67,77 deniz+çocuk+kitap 452 630 22135 3 158,309,491 "deniz günleri": same document 23, adjacent 10 docs (#3 Deniz Günleri, #123 Büyük Deniz Günleri, #154 Beyaz Deniz Günleri) ``` ## Three Formats, Three Prices The first table indexes the same 600 documents three times, and the only thing that changes is what the posting entry carries. The dictionary is identical across all three: 185 terms, 2,850 bytes. The index's weight is not in the dictionary, it is in the **14,609 posting entries**. When only the document id is stored, the index is 61,286 bytes, about 45.1 percent of the source text. Adding term frequency exactly doubles the posting section, and the index reaches 119,722 bytes, 88.1 percent of the text. Adding position brings it to 185,982 bytes — **larger than the text itself**. This last line is the lesson's most concrete result: an inverted index that keeps position can take up more space than the text it indexes. The reason shows up in the second and third columns — against 14,609 posting entries there are 16,565 position records, because a term can occur more than once in the same document. The frequency distribution of the term `deniz` counts this directly: once in 206 documents, twice in 52 documents, three times in 3 documents. ## Order Is a Decision Posting lists are kept in document id order, and this is not a preference, it is a decision that determines how the intersection works. The `deniz+çocuk` query reads two lists of 261 and 84 entries, 345 entries total. Because both lists are sorted, the intersection runs in a single pass, and **470 comparisons** are enough. If the same intersection ran on unsorted lists, each entry of the shorter list would require a search from the start of the longer list: **19,622 comparisons**, forty times more. For the three-term query, the ratio is 630 against 22,135. The order's second consequence shows up in the returned set. `deniz` alone returns 261 documents, `çocuk` returns 84; their intersection drops to 25 documents, and to 3 once a third term is added. Every condition narrows the set, and the cost of narrowing is a growing entry count: from 345 to 452. The returned documents arrive in the order `8, 67, 77`; this order is again document id, that is, the order documents entered the index. Which document is more relevant is still not asked. ## What Position Buys Position information is the index's most expensive component — 66,260 bytes on its own, 35.6 percent of the index. In return it buys exactly one thing: knowing whether two terms sit **next to each other** in a document. The last line counts this. The terms `deniz` and `günleri` occur together in 23 documents; only 10 of these documents have the two terms adjacent, and the titles of those 10 documents genuinely follow the pattern `Deniz Günleri`. An index that does not keep position cannot tell the two sets apart and returns all 23 documents. The decision is put this way: 66,260 bytes buys a 13-document narrowing. Whether that narrowing is worth it in a catalog search depends on the type of question — for a reader searching for a book by two words without knowing its exact title, the adjacency distinction gives the correct result directly. The query form that uses this distinction is built in the second topic; this lesson only shows that the data sits in the index and what it holds. ## Summary - The inverted index has two parts: the dictionary (185 terms, 2,850 bytes) and the posting lists (14,609 entries). The weight sits on the posting side; the dictionary is about 1.5 percent of the index. - What a posting entry carries sets the price: id only costs 61,286 bytes (45.1 percent of the text), adding term frequency costs 119,722 bytes (88.1 percent), adding position costs 185,982 bytes (136.9 percent) — the index becomes larger than the source text. - 16,565 position records fall against 14,609 posting entries; the term `deniz` occurs once in 206 documents, twice in 52, three times in 3. - Keeping posting lists in document id order reduces the intersection to a single pass: `deniz+çocuk` finishes in 470 comparisons, against 19,622 comparisons on an unsorted list. - Position information costs 66,260 bytes and buys the ability to narrow the set from 23 documents to 10 in the `deniz günleri` query. ## Next Step This lesson's index split text into words with a single rule: split on every character that is not a letter or digit, then lowercase using Turkish rules. That rule itself was never questioned. Yet `denizler` and `deniz` become two separate terms because of this rule, and the 43-document loss from the first lesson comes from exactly this. The next lesson indexes the same corpus with three separate analyzer chains — raw, lowercasing, and stemming with a stop-word filter — and runs the same query on all three: the returned set, order, and index size are measured side by side across the three configurations.