How Is Database Indexing Implemented Internally?

Problem What is indexing, and how is it implemented internally?

Be ready to discuss

• The definition: an auxiliary data structure that lets the engine locate rows without scanning the whole table.
• B-trees and B+trees as the standard implementation: keys held in sorted order, O(log n) lookups, and support for range scans and ordered iteration.
• Why B+trees specifically: values live only in leaves, leaves are linked, and the high fanout keeps the tree shallow so a lookup costs very few disk page reads.
• Clustered/primary index: the index is the table, mapping the key directly to the row's storage location.
• Secondary index: maps the indexed value to a primary key or row pointer, so reading other columns costs an extra hop - the bookmark lookup.
• Covering indices: including the selected columns in the index lets the engine answer from the index alone and skip the bookmark lookup.
• Hash indices: O(1) exact-match lookups but no range scans or ordering.
• Specialised index types: GIN/GiST for full-text and geospatial data, and where LSM-trees fit for write-heavy stores.
• The trade-off: indices accelerate reads but every write must maintain them, costing throughput and storage.
• How the planner picks: selectivity estimates and statistics decide whether an index scan beats a sequential scan - a low-selectivity index is often worse than no index.