Database Indexing for Simple and Composite Keys

Problem How does indexing work for simple keys versus composite keys in a database?

Be ready to discuss

• Simple-key index: typically a B+ tree ordering rows by one column's value, giving O(log n) equality and range lookups, with leaf nodes linked for efficient range scans.
• Composite-key index: orders entries lexicographically by the first column, then the second, and so on — think of a phone book sorted by (last name, first name).
• The leftmost-prefix rule: an index on (city_id, created_at) serves filters on city_id alone or city_id + created_at, but does nothing for a query filtering only on created_at — the single most common misconception here.
• Column ordering: put equality predicates before range predicates, since once a range is used the following columns are no longer usable for seeking, only for filtering.
• Covering indexes and index-only scans: when the index contains every column the query needs, the heap/table lookup is skipped entirely — a major win, and the reason to include otherwise-unused columns.
• Costs: every index slows writes and consumes storage; redundant indexes (one that is a prefix of another) are pure overhead.
• Verification: reading EXPLAIN/EXPLAIN ANALYZE to confirm the index is actually used, plus selectivity and cardinality — a low-cardinality leading column often makes the index worthless.