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.

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. Inclusion test: Require an auxiliary structure associated with base data, a declared key or predicate, a row-location or covering relation, and a maintenance rule preserving consistency. Exclusion test: Exclude unsorted duplicate tables, transient query results, application caches without database consistency, and constraints that have no supporting access structure. Nearest boundary: 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. Exit condition: The identity fails when the structure neither points to authoritative rows nor remains synchronized with their relevant values. Common misclassifications: 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. Nearest named distinctions: Materialized View: Stores a query result rather than primarily mapping keys to base rows. Cache: May be disposable or weakly consistent and need not preserve database access semantics. Table Partition: Divides authoritative storage rather than adding an auxiliary mapping. Inverted Index: A specialized database or search index mapping terms to documents. Primary Key: A logical uniqueness constraint often, but not universally, enforced by an index.

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¶

Characterize the workload and expensive predicates.
Choose key expressions and an access structure matching those operators.
Define coverage, ordering, uniqueness, and any partial predicate.
Build entries and map them to rows transactionally.
Measure planner use, latency, size, and write amplification.
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.

Neighborhood in Abstraction Space¶

Database Index sits in a crowded region of the domain-specific corpus (32^nd 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