Index

Prime #

915

Origin domain

Computer Science & Software Engineering

Subdomain

data structures retrieval → Computer Science & Software Engineering

Aliases

Indexing

Core Idea

An index is the structural pattern of an auxiliary structure maintained alongside a primary collection, mapping selected keys to locations within the collection, so that lookup by key is much faster than scanning the collection itself. The defining commitments are five. The index is auxiliary — a separate object from the data it points into, which could exist without it. It is a key-to-location mapping — it stores not the data but pointers (page numbers, file offsets, row IDs, citation IDs^[1]). It is built on selected keys — chosen attributes, not everything, so the choice of key determines which questions it can answer quickly. It carries a maintenance burden — it must be kept consistent when the primary data changes, so inserts, deletes, and updates all incur index-maintenance cost. And it delivers an asymmetric speedup — it makes some queries fast (those whose key it indexes) and no queries slow, except for the write-amplification cost.

An index is not the data it points into, not a cache (which stores copies of values), and not associative memory (the cross-substrate content-addressable retrieval pattern). It is a pointer table: short, derived, ordered or hashed, maintained on the side. The substrate- independent move the prime supplies is spend maintenance cost up front, and storage cost on the side, to make later lookup cheap. The triple — key, pointer, maintenance — is what travels, and although the vocabulary is mildly tied to bibliographic and database practice, the pattern itself is substrate-neutral and appears wherever fast retrieval must be bought with a maintained side-structure.

How would you explain it like I'm…

Back-Of-Book Finder

At the very back of a big picture book there's a little list that says 'dinosaurs ... page 40.' Instead of flipping through every page to find dinosaurs, you check the list and jump straight there. The list isn't the dinosaur picture itself — it just *points* to where it lives. That little pointing-list is an index.

The Pointer List

An index is a separate helper kept next to a big collection of stuff, and it maps keys (like a word or a name) to WHERE that thing is — a page number or a location. Because of it, finding something by its key is way faster than reading through the whole collection. But the index isn't the data; it only holds pointers to the data. The trade-off is that whenever the collection changes, you have to update the index too, so it costs a little extra work to keep it correct — in exchange for much faster looking-up later.

Key, Pointer, Maintenance

An index is an auxiliary structure kept alongside a primary collection that maps selected keys to locations within the collection, so lookup by key is much faster than scanning the collection itself. Five commitments define it: it's auxiliary (a separate object that could be deleted without losing the data), it's a key-to-location mapping (it stores pointers like page numbers or row IDs, not the data itself), it's built on selected keys (so the choice of key decides which questions it can answer fast), it carries a maintenance burden (it must stay consistent as the data changes, so writes cost extra), and it gives an asymmetric speedup (some queries get faster, none get slower, except for that write cost). It is NOT the data, not a cache (which stores copies of values), and not associative memory (content-based retrieval). The core move is: spend maintenance cost up front, and storage on the side, to make later lookup cheap — the triple of key, pointer, and maintenance is what travels across substrates.

 

An index is the structural pattern of an auxiliary structure maintained alongside a primary collection, mapping selected keys to locations within the collection so that lookup by key is much faster than scanning the collection itself. Five commitments define it. It is auxiliary — a separate object from the data it points into, which could exist without it. It is a key-to-location mapping — it stores not the data but pointers (page numbers, file offsets, row IDs, citation IDs). It is built on selected keys — chosen attributes, not everything, so the choice of key determines which questions it can answer quickly. It carries a maintenance burden — it must be kept consistent when the primary data changes, so inserts, deletes, and updates all incur index-maintenance cost. And it delivers an asymmetric speedup — it makes some queries fast (those whose key it indexes) and no queries slow, except for the write-amplification cost. An index is not the data it points into, not a cache (which stores copies of values), and not associative memory (the cross-substrate content-addressable retrieval pattern). It is a pointer table: short, derived, ordered or hashed, maintained on the side. The substrate-independent move the prime supplies is spend maintenance cost up front, and storage cost on the side, to make later lookup cheap. The triple — key, pointer, maintenance — is what travels, and although the vocabulary is mildly tied to bibliographic and database practice, the pattern itself is substrate-neutral and appears wherever fast retrieval must be bought with a maintained side-structure.

