I too "discovered" B-Trees (and B+Trees) recently and wrote about it: <a href="http://grisha.org/blog/2013/05/11/relational-database-on-top-of-key-value-store-explained/" rel="nofollow">http://grisha.org/blog/2013/05/11/relational-database-on-top...</a><p>I even implemented a key/value backed SQL database (using Thredis, which is Redis and SQLite) <a href="http://grisha.org/blog/2013/05/29/sqlite-db-stored-in-a-redis-hash/" rel="nofollow">http://grisha.org/blog/2013/05/29/sqlite-db-stored-in-a-redi...</a><p>SQLite3 has an awesome C implementation with copious comments if you really want to understand them, BTW.<p>The most fascinating thing about B-Trees is that the entire data structure is stored in equally sized blocks (pages), and getting a page by number is a very easy operation in block storage, which is what our RAM and hard drives are (even though back then they were tapes and punch cards).<p>Few people realize that it's not just DB's that use B-Trees, our filesystems are also largely B-Tree based.<p>It's remarkable how few today's "developers" understand how they work or even know what they are, yet they are so fundamental to everything computers do.<p>Without B-Trees our present world of computing wouldn't exist as we know it. It could be the coolest data structure ever :)