4 ms·

I had to implement a simple B+ tree for a databases class in college (since they're often used when implementing databases). It was one of those assignments fe

I had to implement a simple B+ tree for a databases class in college (since they're often used when implementing databases). It was one of those assignments few people fully completed. Most completed parts of it to varying degrees. I got more than halfway through but wasn't able to complete it. It was an extremely difficult assignment and stands out in my mind. They're very interesting and very complex. Nice article!

mad_vill 5y ago
uw madison?
- jwitthuhn 5y ago
  I'm not the original commenter, but I sure did implement a B-tree for my databases course at UW Madison.
cogman10 5y ago
Perhaps it was just my professor, but what really helped was we first did red-black trees and after doing that our teacher explained to us that red black trees were just a type of B-Tree. Once you have that, it's pretty easy to go from one to the other.
- jasonwatkinspdx 5y ago
  That's the approach Sedeewick of the (in?)famous textbook takes. He also has one neat tweak that simplifies rebalancing: when traversing a B-tree for insertion, preemptively split any full nodes as you visit them. This ensures there will always been room in a parent node if child nodes force keys up.
lmkg 5y ago
Implementing a B+ tree was the final assignment in a grad-level Algorithms & Data Structures call that I took. I thought it was a reasonable assignment in that context. It felt like a good capstone to the class, building on what we had learned and finally crossing the line from toy examples to something that approached real-world usefulness. It seems very out-of-place for a databases course. Yes, B-Trees are important for a database, but I don't see how implementing one teaches you about how a database uses one or why it's important.
- ddlutz 5y ago
  I've seen quite a few database courses have you implement them, as they are the backbone for many database systems.
- Tostino 5y ago
  There are actually some pretty good database courses at CMU for example, that go into what is required to build databases from the ground up. So don't think all DB classes are the same, there are some vast differences in that type of class compared to a class teaching you how to use SQL.
  - abhishekjha 5y ago
    >There are actually some pretty good database courses at CMU for example, that go into what is required to build databases from the ground up. Can you name or link a few?
    - Tostino 5y ago
      Here is the YouTube channel for them, tons of content on there. Lectures of previous years classes, etc: https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA Also have some awesome guest speakers, and the conversations they have are often quite insightful.
- jaytaylor 5y ago
  As another data point, I implemented a B+ tree with rebalancing deletion functionality back in CS3090 at UVU circa 2008 from Dr. Curtis Wellborn. It was an undergraduate course, but the professor emphasized that everywhere else it would be a graduate-level of course. My B+ tree implementation served as the foundation for my own (shitty) DBMS ;D As a funny sidenote, the professor claimed that even Stanford DB courses had a buggy / broken algorithm for balanced deletes. While preparing the course, he'd spent a chunk of the summer doing researching it, and had developed his alogrithm in Prolog. He shared the concepts and our implementations worked fine. However, it was ultimately mostly an academic exercise, as balanced deletions come with significant tradeoffs which make it not as useful as I initially thought. Even full-fledged database systems don't typically implement B+ tree indexes with deletion+rebalancing support (the usual technique is marking nodes deleted and cleaning them up when the index is rebuilt).
nicolaslem 5y ago
I got interested in the topic a few years ago and wrote an implementation in Python[0] for myself. It's just a toy but the funny thing is that I regularly get waves of students staring the repository, probably when a teacher gives a similar assignment. [0] https://github.com/NicolasLM/bplustree https://github.com/NicolasLM/bplustree
efficax 5y ago
An in-memory b-tree or one stored on disk? The first one should not be a huge amount of work over implementing, say, a red-black tree. But sorting out the disk storage is hard (and in the end, you've just written a database!)
pkaye 5y ago
I still remember my B-tree implementation in college. The professor wanted us to run it against his data. I quickly commented up my debug prints which introduced a bug with an "if" statement and failed for some of his test cases but I got most of the credit. Later I found the cause of the bug and got pissed off for such a silly mistake.
- macintux 5y ago
  Discovering that your debugging code introduced a new bug is intensely frustrating. It's not nearly as rare an occasion for me as I would prefer.
samsquire 5y ago
Btrees can be really simple, I've written a super simple understandable readable btree here in python. https://github.com/samsquire/btree https://github.com/samsquire/btree It doesn't balance between neighbours on the left and right like some btrees do but it handles splits in a really simple way and balances otherwise. I would recommend everybody write the core algorithm in a simple language like Python first to get the core algorithm understood before trying to implement in a low level language like C or Rust.

mad_vill 5y ago

uw madison?

jwitthuhn 5y ago
I'm not the original commenter, but I sure did implement a B-tree for my databases course at UW Madison.

cogman10 5y ago

Perhaps it was just my professor, but what really helped was we first did red-black trees and after doing that our teacher explained to us that red black trees were just a type of B-Tree. Once you have that, it's pretty easy to go from one to the other.

jasonwatkinspdx 5y ago
That's the approach Sedeewick of the (in?)famous textbook takes. He also has one neat tweak that simplifies rebalancing: when traversing a B-tree for insertion, preemptively split any full nodes as you visit them. This ensures there will always been room in a parent node if child nodes force keys up.

lmkg 5y ago

Implementing a B+ tree was the final assignment in a grad-level Algorithms & Data Structures call that I took. I thought it was a reasonable assignment in that context. It felt like a good capstone to the class, building on what we had learned and finally crossing the line from toy examples to something that approached real-world usefulness. It seems very out-of-place for a databases course. Yes, B-Trees are important for a database, but I don't see how implementing one teaches you about how a database uses one or why it's important.

ddlutz 5y ago
I've seen quite a few database courses have you implement them, as they are the backbone for many database systems.
Tostino 5y ago
There are actually some pretty good database courses at CMU for example, that go into what is required to build databases from the ground up. So don't think all DB classes are the same, there are some vast differences in that type of class compared to a class teaching you how to use SQL.
- abhishekjha 5y ago
  >There are actually some pretty good database courses at CMU for example, that go into what is required to build databases from the ground up. Can you name or link a few?
  - Tostino 5y ago
    Here is the YouTube channel for them, tons of content on there. Lectures of previous years classes, etc: https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA Also have some awesome guest speakers, and the conversations they have are often quite insightful.
jaytaylor 5y ago
As another data point, I implemented a B+ tree with rebalancing deletion functionality back in CS3090 at UVU circa 2008 from Dr. Curtis Wellborn. It was an undergraduate course, but the professor emphasized that everywhere else it would be a graduate-level of course. My B+ tree implementation served as the foundation for my own (shitty) DBMS ;D As a funny sidenote, the professor claimed that even Stanford DB courses had a buggy / broken algorithm for balanced deletes. While preparing the course, he'd spent a chunk of the summer doing researching it, and had developed his alogrithm in Prolog. He shared the concepts and our implementations worked fine. However, it was ultimately mostly an academic exercise, as balanced deletions come with significant tradeoffs which make it not as useful as I initially thought. Even full-fledged database systems don't typically implement B+ tree indexes with deletion+rebalancing support (the usual technique is marking nodes deleted and cleaning them up when the index is rebuilt).

nicolaslem 5y ago

I got interested in the topic a few years ago and wrote an implementation in Python[0] for myself. It's just a toy but the funny thing is that I regularly get waves of students staring the repository, probably when a teacher gives a similar assignment. [0] https://github.com/NicolasLM/bplustree https://github.com/NicolasLM/bplustree

efficax 5y ago

An in-memory b-tree or one stored on disk? The first one should not be a huge amount of work over implementing, say, a red-black tree. But sorting out the disk storage is hard (and in the end, you've just written a database!)

pkaye 5y ago

I still remember my B-tree implementation in college. The professor wanted us to run it against his data. I quickly commented up my debug prints which introduced a bug with an "if" statement and failed for some of his test cases but I got most of the credit. Later I found the cause of the bug and got pissed off for such a silly mistake.

macintux 5y ago
Discovering that your debugging code introduced a new bug is intensely frustrating. It's not nearly as rare an occasion for me as I would prefer.

samsquire 5y ago

Btrees can be really simple, I've written a super simple understandable readable btree here in python. https://github.com/samsquire/btree https://github.com/samsquire/btree It doesn't balance between neighbours on the left and right like some btrees do but it handles splits in a really simple way and balances otherwise. I would recommend everybody write the core algorithm in a simple language like Python first to get the core algorithm understood before trying to implement in a low level language like C or Rust.