AT4 — Precomputation vs. On-Demand
A B-tree index is precomputed at write time: every INSERT or UPDATE must update the index. The benefit arrives at query time: searches that would scan the entire table instead walk the tree. The tradeoff is explicit in PostgreSQL’s query planner: for small tables or queries that touch most rows, a sequential scan is faster than an index scan (because the heap fetches following each pointer cause random I/O, which is slower than sequential I/O for large result sets). For large tables and selective queries, the index wins.
AT3 — Simplicity vs. Flexibility
A binary search tree is simple: two children per node, straightforward to implement. A B-tree is complex: variable numbers of children, node splits and merges on insertion and deletion, careful page management. The flexibility a B-tree provides — performance on disk-based storage — requires substantially more implementation complexity. PostgreSQL’s B-tree index code spans thousands of lines. The binary search tree from Book 1 is fewer than 100.