Self-balancing trees are an important class of data structures. In most textbooks, red/black binary trees are introduced first, and then btrees come later, usually mentioned as a data structure used in file systems. Both data structures have asymptotically identical performance ($O(\log n)$ time for insertion, lookup and deletion). Here, I will show why, despite your textbook’s ordering, btrees ma