Database Index Types and Internals

Problem What is a database index? What types exist, what data structures back them, and what are the trade-offs?

Be ready to discuss

• The core definition: an auxiliary structure that trades storage and write speed for read speed, letting the engine find rows without a full table scan.
• B-tree/B+tree: the default in most RDBMSs - keys stay sorted, giving O(log n) equality lookups plus range scans, ordered iteration, and prefix matching; B+trees keep all values in leaves linked for cheap range traversal.
• Hash indices: O(1) average equality lookup, but no range queries, no ordering, and no prefix matching.
• Bitmap indices: compact and fast for low-cardinality columns, common in analytics/warehouse workloads, but poor under concurrent writes.
• Specialised indices: GIN/GiST for full-text and geospatial, inverted indices for search, LSM-trees in write-optimised stores.
• Clustered vs secondary: the clustered index defines physical row order; a secondary index stores the key plus a row pointer and may need a second lookup to fetch the row.
• The write cost: every INSERT/UPDATE/DELETE must maintain every affected index, so over-indexing quietly destroys write-heavy workloads.
• Composite indices and the leftmost-prefix rule, plus covering indices that enable index-only scans.
• Why the planner sometimes ignores your index: low selectivity, stale statistics, or a function applied to the indexed column.