The Indexing Principle¶

Creating auxiliary structures that map search criteria to data locations trades space and update cost for query speed - the fundamental mechanism behind fast search in large datasets.

Tension Addressed¶

Access Speed vs. Modification Speed

Recognizable As¶

Database indexes; inverted indexes in search engines; book indexes; hash tables as indexes; B-trees for range queries; any "pre-computed lookup" structure

Canonical Sources¶

Bayer & McCreight, "Organization and Maintenance of Large Ordered Indexes" (1972); Zobel & Moffat, "Inverted Files for Text Search Engines" (2006)

Transfers To¶

Databases (query optimization), Search Engines (term lookup), File Systems (inodes), Caching (cache lookup), Machine Learning (embedding indexes)

Sub-concepts: - Primary vs. secondary indexes: Clustering data vs. pointing to data - Covering indexes: Including query columns to avoid data lookup - Index maintenance cost: Why write-heavy workloads minimize indexes