Structural Signature

a primary collection — an auxiliary side-structure — a set of selected keys — a key-to-location pointer mapping — the maintenance burden under update — the asymmetric-speedup invariant (faster reads on indexed keys, no reads slowed)

A structure is an index when the following hold:

• A primary collection. A body of data — table, book, corpus, memory store — that exists independently and could be scanned directly.
• An auxiliary side-structure. A separate object maintained alongside the collection; it is not the data and could be dropped without losing the data.
• Selected keys. The index is built over chosen attributes, not over everything; the key choice determines exactly which questions it can answer quickly.
• A key-to-location mapping. It stores pointers — page numbers, row IDs, offsets, citation IDs — from keys to locations within the collection, not copies of the values themselves (which distinguishes it from a cache).
• A maintenance burden. Every insert, delete, or update to the primary data must be reflected in the index to keep it consistent, incurring write amplification.
• The asymmetric-speedup invariant. The index makes queries on its indexed keys much faster and slows no query except through the write-time maintenance cost — buying cheap reads with paid-up-front maintenance and side storage.

These compose into one move: pay maintenance cost and side storage up front to pre-arrange selected keys, so later lookup on those keys is cheap while the data itself is untouched.

What It Is Not

• Not caching. A cache stores copies of values to avoid recomputing or refetching them; an index stores pointers to where values live. A cache hit returns the data; an index hit returns a location that must then be followed.
• Not associative_memory. Associative memory is content-addressable retrieval — recall by partial content or similarity; an index is an explicit key-to-location table built on chosen keys, answering exact-key lookups, not similarity recall.
• Not search_and_retrieval. Search is the act of locating items matching a query; an index is a pre-built side structure that makes certain searches fast. The index accelerates retrieval; it is not the retrieval process.
• Not hashing. Hashing is the function that turns a key into a short token; an index is the whole lookup apparatus, which may use a hash (a hash index) or an ordering (a B-tree) to arrange its keys.
• Not aggregation. Aggregation summarizes many records into a combined value; an index neither summarizes nor stores values — it preserves per-key pointers so individual records can be found quickly.
• Common misclassification. Expecting an index to return data. The pointer-not-copy commitment means an index hit still requires a fetch; a structure that returns values is a cache or the content store, not an index. Catch it by asking whether the structure holds pointers or copies.

Broad Use

The skeleton recurs across substrates. In books and scholarly works it is the back-of-book subject index, the table of contents (a positional index), and the citation index mapping cited-work IDs to citing-work locations. In libraries it is card catalogs and their digital descendants, classification schemes, and controlled-vocabulary thesauri. In computer science it is database indexes (B-tree, hash, bitmap, inverted), inverted indexes in information retrieval, spatial indexes, inode tables, and compiler symbol tables.^[2] In cognition and neuroscience it is the hippocampal indexing theory of memory: the hippocampus stores pointers to neocortical patterns, not the patterns themselves, so retrieval cues activate the index which reactivates the distributed content, and tip-of-the-tongue states are index-hit-but-content-fetch-miss.^[3] In organisations it is filing systems and registry IDs (ISBN, DOI, ORCID) — auxiliary pointer tables from selected keys to record locations.^[4] In genetics it is chromosomal maps as positional indexes of genes. In geography it is gazetteers mapping place names to coordinates, and postal codes as composite classify-plus-locate indexes.^[5] In law it is statute indexes, case-citation systems, and land registries as parcel-to-owner indexes.^[6] These instances share all five structural features and are not metaphor: a back-of-book index and a database B-tree both maintain a key-to-location mapping on the side, both incur maintenance cost on update, and both deliver the same asymmetric speedup on indexed queries.

Clarity

The prime makes visible that fast retrieval is not free; it is paid for by a side-structure that is itself maintained at cost. Once a practitioner sees this, "how do I make this lookup fast?" reshapes into the more useful "what keys do I index, what maintenance cost am I willing to pay, and what queries am I not speeding up?" The same questions surface for a book editor choosing index terms, a database administrator choosing columns to index, a librarian choosing a controlled vocabulary, and a memory researcher modelling the hippocampus. The prime also exposes the which-question-am-I-supporting discipline: indexes are not generic — they speed up only the queries whose keys they index, and multiple indexes serve multiple query patterns at multiple costs. The clarifying force is to make the chosen key, the maintenance cost, and the set of accelerated queries explicit, rather than treating "add an index" as an unqualified good.

