Indexing and Data Structures

Introduction

Information retrieval systems must locate relevant documents rapidly in collections that may contain millions or billions of items. A naïve system scans every document for every query. If a collection contains N documents and a query requires examining each document, query processing is approximately O(N) before ranking is even considered. This approach is unsuitable for large-scale search.

Indexing solves this problem by performing expensive work during ingestion and storing structures that support efficient retrieval. The central structure is the inverted index, which maps terms to the documents containing them. Modern retrieval systems extend this basic idea with dictionaries, postings lists, positional information, skip structures, compression, segment management, and update pipelines.

Index design is a systems problem involving competing objectives. Larger indexes may support richer ranking and phrase queries but consume more storage and memory. Compression reduces I/O but requires CPU time. Frequent updates improve freshness but create merging and consistency costs. A professional information retrieval engineer must therefore evaluate not only correctness, but also latency, throughput, scalability, durability, and operational complexity.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain the architecture and purpose of an inverted index.
2. Construct dictionaries, postings lists, and positional indexes.
3. Apply skip structures to conjunctive query processing.
4. Explain dictionary and postings-list compression schemes.
5. Design update pipelines using immutable segments and merging.
6. Analyse storage, latency, and scalability trade-offs.
7. Select suitable structures for phrase search, ranking, filtering, and distributed retrieval.

1. The Inverted Index

A document collection is commonly represented as a set D = {d₁, d₂, …, dₙ}. After tokenisation and normalization, each document contains a sequence of terms. The inverted index reverses the document-to-term relationship:

For example, consider:

The index may contain:

A query for “data retrieval” can be processed by intersecting the postings lists for data and retrieval. Instead of scanning all text, the system examines only the relevant lists.

The inverted index has two principal components:

• Dictionary (lexicon): the set of indexed terms and metadata such as document frequency and a pointer to each postings list.
• Postings: occurrences of each term, usually represented by document identifiers and, when required, frequencies, positions, fields, or payloads.

A term’s document frequency, written df(t), is the number of documents containing term t. Its collection frequency, written cf(t), is the total number of occurrences of t across the collection. These values are different: a term may occur many times in a small number of documents or once in many documents.

1.1 Index construction

A standard indexing pipeline consists of the following stages:

1. Document acquisition: obtain documents and metadata.
2. Parsing: identify fields such as title, body, author, and date.
3. Tokenisation: split text into tokens.
4. Normalization: apply case folding, Unicode normalization, and optionally accent handling.
5. Stop-word processing: remove or retain frequent function words according to the retrieval task.
6. Stemming or lemmatization: conflate related word forms when appropriate.
7. Term-document generation: emit pairs such as (term, document identifier).
8. Sorting: order pairs by term and document identifier.
9. Inversion: group sorted pairs into postings lists.
10. Encoding and storage: compress and write the dictionary and postings.

A crucial engineering principle is that linguistic processing must be consistent between indexing and querying. If “retrieval” is stemmed during indexing but not during query processing, expected matches may be lost.

1.2 In-memory and external indexing

For a small collection, an in-memory dictionary can accumulate postings directly. For a large collection, all term-document pairs cannot fit in memory. An external-memory indexer creates sorted temporary blocks, writes them to disk, and merges them.

If a block contains B term-document pairs and the complete collection produces P pairs, approximately ⌈P/B⌉ initial blocks are created. A multiway merge then combines them. The exact I/O cost depends on block size, number of merge passes, storage technology, and buffering. Larger blocks generally reduce merge overhead but require more memory.

A typical implementation stores postings in document-identifier order. This order enables efficient intersection, compression through gaps, and skipping.

2. Dictionaries and Lexicons

The dictionary answers questions such as:

• Does a term exist?
• Where is its postings list stored?
• What is its document frequency?
• Is the term associated with a field, type, or feature?

Common dictionary structures include sorted arrays, hash tables, tries, finite-state transducers, and minimal perfect hashing.

For a sorted dictionary of V terms, binary search requires O(log V) comparisons. A hash table has expected O(1) lookup under suitable hashing and load-factor assumptions, but does not naturally support alphabetical range queries.

The dictionary may be kept partly or wholly in memory. Since every query often requires several term lookups, dictionary latency is important. A compact representation can improve cache locality even if it requires a few more operations.

3. Postings Lists

A postings list records the documents associated with a term. At its simplest, it is an increasing sequence of document identifiers:

For ranked retrieval, postings often contain additional information:

