Indexes
The role of an index, the B-tree behind it, unique, composite and covering indexes, the leftmost-prefix rule, selectivity, write cost and the cases where the database cannot use one.
- 24 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Index: what is it?
Show the answer
An auxiliary structure, sorted on one or more columns, that finds rows without reading the whole table, at the price of an update on every write.
Like a book's index: you look the word up in a sorted list instead of reading every page. Each INSERT, UPDATE or DELETE, however, must update the index.
A table receives millions of INSERT statements and has 8 indexes. What effect does that have on the INSERT statements?
- Each INSERT also updates the 8 indexes: it is slower
- INSERT is faster, because the indexes keep rows sorted
- None: indexes are only updated at read time
- Indexes are only rebuilt when the server restarts
Show the answer
Each INSERT also updates the 8 indexes: it is slower
An index speeds up reads and slows down writes: each row written must be inserted into each one. Keep the indexes that are actually used.
An index over several columns only lets a search go down the tree if the query filters on its …: the first column, then the second, in the declared order.
Show the answer
An index over several columns only lets a search go down the tree if the query filters on its leftmost prefix: the first column, then the second, in the declared order.
For an index (a, b, c), conditions on a, on a and b, or on a, b and c benefit. A condition on b alone or c alone cannot go down the tree in one go; some databases can skip the first column when it has very few values (skip scan), but that is the exception.
B-tree: what is it?
Show the answer
A balanced tree whose every node holds several sorted keys: all leaves are at the same depth, and a search goes down from the root to a leaf.
With hundreds of keys per node the tree stays very shallow: three or four levels are enough for millions of rows, so three or four reads.