B-trees: Samuel’s guide
Summary: Samuel's tutorial on B-trees.
Topics: B-trees, data structures, algorithms, coding
Slides: link (pdf)
References
- R. Bayer and E. McCreight, "Organization and maintenance of large ordered indices", ACM SIGFIDET (1970)
- D. Comer, "The Ubiquitous B-tree", ACM Computing Surveys (1979)
- D. E. Knuth, "The art of computer programming, vol. 3: sorting and searching", Chap. 5.4.9 (1998)
- D. E. Knuth, "The art of computer programming, vol. 3: sorting and searching", Chap. 6.2.4 (1998)
- R. Sedgewick et al., "Algorithms", 4th Ed. (2011)
- M. T. Goodrich et al., "Algorithm design and applications", Chap. 20 (2015)
- T. Cormen et al., "Introduction to algorithms", Chap. 18, MIT press (2022)
- https://www.ibm.com/ibm/history/exhibits/storage/storage_350.html (accesssed 2022)
- E. McCreight, https://www.mccreight.com/people/ed_mcc/index.htm (accesssed 2022)
- (B-tree use in MySQL) https://www.vertabelo.com/blog/all-about-indexes-part-2-mysql-index-structure-and-performance/ (accesssed 2022)
- (B-tree use in ApFS) https://www.ntfs.com/apfs-structure.htm (accesssed 2022)
- (B-tree use in btfs) https://en.wikipedia.org/wiki/Btrfs (accesssed 2022)
- (2-3-4 trees) https://en.wikipedia.org/wiki/2-3-4_tree (accesssed 2022)
- (Current Linux B+ tree - uses linear scans) https://github.com/torvalds/linux/blob/7f317d34906c1033f0752fc137dda04e43979bb8/include/linux/btree.h (accesssed 2022)
- L. Xinyu, "Elementary Algorithms", Chap. 7 (2022)