Is a postings reference always a memory pointer?

No; it can be a document identifier or another locator.

Does an index guarantee constant-time queries?

No; cost depends on its structure and the query.

Can a phrase query need more than term membership?

Yes; order and position matter.

AI Glossary / Graphs and symbolic AI / Advanced

Index

Definition

An index is an auxiliary data structure that links searchable keys or terms to the records, sentences, or documents associated with them. It helps a system locate matching items without repeatedly examining the entire collection. In this glossary entry, the term concerns information access, rather than a numerical position in an array or a market indicator.

What it means

The source collection holds the content. The index organizes access to that content around anticipated queries. For example, a term index can record which document identifiers contain each word, while a record index can help locate entries with a particular identifier.
An index does not automatically understand the content or establish that a retrieved statement is true. It identifies matches according to its keys, preprocessing rules, and supported operations.
Its usefulness also depends on its relationship to the current collection. Missing entries can hide relevant records, while outdated references can point to content that has changed or been removed.

How it works

Choose the information to index and assign stable identifiers to the source items. Extract keys, such as normalized text terms or selected field values, and associate those keys with item references.
A basic inverted text index has a dictionary of terms and a postings list for each term. A postings list identifies documents containing that term. Depending on the design, additional information can include occurrence counts or positions.
At query time, the system looks up keys and combines their matching lists. An AND query intersects lists; an OR query combines them without duplicating document identifiers. Further checks may be needed for conditions that the index does not encode.
Building and maintaining an index has costs. It uses storage and requires work when indexed content changes. Database systems can choose a scan when they estimate that using an available index would be less efficient. An index is therefore a tool for a workload, not a universal promise of faster access.

Three practical examples

A knowledge-base assistant retrieves articles containing specified product terms before constructing an answer. The retrieval stage identifies candidate content; the answer still needs to reflect the meaning and authority of that content.
A service database uses an order-identifier index to locate a record. This avoids treating every lookup as an instruction to examine every stored order.
A document-review tool combines indexes for terms and metadata. It might identify records containing a phrase candidate, then check the source text to verify the requested wording and context.

Think of it this way

Think of a library catalog that tells you which shelves contain books on a subject. The catalog saves searching shelf by shelf. It does not replace reading the books, and an outdated shelf reference can still send you to the wrong place.

Worked example

Consider five invented documents, each represented here by its full text:
D1: “robot checks invoice”. D2: “invoice requires review”. D3: “robot assists review”. D4: “review checks robot”. D5: “sensor checks pressure”.
For this example, lowercase the text, split it at spaces, and record each document once per distinct term. Do not apply stemming, synonym expansion, or other preprocessing.
The postings list for robot is {D1, D3, D4}. The list for invoice is {D1, D2}. The list for review is {D2, D3, D4}. The list for checks is {D1, D4, D5}.
The query robot AND review intersects {D1, D3, D4} with {D2, D3, D4}, yielding {D3, D4}. Both documents contain both terms. The query invoice OR robot returns {D1, D2, D3, D4}; D1 appears once, even though it matches both terms.
Now ask for the exact phrase “robot checks”. Intersecting the robot and checks lists gives {D1, D4}. However, only D1 contains the phrase in that order with the words adjacent. D4 contains “checks robot,” so a term-only index supplies candidates but cannot by itself settle this phrase query. Stored positions or a source-text check can resolve the distinction.
Next, replace D3's text with “robot assists audit”. A current index must remove D3 from the review list and add it to the audit list. Its membership in robot remains unchanged. The updated robot AND review query should return only D4.
If the index still returns D3, its stored term membership no longer matches the source collection. That is an index-maintenance problem, not evidence that the new D3 text contains review.
Finally, repeat the word robot within D1. In the basic membership index, D1 still appears only once in the robot postings list. An index that stores term frequencies may update that additional statistic, but repeated occurrences do not create new documents.

Illustrative case study

Fictional Maple Knowledge builds an assistant over internal help articles. A review finds that recently revised articles still appear under terms removed from their text.
The team traces the issue to an update process that adds new term associations but leaves old ones in place. It tests replacements as well as insertions and verifies that search results reflect the intended document version.
Maple also distinguishes term matching from phrase matching in its evaluation. Reviewers compare indexed results with direct checks on a small reference collection.

Common misconceptions and mistakes

“An index is the source content.” It primarily organizes access to content.
“Matching terms prove the requested meaning.” Context and query semantics still matter.
“Every index answers every query.” Capabilities depend on what it stores.
“More indexes always improve performance.” Maintenance and storage have costs.
“Repeated words imply repeated documents.” Document membership and occurrence frequency differ.

Business use

Choose indexes around the questions the application needs to answer. Track query performance together with update cost, storage use, and correctness after content changes.
Test insertions, replacements, and removals. Include common terms, rare terms, and combinations whose answers are known. For an AI assistant, distinguish successful retrieval from a supported final answer: finding a record is only one part of using it correctly.

Check your understanding

Why does D4 fail the phrase query?

Answer: Its words occur in the reverse order.

What changes after replacing D3?

Answer: It leaves review's postings and enters audit's.

Why does D1 appear once in the OR result?

Answer: The result represents distinct documents.

Related terms

Inverted index
postings list
document identifier
key
retrieval
query processing
term frequency
index maintenance

Learn next

Build the complete term-to-document mapping for the example. Compare term conjunction with exact phrase matching, then update one document and identify every affected posting.

Sources

AIMA glossary, index: https://github.com/aimacode/aima-glossary/blob/master/glossary.md Manning, Raghavan and Schutze, inverted-index construction: https://nlp.stanford.edu/IR-book/html/htmledition/a-first-take-at-building-an-inverted-index-1.html Manning, Raghavan and Schutze, Boolean query processing: https://nlp.stanford.edu/IR-book/html/htmledition/processing-boolean-queries-1.html PostgreSQL documentation, introduction to indexes: https://www.postgresql.org/docs/current/indexes-intro.html

Previous: Independent variable Next: Index number