Skip to content

Database Index

A maintained auxiliary structure mapping declared key values or predicates to database rows so selected retrieval and ordering become faster at a storage and update cost.

Version
v1 · 2026-09-28 · History
Domain-specific #
8864
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomain
Database Systems → Computer Science & Software Engineering

Core Idea

A database index copies or derives key information from a base relation and arranges it for a particular family of access paths. Entries either point back to rows or include enough additional columns to answer a query directly.

The speedup is conditional rather than magical. Tree, hash, bitmap, spatial, full-text, expression, and partial indexes support different predicates. Every index consumes storage and must be kept transactionally consistent as rows are inserted, changed, or removed.

How would you explain it like I'm…

The Back-of-the-Book Finder

At the back of a big book there is an index that says "dinosaurs, page 42," so you don't have to read every page to find them. A database index is like that for a computer's tables. But every time you add or change a page, someone has to update the index too, and it takes up extra paper.

Shortcut List for Finding Rows

A database stores information in big tables with many rows. A database index is an extra, specially sorted list built from some of the table's information, like a phone book sorted by last name, that points back to the matching rows. It helps the computer find certain things much faster without checking every row. Different kinds of indexes help with different kinds of questions, so an index only speeds up the searches it was built for. It also takes extra space and must be updated every time rows are added, changed, or deleted.

Access-Path Lookup Structure

A database index is a separate structure that copies or derives key information from a table and organizes it to speed up particular kinds of lookups. Each entry either points back to the full row or includes enough extra columns to answer a query directly without visiting the table. Different kinds of indexes, such as tree, hash, bitmap, spatial, full-text, expression, and partial indexes, support different kinds of search conditions, so an index helps some queries and not others. Indexes also have costs: they use storage, and every time rows are inserted, changed, or deleted, the index has to be updated consistently within the same transaction. So adding an index is a trade-off, not a free speed boost.

 

A database index copies or derives key information from a base relation and arranges it to support a particular family of access paths. Entries either point back to rows or include enough additional columns to answer a query directly, in which case the index covers the query. The speedup is conditional: tree, hash, bitmap, spatial, full-text, expression and partial indexes each support different predicates, so an index accelerates only queries whose conditions match its organization. Because it is a derived, redundant structure, every index consumes storage and must be kept transactionally consistent with the base relation as rows are inserted, changed or removed, which adds write cost. The design trade-off is therefore read acceleration for specific access patterns against storage and maintenance overhead. An index is distinct from the table itself and from the physical sort order of the table, although some systems cluster rows by an index key.

Structural Signature

Sig role-phrases:

  • Base relation — Contains the authoritative rows being indexed. It is source. Counterfactual: An index without a referenced dataset has no retrieval target.
  • Key expression — Derives ordered or hashed values from chosen columns or functions. It is selector. Counterfactual: A query can benefit only when its predicate matches the key semantics.
  • Entry-to-row mapping — Connects keys to row identifiers or included values. It is relation. Counterfactual: Detached keys cannot retrieve records.
  • Access structure — Organizes entries as a tree, hash, bitmap, or other scheme. It is mechanism. Counterfactual: Different structures support different predicates and orderings.
  • Maintenance path — Updates index entries as underlying rows change. It is invariant. Counterfactual: A stale structure returns incomplete or wrong results.
  • Query planner — Chooses whether and how an index reduces work. It is consumer. Counterfactual: Existence does not guarantee use or benefit.

What It Is Not

  • It is not a second authoritative copy of the table.
  • It is not guaranteed to improve every query.
  • It is not merely a sorted report.
  • It is not free of storage and write cost.
  • Closest near-miss. A table partition reorganizes the base relation into pieces; an index remains auxiliary and maps key conditions toward relevant rows, although systems may combine both.

Scope of Application

  • Point lookup. Finds rows matching exact key values.
  • Range access. Traverses ordered keys between bounds.
  • Ordering. Returns rows in index order when semantics match.
  • Constraint enforcement. Supports uniqueness and related integrity checks.
  • Covering queries. Answers from stored keys and included values.
  • Specialized search. Indexes text, geometry, arrays, or expressions with tailored operators.

