Balanced Trees: AVL, Red-Black and the B-Tree Behind Database Indexes
A balanced tree keeps its height at O(log n) whatever the insert order: with 10,000 sorted ids a plain BST is 10,000 levels tall, an AVL tree 14. We write AVL insert and rotations in C#, look at SortedSet's red-black tree through reflection, and inspect the levels and leaf chain of a real B+tree index in PostgreSQL with pageinspect.
8 Nov 2026
·
15 min
·
2
