Database Indexing

WHY INDEXES EXIST: A table scan reads every row (O(n)); an index is a sorted side-structure that turns lookups into O(log n). Trade-off: faster reads, slower writes, more storage — the librarian's card catalog vs walking every shelf. B-TREE — THE DEFAULT: Balanced tree keeps data sorted for range scans, equality, and ORDER BY. Great for '=', '<', 'BETWEEN', prefix LIKE. Most SQL indexes are B-trees. Hash indexes are faster for exact '=' only but can't range-scan. COMPOSITE INDEXES & LEFTMOST PREFIX: An index on (a,b,c) also serves queries on (a) and (a,b) — but NOT (b) or (c) alone. Order columns by selectivity and query shape. Covering index = all needed columns live in the index, so no table trip. WHEN INDEXES FAIL: Functions on columns (WHERE UPPER(name)=), leading wildcards (LIKE '%x'), low-cardinality columns (boolean flags), and tiny tables all defeat or waste indexes. Read the query planner (EXPLAIN) — never guess.