Index as Read-Write Trade-off¶

An index trades write performance (maintaining the index on every change) for read performance (fast lookup without scanning all data); the optimal set of indexes depends on actual access patterns.

Tension Addressed¶

Write Optimization vs. Read Optimization

Recognizable As¶

Secondary data structures for lookup, B-trees, hash indexes, covering indexes, index selection, slow writes after adding indexes

Canonical Sources¶

Knuth, "The Art of Computer Programming, Vol. 3: Sorting and Searching" (1973); Kleppmann, "Designing Data-Intensive Applications" (2017)

Transfers To¶

Search engines (inverted indexes), caching (lookup structures), file systems (directory indexes), any system requiring fast lookup

Sub-concepts: - Selectivity: An index is only useful if it discriminates well; indexing a boolean column rarely helps - Covering indexes: When the index contains all required data, the main table need not be accessed - Index overhead: Each index adds write latency and storage; over-indexing degrades performance