• term frequency in the document;
• field identifier;
• positions;
• impact score or quantized weight;
• document-level features or payloads.

A conceptual posting may therefore be represented as:

The appropriate representation depends on the query workload. Boolean filtering may need only document identifiers. BM25-style ranking generally needs term frequency and document statistics. Phrase queries need positions.

3.1 Boolean intersection

To evaluate a conjunctive query such as “data AND retrieval,” postings lists are intersected. The classic two-pointer algorithm advances the pointer whose current document identifier is smaller. If the lists have lengths a and b, the worst-case time is O(a + b), assuming constant-time identifier comparison.

The shorter list is usually selected first for candidate generation. If one list has one million entries and another has one hundred entries, beginning with the shorter list can substantially reduce subsequent work, especially when additional filtering is applied.

3.2 Query-at-a-time and document-at-a-time processing

In query-at-a-time or term-at-a-time processing, one postings list is processed across many candidate documents before moving to the next term. This can be efficient for accumulator-based ranking and vectorized operations.

In document-at-a-time processing, the system advances several postings iterators together and evaluates one candidate document at a time. This approach can support early termination when postings are ordered by impact or score. The choice depends on ranking algorithm, hardware, compression format, and whether top-k results are required.

4. Positional Indexes and Phrase Search

A non-positional index can determine that two terms occur in the same document but not whether they occur next to one another. A positional index stores token positions for each term.

For example:

The phrase “information retrieval” matches because retrieval occurs at the position immediately following information. A phrase of length m can be checked by testing whether position sequences form consecutive runs with the required order.

Positions may be stored as absolute values or as gaps. For positions 3, 8, and 10, the positional gaps may be 3, 5, and 2, depending on whether the first gap is measured from zero or one. The convention must be fixed and documented because decoding depends on it.

Positional indexes increase storage and indexing cost. They are essential for exact phrase search, proximity scoring, passage retrieval, and some structural ranking features. If the application does not support these operations, omitting positions may be a worthwhile optimization.

Fields provide another form of structure. A title posting and a body posting may be kept separately or annotated with field identifiers. This supports queries such as “term in title” and field-weighted ranking.

5. Skip Structures

When intersecting long postings lists, a system need not inspect every document identifier. A skip pointer allows an iterator to jump forward when it is known that intervening values cannot match.

Suppose one list contains [3, 7, 12, 18, 25, 31] and another contains [3, 12, 25]. A skip from 3 to 12 or from 12 to 25 may reduce comparisons. When the current identifier in one list is smaller than the current identifier in the other, the algorithm follows a skip if the skip target does not exceed the other list’s current identifier.

Skip structures are most useful for long lists and conjunctive queries. They introduce extra storage and decoding work, and their benefit depends on list lengths, query distribution, and hardware. A traditional heuristic places roughly √L skips in a list of length L, but this is not a universal optimum. Modern systems may use skip blocks, block-max indexes, SIMD-friendly block metadata, or learned navigation structures instead.

Block-max indexes store an upper bound on scores within each postings block. During top-k retrieval, a block whose maximum possible score cannot beat the current threshold can be skipped. This is different from Boolean skipping: it uses ranking bounds rather than only document identifiers.

6. Compression of Index Structures

Compression reduces storage consumption and disk and memory bandwidth. It can also improve latency because fewer bytes must be transferred, although decoding consumes CPU resources.

6.1 Gap encoding

Because document identifiers in a postings list are increasing, storing differences is more efficient than storing full identifiers. For document identifiers [100, 105, 119, 120], the gaps are [100, 5, 14, 1]. Small gaps usually require fewer encoded bits.

The first value is often stored as an initial document identifier; subsequent values are reconstructed cumulatively:

Here dᵢ is the reconstructed document identifier and gapᵢ is the encoded difference. This equation assumes postings are strictly increasing and that the first value is separately initialized.

6.2 Variable-byte coding

Variable-byte coding represents an integer using one or more bytes. Seven bits per byte hold data and one bit indicates whether the byte is the final byte. Small integers therefore occupy fewer bytes. It is simple and fast, though not always optimal in bit density.

6.3 Unary and gamma coding

Unary coding represents a positive integer n using n−1 zeros followed by one, or the reverse convention. It is simple but inefficient for large values.

Elias gamma coding represents a positive integer n using the binary length information followed by the remaining binary bits. It is attractive when gap distributions contain many small values, but decoding may be slower than byte-oriented methods.

6.4 Rice and block-based coding