Manages Complexity

The prime transforms an O(n) scan into an O(log n) or O(1) lookup at the cost of O(log n) or O(1) maintenance per write — the central management move is this complexity redistribution. The index absorbs the lookup cost at the price of a small storage overhead and a write amplification: each insert touches both data and index. The pattern also enables separation of indexing concerns from storage concerns: the same data can be indexed multiple ways for multiple access patterns, and indexes can be rebuilt, dropped, or re-keyed without changing the underlying data. The management payoff is that the cost of access is moved off the read path — where it would be paid repeatedly, once per query — and onto the write path and a side storage budget, where it is paid once per change. Lookups become cheap because the side-structure has pre-arranged the keys; the bill arrives as maintenance, and the design choice is which queries are worth that bill.

Abstract Reasoning

The pattern raises substrate-independent design questions. Which key? — single-column versus composite, identifier versus content-derived; the wrong key indexes the wrong question. Which structure? — ordered for range queries (B-tree) versus hashed for equality. Where does maintenance cost fall? — synchronously on write versus asynchronously via background reindexing; books typically build the index once at publication, databases can do either. Selectivity — how many records does a typical key match? Low-selectivity indexes (most rows share the value) are nearly useless; high-selectivity indexes are powerful. Coverage versus cost — a covering index that includes the data needed to answer the query trades storage for I/O. And staleness tolerance — a search-engine inverted index may be hours stale, a bank-balance index must be transactional. These transfer cleanly across database indexes, library catalogs, citation systems, memory models, and gene maps. The reasoner asks, of any retrieval problem: what key, what structure, what selectivity, what maintenance timing, and what staleness can be tolerated?

Knowledge Transfer

The intervention catalog carries portable moves. Add an index for a slow query you can name a key for, and remove indexes that pay maintenance for queries no one asks. Composite-key indexes match composite questions (last name plus first name, latitude plus longitude). Inverted indexes invert the natural key-to-location: instead of "for each row, which terms?", store "for each term, which rows?" — the move that made full-text search tractable, and the same move behind citation indexes and reverse lookups.^[7] Spatial indexes use space-filling curves or hierarchical bounding, an idea reused in graph partitioning and physics tree codes.^[8] And index-only access paths save the data fetch when the index carries enough information. The role mappings are direct: primary collection ↔ table / book / corpus / neocortex, index ↔ B-tree / back-of-book index / inverted index / hippocampal pointer set, key ↔ column / subject term / token / retrieval cue, pointer ↔ row ID / page number / posting / cortical address, maintenance ↔ write amplification / re-indexing at new edition / re-encoding. A librarian who understands controlled-vocabulary selectivity reads a database-tuning paper and immediately sees the shared maintenance trade-offs; a memory researcher who understands hippocampal indexing reads a search-engine architecture paper and recognises the inverted-index reuse. A medical-records system indexing 100 million encounters on patient_id, on (diagnosis_code, encounter_date), and on clinical-note text via an inverted index pays each index's cost — three structures updated per insert, roughly doubled storage, hours-long rebuilds — and the same three-knob design (which key, which structure, what maintenance cost) recurs in the back-of-book index an editor builds, the citation index built for science, and the hippocampal pointer structure mapping cues to distributed content. Because the pattern is substrate-neutral while only its vocabulary leans bibliographic, the transfer is recognition of one shape — a maintained key-to-pointer side-table — across books, databases, cognition, genetics, geography, and law.

Examples

Formal/abstract

