Databases · Question 22 of 50
How does a database index work, and when is it not used?
B-trees, selectivity, and the order of columns in a composite index.
The answer
Most indexes are B-trees: a sorted, balanced tree of the column's values, each pointing to its row. A lookup walks from the root to a leaf in a few steps instead of reading every row, O(log n) instead of O(n), and because the leaves are sorted, ranges and ORDER BY are cheap too. The cost is storage and slower writes, since every insert and update maintains each index.
It may not be used when the query wraps the column in a function (WHERE LOWER(email) = ...), starts a LIKE with a wildcard (LIKE '%gmail'), skips the first column of a composite index, or matches so many rows that reading the table is cheaper. Check with EXPLAIN.
The picture
[ M ]
/ \
[ D H ] [ R W ]
/ | \ / | \
A–C E–G I–L N–Q S–V X–Z → row pointers
WHERE name = 'Kiran': M → D H → I–L → row 3 steps, not a millionAn index on (a, b): which queries can use it?
Show the answer
WHERE a = ?, WHERE a = ? AND b = ?, and ORDER BY a, b. Not WHERE b = ? on its own: the leftmost-prefix rule.