L8: Sometimes It Pays Not to Be Binary

<aside> 🌲

L8 — Sometimes It Pays Not to Be Binary covers multiway tree structures: B-Trees (designed for disk-based storage), B+ Trees (the practical variant with data only in leaves), and Tries (prefix trees for word/string processing). It also explains why Big-O alone doesn't capture real-world performance — hardware constraints like disk access time and cache locality matter.

</aside>

📋 At a Glance

[ ] Understand why Big-O fails to capture real-world disk access costs
[ ] Know the physical mechanics of hard drives (spinning disk, seek time ~10 ms, ~1 million × slower than RAM)
[ ] Explain why number of disk accesses matters more than comparisons
[ ] Know what a B-Tree is: a balanced multiway tree (B = balanced, NOT binary)
[ ] Understand B-Trees are optimised for disk-based storage and databases
[ ] Know the difference between B-Trees and B+ Trees (data in all nodes vs. data only in leaves)
[ ] Know the two parameters: M (max branches per node) and L (max data items per leaf)
[ ] State the B+ Tree properties (root, internal nodes, leaves, depth)
[ ] Trace insertion into a B+ Tree, including leaf splits and internal node splits
[ ] Trace search in a B+ Tree
[ ] Understand row-major vs. column-major ordering and its effect on cache performance
[ ] Know what a Trie is: a multiway tree for storing strings/words
[ ] Trace building a Trie from a set of words
[ ] Understand Trie compression (collapsing one-way branches)
[ ] Know the trade-off: Tries are extremely fast but use huge amounts of memory
[ ] Understand the key lesson: choose the right data structure for the task