Take a database B-tree index on a last_name column as the rigorous instance. The primary collection is a table of a million customer rows stored in insertion order on disk. The auxiliary side-structure is a balanced B-tree, a separate object that could be dropped without losing a single row of data. Its selected key is last_name — a deliberate choice that determines exactly which questions it accelerates. The key-to-location mapping is decisive and distinguishes the index from a cache: each leaf stores not the row's data but a pointer (a row ID or disk offset) to where the row lives. The maintenance burden is concrete: every insert, delete, or update must also rebalance the tree, so writes pay \(O(\log n)\) index upkeep — the write amplification the prime names. The asymmetric-speedup invariant is the payoff: a query WHERE last_name = 'Okafor' drops from an \(O(n)\) full scan of a million rows to an \(O(\log n)\) descent of the tree, while no query is slowed except through that write-time cost.^[2] The prime's design discipline is what the index makes askable: selectivity governs whether the index helps at all — indexing a boolean is_active column where half the rows match is nearly useless, because the index still points at 500,000 rows, whereas last_name is highly selective.^[9] And the structure choice matters: a B-tree (ordered) serves range queries like last_name BETWEEN 'A' AND 'C', where a hash index (equality only) would not.^[2] The intervention this enables: rather than "add an index" reflexively, the designer asks which named query needs speeding, whether its key is selective, and whether range or equality access is required.

Mapped back: The B-tree instantiates every role — independent table, droppable side-tree, chosen key, pointer (not copy) mapping, \(O(\log n)\) maintenance, asymmetric read speedup — and shows the prime's read/write cost redistribution and the selectivity discipline operating concretely.

Applied/industry

Consider the hippocampal indexing theory of memory in neuroscience and a back-of-book subject index in publishing as two applied instances of the identical shape. In the hippocampal model the primary collection is the distributed neocortical patterns that constitute a memory's content; the auxiliary side-structure is a sparse set of hippocampal pointers; the key is a retrieval cue; and — exactly as the prime insists — the hippocampus stores pointers to cortical patterns, not the patterns themselves. A cue activates the index, which reactivates the distributed content. The prime's distinctions illuminate a clinical phenomenon: a tip-of-the-tongue state is an index-hit but content-fetch-miss — the pointer fires (you know the word exists, its first letter, its shape) but the cortical fetch fails, precisely the failure profile an index, not a cache, would produce.^[10] A back-of-book index runs the same five features mechanically: the primary collection is the book's pages, the side-structure is the alphabetised subject list, the selected keys are the terms an editor judges readers will search, the pointers are page numbers, and the maintenance burden is paid at each new edition when pagination shifts.^[11] The shared intervention across all three — neuroscientist, editor, and the database administrator above — is the same three-knob design: which keys to index, which structure to use, and what maintenance cost to accept, while the data itself stays untouched.

Mapped back: Hippocampal indexing and the back-of-book index both run the prime end-to-end — an independent content store, a maintained key-to-pointer side-structure, and an asymmetric retrieval speedup — and the pointer-not-copy commitment is what makes the tip-of-the-tongue failure mode legible as an index miss rather than a content loss.

Structural Tensions

T1 — Read Speedup versus Write Amplification. The index buys cheap reads on its key by paying maintenance on every write — the asymmetric-speedup invariant has a write-side cost. The tension is that reads and writes pull in opposite directions: more indexes accelerate more query patterns but slow every insert, delete, and update. The failure mode is reflexively adding indexes until write throughput collapses, paying maintenance for queries no one runs. Diagnostic: for each index, name the actual query it serves and weigh its read benefit against the per-write upkeep; drop indexes whose queries are rare or absent.

T2 — Key Choice versus Question Set. An index speeds only the queries whose key it indexes; the key choice silently fixes which questions are fast and which still scan. The tension is scopal: an index is not generic, yet "add an index" is treated as an unqualified good. The failure mode is indexing the wrong key — building a structure on an attribute nobody filters by while the hot query still does a full scan. Diagnostic: ask which named queries must be fast, and confirm the index's key matches their filter; an index that answers a question no one asks is pure cost.

T3 — Selectivity versus Uselessness. An index helps in proportion to how few records its typical key matches; a low-selectivity key (half the rows share the value) points at so many locations it barely beats a scan. The tension is measurement: the same index structure is powerful on a high-selectivity key and near-worthless on a low one. The failure mode is indexing a boolean or heavily-skewed column and expecting a speedup that the selectivity cannot deliver. Diagnostic: estimate how many records a typical key value matches; if it is a large fraction of the collection, the index will not pay for itself.

