How Is Database Indexing Implemented Internally?

Q: What is indexing and how is it implemented internally?

A: An index is an auxiliary data structure that lets the database look up rows without scanning the entire table.

Key points to cover:

• Most relational databases implement indexes as B-trees (or B+ trees), which keep keys sorted and support O(log n) lookups, range scans, and ordered iteration.
• A primary key index typically maps directly to the row location (clustered index), while a secondary index maps the indexed column's value to the primary key / row pointer (necessitating an extra lookup, a.k.a. a "bookmark lookup").
• Follow-up scenario: two DBs A and B hold the same table T(C1, C2), where C1 is the primary key in both, but C2 is additionally indexed only in DB B. For SELECT C2 FROM T WHERE C1=X, both DBs answer equally fast since they use the primary key/clustered index on C1. For SELECT * FROM T WHERE C1=X AND C2=Y, DB B can be faster if the optimizer uses the secondary index on C2 in combination with C1, but in this case since C1 is already the primary key, the extra index on C2 mainly helps when C2 is used without C1 in the predicate; the exact winner depends on selectivity and the query planner's chosen access path.
• Some databases also support hash indexes (O(1) exact-match lookups, no range scan support) and specialized indexes (GIN/GiST for full-text or geospatial data).