Rice coding is effective for geometrically distributed gaps when an appropriate parameter is selected. Block-based schemes such as PForDelta and SIMD-oriented codecs compress a block of integers using a common bit width and exceptions for unusually large values. They often provide a strong balance between compression and decoding speed on modern processors.

Compression should be evaluated empirically. Relevant measures include:

and postings throughput, commonly measured in decoded integers per second. A high compression ratio is not automatically desirable if it causes unacceptable query latency.

Dictionary compression may use front coding. If sorted terms share prefixes, a term can be stored as the length of the shared prefix plus its remaining suffix. Finite-state transducers can compress large lexicons while supporting term traversal and lookup.

7. Update Pipelines and Segment Architecture

A static index is easy to optimize but cannot reflect new or modified documents. Production systems therefore use update pipelines.

A common design is the log-structured merge architecture:

1. Incoming documents are parsed and analyzed.
2. Updates are written to a durable transaction log or commit log.
3. A mutable in-memory index, often called a buffer, receives new postings.
4. When the buffer reaches a threshold, it is flushed as an immutable segment.
5. Background processes merge segments into larger segments.
6. A new searcher is opened against a committed snapshot.

Immutable segments simplify concurrency and recovery. Queries can read stable files while new data is written elsewhere. Deletions are frequently represented by tombstones or live-document bitsets until a merge physically removes obsolete postings.

7.1 Segment merging

Without merging, every query may need to search many small segments. Merging reduces the number of search structures but consumes I/O and CPU. A tiered merge policy combines segments according to size and count; a leveled policy maintains size-based levels and often gives more predictable read amplification.

Important operational concepts include:

• Write amplification: extra bytes written because data is repeatedly merged.
• Read amplification: extra structures or segments examined per query.
• Space amplification: temporary and duplicate storage during merging.
• Refresh latency: delay before a committed document becomes searchable.
• Durability latency: delay before an update is safely persisted.

These objectives conflict. Very frequent refreshes improve freshness but increase overhead. Large merges improve read efficiency but can compete with query processing and create temporary storage peaks.

7.2 Deletes and updates

An update is commonly implemented as delete-plus-add: the old document is marked invalid and a new version is indexed. A version number or sequence number prevents an older asynchronous operation from overwriting a newer one. Tombstones must eventually be compacted, otherwise deleted documents continue consuming resources.

Distributed systems add concerns such as shard routing, replica synchronization, failed writes, idempotent replay, and snapshot consistency. A robust pipeline separates ingestion acknowledgment from search visibility and documents both guarantees.

8. Distributed and Scalable Indexing

Large collections are partitioned across machines called shards. A document-partitioned index assigns each document to one shard, so every shard contains a complete local inverted index for a subset of documents. A query is broadcast to relevant shards, each returns local top-k results, and a coordinator merges them.

Document partitioning is operationally simple and supports local indexing, but a query may contact many shards. Term partitioning assigns different terms to different machines, reducing duplication but making query processing and postings access more complex.

Replication improves availability and query throughput but increases storage and update traffic. Shard size should balance parallelism against coordination overhead, recovery time, and merge cost. Excessively small shards create too many files and network operations; excessively large shards reduce flexibility and make recovery slow.

For a distributed top-k query, local results must contain enough candidates for the coordinator to determine the global top k. If local ranking uses different statistics or stale snapshots, ranking consistency may be affected. Global document-frequency statistics can be periodically synchronized or approximated, depending on quality requirements.

9. Design Trade-offs and Evaluation

Index design should begin with workload characterization rather than a preferred data structure. Important questions include:

• What proportion of queries are Boolean, phrase, semantic, or hybrid?
• Is freshness measured in seconds, minutes, or hours?
• What are the p95 and p99 latency targets?
• How large are documents and postings lists?
• What fraction of terms are rare, common, or newly observed?
• Are updates mostly inserts, or are there frequent modifications and deletes?

Useful measurements include:

A sound evaluation uses representative queries, realistic update rates, warm and cold cache conditions, and failure scenarios. Average latency alone is inadequate because users experience tail latency. Compression and skipping should be tested together with ranking, because a technique that helps Boolean intersection may have little effect on a top-k scoring workload.

10. Applied Case: A University Research Repository

The following is an illustrative case.

Background

A university repository contains 12 million theses, articles, and technical reports. Users search titles, abstracts, full text, authors, dates, and exact phrases. New records arrive continuously, while metadata corrections and withdrawals occur daily.

Problem