Clarity

Record table, key expressions, sort direction, collation, predicate, included values, structure type, uniqueness, size, selectivity, maintenance burden, and observed query plan. Benchmark representative reads and writes.

Manages Complexity

The abstraction separates logical rows from a redundant access path, allowing designers to trade space and update work for fewer comparisons or page reads. Explicit key and predicate semantics prevent misplaced confidence.

Abstract Reasoning

  1. Characterize the workload and expensive predicates.
  2. Choose key expressions and an access structure matching those operators.
  3. Define coverage, ordering, uniqueness, and any partial predicate.
  4. Build entries and map them to rows transactionally.
  5. Measure planner use, latency, size, and write amplification.
  6. Remove or redesign indexes whose maintained cost exceeds demonstrated value.

Knowledge Transfer

The transferable cargo is a maintained key-to-record access path. It transfers to search and storage systems when authoritative data, key semantics, consistency, and cost are preserved; an unmanaged cache is only analogous.

Examples

Applied / In Practice

A composite index on family_name and given_name orders key tuples and points to matching rows, supporting prefixes and ranges under its collation.

Mapped back: structure → B-tree; predicates → equality and range.

Applied / In Practice

An index stores only orders whose status is open, reducing size while serving queries that imply the same predicate.

Mapped back: membership → status=open.

Applied / In Practice

A nightly export sorted by customer name has no maintained link to current table rows, so it is a report rather than an index.

Mapped back: maintenance → none.

Structural Tensions

T1 — Read Speed versus Write Cost. Every maintained structure can reduce retrieval work while adding update operations.

Diagnostic: Does the workload justify the amplification?

T2 — Coverage versus Storage. Including more columns may avoid base-row access but increases space and maintenance.

Diagnostic: Which queries need covering values?

T3 — Logical Predicate versus Physical Organization. Equivalent queries may or may not match expression, collation, type, or partial-index conditions.

Diagnostic: Can the planner prove compatibility?

Structural–Framed Character

Database Index is hybrid: structurally an auxiliary mapping and framed by database transactions, query planning, storage layout, and workload economics.

Structural Core vs. Domain Accent

The core links derived keys to authoritative records through an organized access structure. Database engineering adds pages, B-trees, hashes, collations, operators, selectivity, partial predicates, covering values, concurrency, and maintenance.

  • Approved root. No frozen parent entails a database-maintained access path with these consistency obligations.

  • Related — index, B-tree, hash table, query optimizer, materialized view, database constraint, and table partitioning. These are structures, consumers, or neighbors.

Neighborhood in Abstraction Space

Database Index sits in a crowded region of the domain-specific corpus (32nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Matrices, Measures & Numeric Structures (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Materialized View. Tell: Stores a query result rather than primarily mapping keys to base rows.
  • Cache. Tell: May be disposable or weakly consistent and need not preserve database access semantics.
  • Table Partition. Tell: Divides authoritative storage rather than adding an auxiliary mapping.
  • Inverted Index. Tell: A specialized database or search index mapping terms to documents.
  • Primary Key. Tell: A logical uniqueness constraint often, but not universally, enforced by an index.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Database_index (revision 1357770109).
  • Preserved source candidate: https://terabyte.systems/posts/how-do-database-indexes-speed-up-queries/
  • Preserved source candidate: https://www.postgresql.org/docs/9.1/sql-createtable.html
  • Preserved source candidate: https://download.oracle.com/docs/cd/B12037_01/server.101/b10743/schema.htm#sthref1069
  • Preserved source candidate: http://searchsecurity.techtarget.com/generic/0,295582,sid87_gci1184450,00.html
  • Preserved source candidate: https://web.archive.org/web/20070818140343/http://searchsqlserver.techtarget.com/generic/0,295582,sid87_gci1184450,00.html
  • Preserved source candidate: https://msdn2.microsoft.com/en-us/library/ms177443.aspx
  • Preserved source candidate: http://www.microsoft.com/mspress/books/9364.aspx
  • Preserved source candidate: https://literatejava.com/sql/covering-indexes-query-optimization/

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.