Database indexing is a core idea in computer science because it explains how databases find rows quickly without scanning every record. This cheat sheet covers common index types, access paths, B-trees, B+ trees, and design choices used in real database systems. Students need these ideas to understand query performance, storage tradeoffs, and why some searches are much faster than others.
Key Facts
- A full table scan checks every row, so its cost is approximately O(n) for n rows.
- An index stores key values with pointers to rows, allowing many searches to avoid reading the whole table.
- A B-tree keeps keys sorted and balanced, so search, insert, and delete usually take O(log n) node visits.
- A B+ tree stores all data pointers in the leaf nodes, while internal nodes store separator keys used for navigation.
- A clustered index stores table rows in the same physical or logical order as the index key, while a nonclustered index stores separate pointers to rows.
- Selectivity is the fraction of rows returned by a condition, often estimated as selectivity = matching rows / total rows.
- A composite index on (A, B, C) can efficiently support filters on A, A and B, or A and B and C, but not usually B alone.
- Every extra index can speed up reads but slows writes because insert, update, and delete operations must also update index entries.
Vocabulary
- Index
- A data structure that stores searchable key values and row locations so a database can find records faster.
- Access Path
- The method a database optimizer chooses to retrieve data, such as a table scan, index scan, or index seek.
- B-tree
- A balanced search tree where each node can hold many keys and all leaf paths have the same length.
- B+ tree
- A B-tree variant where internal nodes guide the search and leaf nodes contain the searchable entries or row pointers.
- Selectivity
- A measure of how narrow a query condition is, calculated as matching rows divided by total rows.
- Composite Index
- An index built from two or more columns in a specific order, such as (last_name, first_name).
Common Mistakes to Avoid
- Assuming every index makes every query faster is wrong because an index only helps when the query can use its keys efficiently.
- Ignoring column order in a composite index is wrong because an index on (A, B) is usually useful for A or A and B, not for B alone.
- Using indexes on very low-selectivity columns without checking the workload is often wrong because values like true and false may still match too many rows.
- Forgetting write costs is wrong because each insert, update, or delete may require changes to one or more index structures.
- Confusing B-trees with binary search trees is wrong because B-trees have many keys per node and are designed to reduce disk or page reads.
Practice Questions
- 1 A table has 1,000,000 rows, and a query condition matches 2,000 rows. What is the selectivity?
- 2 If a B+ tree index has height 4, about how many node levels must be visited to find a single key?
- 3 A database has a composite index on (student_id, course_id, semester). Which filters can most directly use the leftmost prefix rule: student_id only, course_id only, or student_id and course_id?
- 4 A column stores only three possible values: low, medium, and high. Explain why an index on this column might not improve many queries.
Understanding Database Indexing & B-Trees Reference
A database usually reads data in fixed size blocks called pages. This matters because the slow part is often moving pages from storage into memory, not comparing one value with another. A B tree is built to keep its height small, so one node can contain many keys and child links.
The database begins at a root page, chooses the correct range, then follows a few lower pages until it reaches a leaf. Wide nodes reduce the number of page reads.
Frequently used upper pages may stay in memory, which makes repeated searches faster. Balanced structure is important because no branch becomes much longer than the others.
B plus trees are especially useful for ordered data. Their leaf pages are linked in key order. After locating one matching leaf entry, the database can move through nearby leaf entries for a range such as dates in one month or scores between two values.
This is different from finding a single exact value. Ordered indexes can support sorting too.
If rows are requested in the same order as an index, the database may read index entries directly instead of collecting rows first and sorting them later. This can save memory and temporary storage work.
The query planner chooses an access path by estimating how much work each option requires. It uses table statistics, such as the number of rows, the number of distinct values, and the distribution of values. An index is not automatically useful for every condition.
A search for a rare student ID may return one row, so an index is attractive. A search for a common value, such as a status held by most rows, may require many row lookups. Reading the table once can then be cheaper.
Estimates can be wrong when statistics are old or when values are unevenly distributed. This is why a database can sometimes choose a poor plan even when a sensible index exists.
Index design starts with real query patterns. Consider a school system that filters attendance records by student, then date. An index whose first key is student and whose second key is date can locate one student before scanning only that student’s date range.
Reversing the key order changes which searches work well. The order should reflect common filters, joins, ordering, and range conditions. Some indexes include extra columns so a query can obtain every needed value from the index itself.
This is called a covering index. It can avoid fetching table rows, but it uses more storage. Students should remember that indexes are maintained structures, not free shortcuts.
Adding an attendance row requires placing entries into every relevant index. Changing an indexed value may remove one entry and add another. Good designs use a small set of indexes that help important queries while keeping updates manageable.