B-Trees: More Than I Thought I'd Want to Know
Recently, I’ve been reading through the excellent Database Internals (Alex Petrov, 2019). The first half of the book is dedicated to the implementation of database storage engines – the subsystem(s) of a DBMS that handles long-term persistence of data. A surprising amount of this section discusses the implementation and optimization of various B-Tree data structures.
In my college Data Structures and Algorithms course, we covered B-Trees, but I didn’t grok why I’d choose to use one. As presented, B-Trees were essentially “better” Binary Search Trees, with some hand-waving done that they had improved performance when used in database applications. I remember needing to memorize a bunch of equations to determine the carrying capacity of a M-degree B-Tree, and a vague understanding of B-Tree lookup/insertion/deletion, but not much else. Which is a shame! They’re interesting structures.
I this was partially a failure of visualization, and partly a failure of providing motivating examples. On visualization: Most B-Tree visualizations I’ve seen portray them more-or-less as n-ary trees, usually of degree 3-5. This is not wrong, but it obscures why you would actually use a B-Tree (e.g. in part, collocation of perhaps hundreds of keys in a single node).