T4 — Ordered versus Hashed Structure. The structure choice fixes which access patterns are cheap: ordered (B-tree) serves ranges, hashed serves equality only. The tension is that the same key indexed two ways answers different question shapes. The failure mode is choosing a hash index and then needing range queries (BETWEEN, prefix, sort), which the structure cannot serve, or paying for ordered structure where only equality lookups occur. Diagnostic: ask whether the queries are equality-only or include ranges and ordering, and match the index structure to the access shape before building it.

T5 — Maintenance Timing versus Staleness Tolerance. Maintenance can fall synchronously on each write (always consistent, slower writes) or asynchronously via background reindexing (faster writes, temporarily stale index). The tension is temporal: consistency and write speed trade off through when the index is updated. The failure mode is mismatching timing to need — a transactional bank-balance index updated lazily returns wrong answers, while a search corpus forced to index synchronously throttles ingestion for freshness no one requires. Diagnostic: ask how stale the index may be for its queries, then choose synchronous maintenance only where staleness is intolerable.

T6 — Index versus Cache and Content Store. An index stores pointers, not copies of values — which distinguishes it from a cache (copies of data) and from the content store it points into. The tension is that the pointer-not-copy commitment determines the failure profile, and the three are easily conflated. The failure mode is expecting an index to return data it does not hold — a pointer fires but the content fetch fails (the tip-of-the-tongue miss), or a cache is mistaken for an index and grows stale copies instead of pointers. Diagnostic: ask whether the structure holds pointers or values; an index hit still requires a fetch, and that two-step is exactly where index misses differ from content loss.

Structural–Framed Character

Index sits at the structural end of the structural–framed spectrum, aggregate 0.2: the skeleton — an auxiliary key-to-location pointer table maintained on the side to make lookup cheap — is substrate-neutral, with two diagnostics carrying half-weight.

Vocabulary travels (0.5): "index," "key," "B-tree," "inverted index," "selectivity," "write amplification" lean bibliographic and database, and that residual flavour earns the half-point. But it is only half, because the maintained-pointer-table move is read off other substrates in their own words: a neuroscientist's hippocampal pointer set mapping cues to neocortical patterns, a geneticist's chromosomal map of genes, a geographer's gazetteer of place names to coordinates, a back-of-book subject index — each instantiates "selected keys, pointers not copies, maintenance on update" without importing the database lexicon. Institutional origin (0.5): the construct leans on bibliographic and database practice, a faint disciplinary origin; yet the hippocampal-indexing case shows the same key-to-pointer structure arising in a biological substrate with no institution at all, which holds this to 0.5. The other three read zero. No evaluative weight: an index is neither good nor bad — "add an index" is a cost/benefit choice, not approval. Not human-practice-bound: hippocampal indexing realizes the pattern in neural tissue with no human practice required for the structure to hold. Recognized, not imported: to call a structure an index is to recognize a maintained key-to-pointer side-table already present — the tip-of-the-tongue failure is read off as an index miss, not overlaid. Two half-points against three zeros land exactly at the 0.2 aggregate and structural label.

Substrate Independence

Index is a strongly substrate-independent prime — composite 4 / 5 on the substrate-independence scale. Its domain breadth is maximal: the maintained key-to-pointer side-table appears as the back-of-book subject index and citation index in scholarly works, as card catalogs and controlled-vocabulary thesauri in libraries, as B-tree, hash, bitmap, and inverted indexes in computer science, as the hippocampal indexing of memory in neuroscience (the hippocampus storing pointers to neocortical patterns, not the patterns themselves), as registry IDs and filing systems in organizations, as chromosomal maps in genetics, as gazetteers in geography, and as statute indexes and land registries in law. These are not metaphor — a back-of-book index and a database B-tree both maintain a key-to-location mapping on the side, both pay maintenance on update, and both deliver the same asymmetric speedup. The structural abstraction is high: the same triple — selected key, pointer not copy, maintenance burden — and the same design discipline (which key, which structure, what selectivity, what staleness tolerance) carry across every instance. The transfer evidence is concrete: a librarian's controlled-vocabulary selectivity, a database administrator's index tuning, and a memory researcher's hippocampal model share recognizable trade-offs, and the inverted-index move (store "for each term, which rows?") reappears in citation systems and reverse lookups. What caps it at 4 is a mild bibliographic-and-database vocabulary accent ("index," "B-tree," "write amplification") that leans on those practices. The hippocampal-indexing case, realizing the structure in neural tissue with no institution at all, confirms it runs in a biological substrate. Maximal spread and strong transfer with a light vocabulary accent give a confident 4.

