db-10 — References

Primary source

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd or 4th ed., MIT Press. Chapter 18 (B-Trees) is the textbook treatment whose proactive- split / proactive-rebalance discipline we follow line-for-line. This is the single most important reference for the lab.

Original papers

• R. Bayer & E. McCreight, Organization and Maintenance of Large Ordered Indices, Acta Informatica 1, 1972. The paper that introduced the B-tree.
• D. Comer, The Ubiquitous B-Tree, ACM Computing Surveys 11(2), 1979. The classic survey; explains B+, B*, and variants. A useful read before starting db-11 where the leaves-only layout enters.

Production engines that use B-trees or B+-trees

• SQLite — pure B+-tree pager-backed; the closest analog to what db-10 + db-11 will become by db-15. https://www.sqlite.org/arch.html
• Postgres — heap files plus B-tree indexes; index pages are very similar to SQLite's internal nodes. https://www.postgresql.org/docs/current/btree-implementation.html
• MySQL / InnoDB — clustered B+-tree per table. https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-structure.html
• LMDB — B+-tree with copy-on-write pages; one of the cleanest open-source B-tree implementations to read. https://www.symas.com/lmdb
• BoltDB / bbolt — Go port of LMDB; readable and small. https://github.com/etcd-io/bbolt

Cross-lab dependencies

• None upstream. db-10 is the start of the B-tree track and imports no earlier labs.
• Downstream consumers: db-11 (pager) wraps each node in a fixed- size disk page; db-12 (SQL frontend) treats the tree as the table storage layer; db-13 (MVCC) snapshots node references rather than page bytes; db-14 (indexes) builds secondary B-trees over the primary tree's keys.