The initial system scans source files and has a median response time of several seconds. Phrase queries are unreliable, withdrawn documents sometimes remain visible, and nightly rebuilding creates a long period during which new records cannot be searched.

Analysis

The workload requires positional search for phrases, field-aware ranking, frequent incremental updates, and reliable deletion handling. A single mutable index would complicate concurrent reads and recovery. Full positional data for every field would consume unnecessary storage, so positions are retained for title and abstract and selectively for full text.

Approach and solution

The engineering team implements the following design:

• a normalized term dictionary stored in a compact sorted structure;
• document-ordered postings with gap encoding;
• term frequency and field identifiers for ranking;
• positional postings for phrase-capable fields;
• immutable segments produced from memory buffers;
• a durable update log and sequence numbers;
• background tiered merging;
• tombstones and live-document bitsets for withdrawals;
• replicas for availability and query parallelism;
• block-level score bounds for top-k pruning.

Rare-term and common-term queries are benchmarked separately. Segment refresh occurs frequently enough to meet the repository’s freshness objective, while durable commits occur less often to limit synchronization overhead.

Outcome

The redesigned system avoids full collection scans, supports exact phrases, and makes update visibility explicit. Query latency becomes more predictable because large searches use compressed postings, skipping, and score bounds. Storage increases relative to a non-positional Boolean index, but the increase is justified by the repository’s phrase-search requirements.

Learning points

1. Index features should follow user and ranking requirements.
2. Immutable segments simplify correctness and concurrency.
3. Compression must be assessed using both storage and latency.
4. Deletes require lifecycle management, not merely a logical flag.
5. Tail latency and freshness are first-class design objectives.

11. Challenges, Governance, and Contemporary Directions

Indexing systems inherit risks from their source data. Personal information, confidential research, copyrighted material, and legally restricted documents require access controls and retention policies. A document must not become searchable merely because it has entered an ingestion queue. Authorization filters should be applied consistently during retrieval, and caches must not leak results across users.

Audit logs should record indexing decisions, deletion requests, permission changes, and model or analyzer versions. Reproducibility matters: changing tokenization or stemming can alter recall and invalidate comparisons with previous results. Regulatory deletion requirements may require removal from primary indexes, replicas, caches, backups, and derived representations according to applicable policy.

Contemporary systems increasingly combine lexical indexes with vector indexes for semantic retrieval. This does not eliminate inverted indexes: exact terms, identifiers, dates, filters, phrase matching, and explainable lexical ranking remain important. Hybrid retrieval must coordinate candidate generation, access control, freshness, and score fusion. AI-assisted indexing can generate entities, summaries, or embeddings, but derived features should be versioned, quality-tested, and governed because model errors can introduce systematic retrieval failures.

Best practices include:

• define analyzer behavior as versioned configuration;
• use deterministic document identifiers and idempotent updates;
• keep postings sorted unless a measured workload justifies another order;
• monitor segment count, merge debt, tombstone ratio, and disk headroom;
• benchmark p95 and p99 latency under realistic load;
• test recovery, partial failure, replay, and concurrent updates;
• separate search visibility from durability guarantees;
• protect sensitive fields at indexing, storage, and query stages;
• validate compression and skip structures with production-like distributions.

Chapter Summary

An inverted index maps terms to postings lists and provides the foundation for efficient retrieval. Its dictionary supports term lookup, while postings may contain document identifiers, frequencies, fields, positions, and ranking payloads. Positional indexes enable phrase and proximity queries; skip structures and block metadata reduce unnecessary postings access. Gap encoding and integer compression reduce storage and memory bandwidth, but their value must be evaluated against decoding cost.

Modern systems commonly use durable update logs, mutable buffers, immutable segments, tombstones, and background merging. These mechanisms balance freshness, query performance, write amplification, space consumption, and recovery. Distributed indexes introduce shard, replica, coordination, and consistency decisions. Effective engineering therefore requires workload-driven evaluation using storage, throughput, tail latency, freshness, and reliability measurements. Governance is equally important when indexes contain personal, confidential, copyrighted, or regulated information.

Key Terms

Inverted index: A structure mapping terms to documents that contain them.

Dictionary: The lexicon of indexed terms and associated metadata.

Postings list: An ordered list of postings associated with a term.

Document frequency: The number of documents containing a term.

Collection frequency: The total number of occurrences of a term in a collection.

Positional index: An index that stores token positions within documents.

Gap encoding: Representing increasing identifiers by differences between successive values.

Skip pointer: Metadata that permits an iterator to jump over postings.