• Composite substrate independence — 4 / 5
• Domain breadth — 5 / 5
• Structural abstraction — 4 / 5
• Transfer evidence — 4 / 5

Relationships to Other Abstractions

Current abstraction Index Prime

Parents (1) — more general patterns this builds on

• Index presupposes Search and Retrieval Prime

  'Not search_and_retrieval — search is the ACT; an index is a pre-built side structure that makes certain searches fast.' An index presupposes a retrieval setting it accelerates; it is the apparatus-for-retrieval, not the retrieval activity.

Hierarchy paths (4) — routes to 3 parentless roots

• Index → Search and Retrieval → Problem Space → Representation → Abstraction

Show alternative paths (3)

Neighborhood in Abstraction Space

Index sits in a sparse region of abstraction space (82^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely rather than landing on a neighbor.

Family — Graph & Relational Structure (14 primes)

Nearest neighbors

• Data Structure — 0.71
• Stack — 0.71
• Preimage — 0.70
• Measure — 0.69
• Primary vs. Secondary Sources — 0.68

Computed from structural-signature embeddings · 2026-07-26

Not to Be Confused With

The most consequential confusion is with caching, because both are auxiliary structures maintained alongside primary data to make access faster, and both incur a consistency burden when the data changes. The decisive difference is what they store. A cache stores copies of values: a cache hit hands you the data directly, and its risk is staleness — the copy may diverge from the source. An index stores pointers: an index hit hands you a location, which you must then follow to fetch the value, and its risk is a dangling or wrong pointer — the location may no longer hold what you expect. This single difference cascades through their whole behaviour. A cache can serve data even when the source is slow or unavailable (it has a copy); an index cannot (it only knows where to look). A cache's invalidation problem is "is my copy still correct?"; an index's maintenance problem is "do my pointers still aim at the right places?" Mistaking one for the other produces real bugs: building an "index" that quietly caches values and then serves stale ones, or building a "cache" of pointers that returns locations whose contents have moved.

It is also distinct from associative_memory, with which it shares the goal of fast retrieval but not the mechanism. Associative memory is content-addressable: you recall an item by presenting part of its content or something similar to it, and the structure completes or matches the pattern. An index is key-addressable: it answers lookups on the specific keys it was built over, and only those — an index on author cannot answer a query by title. The selection of keys is the defining constraint of an index and the source of its asymmetry (fast on indexed keys, no help on others), whereas associative memory's whole point is graceful retrieval from partial or approximate cues. Reading an index as associative memory leads to expecting similarity-based or partial-match recall that an exact-key pointer table simply cannot provide.

A third confusion is with search_and_retrieval, the activity an index serves. Search is the process of locating items that satisfy a query; an index is a pre-arranged side structure that makes some of those searches cheap. You can search without an index (scan the whole collection) and you can maintain an index that a given search never uses (the query keys on an unindexed attribute). Conflating the structure with the activity obscures the core trade the index makes: it pays maintenance and storage cost up front so that later searches on its keys are cheap — a bargain that only pays off if those searches actually happen.

For a practitioner the unifying discipline is to name what the auxiliary structure holds and what it is keyed on. A cache holds values (risk: staleness); an index holds pointers keyed on chosen attributes (risk: stale pointers, and uselessness for un-indexed queries); associative memory matches on content; and search is the activity all of these accelerate. Keeping the pointer-not-copy and selected-key commitments in view is what prevents an index from being asked to do a cache's, a memory's, or a search engine's job.

Solution Archetypes

Solution archetypes in the catalog that build on this prime — directly (this prime is a source ingredient) or as a related prime.

Built directly on this prime (2)

• Operation-Weighted Data Structure Design: Choose the information structure around the real operation mix, making lookup, update, traversal, storage, consistency, and maintenance tradeoffs explicit instead of accidental.
  ▸ Mechanisms (11)
• Registry-Mediated Discovery: Put a maintained discovery registry between agents and changing counterparts so stable names resolve to current locations, interfaces, or contact records instead of hard-coded references.
  ▸ Mechanisms (10)

Also a related prime in 3 archetypes

• LIFO Stack Discipline: Use a last-in, first-out nesting discipline whenever safe work depends on closing the current context before returning to the one beneath it.
• Metric-Space Specification and Validation: Turn vague closeness into a validated distance function before using near/far relationships to search, cluster, route, threshold, or reason locally.
• Preimage Set Characterization: Given an output condition, identify and bound the complete set of inputs that could produce it before acting as if the output has a unique source.

References

[1] Garfield, Eugene. "Citation Indexes for Science: A New Dimension in Documentation Through Association of Ideas." Science, vol. 122, no. 3159 (1955): 108–111. Originates the citation index — a side table mapping cited-work IDs to citing-work locations, an inverted key-to-location pointer structure. ↩

[2] Comer, Douglas. "The Ubiquitous B-Tree." ACM Computing Surveys, vol. 11, no. 2 (1979): 121–137. Survey of the B-tree as the canonical key-to-location index: an auxiliary balanced structure giving O(log n) lookup on its indexed key at O(log n) maintenance per write, serving range queries that hashing cannot. ↩

[3] Teyler, Timothy J., and Pascal DiScenna. "The Hippocampal Memory Indexing Theory." Behavioral Neuroscience, vol. 100, no. 2 (1986): 147–154. Proposes that the hippocampus stores pointers (an index) to distributed neocortical patterns rather than the content itself, so a cue activates the index which reactivates the content. ↩

[4] International DOI Foundation. DOI Handbook (and ISO 26324: Digital Object Identifier System). Persistent registry-identifier system mapping selected keys (DOI names) to record locations through a resolution service — an auxiliary pointer table from keys to record locations, the registry-ID instance (with ISBN, ORCID). ↩

[5] J. Paul Getty Trust. Getty Thesaurus of Geographic Names (TGN). A structured gazetteer mapping place names (and historical/vernacular variants) to coordinates and place types — an auxiliary key-to-location pointer table over place-name keys, the geography instance. ↩

[6] Cornell Legal Information Institute (Wex). Torrens Title / Land Registration. Land registries maintain a tract index (and grantor/grantee indexes) mapping each parcel to its registered proprietor and interests — an auxiliary parcel-to-owner pointer table, the law instance (with statute and case-citation indexes). ↩

[7] Zobel, Justin, and Alistair Moffat. "Inverted Files for Text Search Engines." ACM Computing Surveys, vol. 38, no. 2 (2006): article 6. The inverted index ('for each term, which documents?') that makes full-text search tractable — the same key-to-location inversion behind citation indexes and reverse lookups. ↩

[8] Guttman, Antonin. "R-Trees: A Dynamic Index Structure for Spatial Searching." In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, 47–57. New York: ACM, 1984. Spatial index using hierarchical bounding; the bounding/space-partitioning idea reused in graph partitioning and physics tree codes. ↩

[9] Selinger, P. Griffiths, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. "Access Path Selection in a Relational Database Management System." In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, 23–34. New York: ACM, 1979. Establishes selectivity as the determinant of whether an index pays off — a low-selectivity key points at too many rows to beat a scan. ↩

[10] Brown, Roger, and David McNeill. "The 'Tip of the Tongue' Phenomenon." Journal of Verbal Learning and Verbal Behavior, vol. 5, no. 4 (1966): 325–337. The tip-of-the-tongue state as a retrieval failure in which partial-pointer information is available but the content fetch fails — the index-hit/content-miss failure profile. ↩

[11] University of Chicago Press. "Indexes" (chapter 16/15), The Chicago Manual of Style. The standard guide to back-of-book indexing: selected subject terms as keys, page numbers (locators) as pointers, with maintenance paid when pagination shifts across editions — the publishing instance. ↩