Art of Codeartofcode
Lesson 14 of 15

9. Indexes

1
The picture to keep in your head
2
9.1 What is an index, exactly?
3
9.2 What's the difference between a full table scan and an index lookup?
4
9.3 What does an index look like inside?
5
9.4 How do composite indexes work, and what is the leftmost-prefix rule?
6
9.5 What is a covering index?
7
9.6 How do you know whether a query uses an index?
8
9.7 What does an index cost you?
9
9.8 When does an index not help, or even hurt?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
9. Indexes

Sources

3 min read+10 XP

Source notes

  • B-trees: Rudolf Bayer and Edward McCreight, "Organization and Maintenance of Large Ordered Indexes", Acta Informatica, 1972. B-tree as the default index type: PostgreSQL, MySQL InnoDB, SQLite and SQL Server documentation.
  • LSM trees: Patrick O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996. Used by RocksDB, LevelDB and Apache Cassandra per their documentation.
  • PostgreSQL features named here (hash indexes, index-only scans, INCLUDE, expression indexes, CREATE INDEX CONCURRENTLY, citext, EXPLAIN ANALYZE): PostgreSQL documentation.
  • SQLite query plans (EXPLAIN QUERY PLAN, "SCAN", "SEARCH", "USING COVERING INDEX") and expression indexes: SQLite documentation. Test run used SQLite 3.46.1.
  • Timings (6.93 ms vs 0.017 ms; 19 ms vs 91 ms for inserts) come from this chapter's test run on 2026-10-08; they vary by machine. Level 2 figures are assumptions; arithmetic computed 2026-10-08.
  • Level 3 and Level 4 code: tested 2026-10-08 (code/ch09_indexes.py, all checks pass).