Block-max index: Block-level upper bounds used to prune ranked retrieval.

Variable-byte coding: A variable-length byte representation of integers.

Front coding: Dictionary compression based on shared prefixes.

Immutable segment: A fixed index segment that is not modified after creation.

Tombstone: A marker indicating that a document or version is deleted.

Refresh latency: Delay before an indexed update is searchable.

Write amplification: Additional writing caused by repeated data organization or merging.

Read amplification: Extra structures or segments examined during a read.

Space amplification: Temporary or duplicate storage beyond the logical data size.

Shard: A partition of an index in a distributed system.

Replica: A redundant copy maintained for availability or throughput.

Hybrid retrieval: Retrieval combining lexical and semantic methods.

Review Questions

Short Answer Questions

1. What are the two principal components of an inverted index?
2. Distinguish document frequency from collection frequency.
3. Why are postings lists normally stored in document-identifier order?
4. What capability does a positional index provide that a basic inverted index does not?
5. State one advantage and one cost of immutable index segments.

Long Answer Questions

1. Explain the complete pipeline for constructing an inverted index from a document collection.
2. Compare hash tables, sorted arrays, tries, and finite-state representations for dictionary storage.
3. Explain how gap encoding, variable-byte coding, and block-based compression affect storage and query performance.
4. Describe a log-structured update pipeline, including refresh, durability, deletion, and segment merging.
5. Analyse the trade-offs between document partitioning and term partitioning in a distributed retrieval system.

Analytical / Application Questions

1. Design an index for a legal document repository requiring exact phrases, field restrictions, frequent corrections, and strict deletion compliance. Justify the structures and update policies selected.
2. A query workload contains many conjunctions over long postings lists but few phrase queries. Recommend whether positional data and skip structures should be used, and explain the storage and latency consequences.
3. A system has good median latency but poor p99 latency during large segment merges. Diagnose likely causes and propose an evaluation and mitigation plan.

Multiple Choice Questions with Answers

Question 1

What does an inverted index primarily map?

A. Documents to their publication dates

B. Terms to documents containing them

C. Queries to user accounts

D. Segments to hardware devices

Correct Answer: B. Terms to documents containing them

Question 2

Which index feature is required for reliable exact phrase matching?

A. Document identifiers only

B. Collection frequency only

C. Token positions

D. A hash table for documents

Correct Answer: C. Token positions

Question 3

For postings [100, 105, 119, 120], which sequence gives the usual gaps after the first identifier?

A. [100, 5, 14, 1]

B. [100, 105, 119, 120]

C. [1, 5, 14, 100]

D. [5, 14, 1, 0]

Correct Answer: A. [100, 5, 14, 1]

Question 4

What is a principal benefit of storing postings in increasing document-identifier order?

A. It eliminates the need for a dictionary

B. It supports efficient intersection and gap compression

C. It guarantees semantic relevance

D. It prevents all index updates

Correct Answer: B. It supports efficient intersection and gap compression

Question 5

Which structure is most naturally suited to prefix queries such as terms beginning with “comput”?

A. Trie

B. Tombstone list

C. Postings skip pointer

D. Document-frequency counter

Correct Answer: A. Trie

Question 6

What is the main purpose of a skip pointer?

A. To encrypt a postings list

B. To jump over postings that cannot contribute to an intersection

C. To assign document identifiers randomly

D. To calculate collection frequency

Correct Answer: B. To jump over postings that cannot contribute to an intersection

Question 7

Why are immutable segments useful in an update pipeline?

A. They make all documents permanently undeletable

B. They simplify concurrent reading and recovery

C. They remove the need for compression

D. They guarantee zero write amplification

Correct Answer: B. They simplify concurrent reading and recovery

Question 8

Which metric describes the delay before an update becomes searchable?

A. Space amplification

B. Refresh latency

C. Collection frequency

D. Compression ratio

Correct Answer: B. Refresh latency

Question 9

A term occurs in 40 documents and appears 200 times in total. What are its document frequency and collection frequency respectively?

A. 40 and 200

B. 200 and 40

C. 40 and 40

D. 200 and 200

Correct Answer: A. 40 and 200

Question 10

What is a likely consequence of retaining positional information for every occurrence in a large collection?

A. Lower storage use with no processing cost

B. Greater storage and indexing cost, with phrase-query support

C. Removal of the need for document identifiers

D. Guaranteed improvement in every query type

Correct Answer: B. Greater storage and indexing cost, with phrase-query support