Confession Time: I Never Taught You About B-Trees.
I work with databases for a living.
I teach people, and I help them via consulting.
And as far as I can remember, I’ve never written something about how b-trees work.
And I don’t ever expect to. Ever.
For decades, I felt really guilty about that. I kept telling myself, “Man, I’m not really teaching people about databases because I don’t explain b-trees. My most popular free class, How to Think Like the Engine, completely glosses over the whole concept of b-tree navigation, and I act like all of the magic is just within the leaf pages themselves. It’s not, and … I should probably explain the rest of the magic.”
But the rest of that magic just isn’t that important.
When I teach How to Think Like the Engine, I see all kinds of lights go on in peoples’ eyes, and they say stuff like, “Now I get it. Now I understand why column order matters in an index, and I’m starting to get what columns are supposed to go first, and why my query is scanning an index instead of seeking on it, and why key lookups have to be done.” They immediately do a better job of designing indexes to support their queries. As they’re walking away, I feel like I need to add, “Oh, by the way, there’s this thing called a b-tree, and it’s how you actually find the page you want, and … I mean it’s probably important, but… yeah sure you should go, because I gotta scope how much I can teach you in the limited time we have together.” I felt really guilty about that.
I stopped feeling guilty when I watched Adam Savage answer the first question in this YouTube video:
He said:
Science communication is about getting the idea across, not all the facts. I know that sounds weird, but sometimes the facts can get in the way of the understanding.
He goes on to explain much more, and with every sentence that he uttered, I found myself yelling, “YEAH! YEAH EXACTLY! PREACH!”
I’m telling you because I want to ease your pain, too.
Some of you out there wanna share what you’ve learned. You wanna write a tutorial or build a presentation, and you feel overwhelmed because you keep adding more and more onto the list of things you think it needs to include. You feel like you can’t explain topic A and topic E without covering B, C, and D in detail.
Your strategy is to:
- Come up with the concept you want to teach.
- Write your takeaway slide: the 4-6 bullet points that you want the audience to have learned during your time together.
- Write a bio of the perfect person to attend your session. How old are they? What do they do for a living? What do they know already? What terms have they never heard before?
- Write out the linear story you’re going to tell them, trying to keep it in a straight line as much as possible, without going off on tangents. You need to get them from what they know today, to knowing the 4-6 bullet point takeaways, taking them on as few detours as possible.
When you find yourself saying, “Oh but they really need to know C or else their project is screwed – but it would take too long!” – no problem, just add that to a resources slide that you’re going to cover at the end.
Your readers/attendees are not going to walk straight out of your session and go build a database server by hand! They’re just using your session as a starting point for their learning journey, and you’re going to be so excited and compelling that it’s going to motivate them to learn more. Your resources list at the end of the session is valuable, and the really motivated students are gonna devour that stuff on their own time.
Except for b-trees. People writing queries have no business learning that minutiae, and I’m tired of feeling guilty for avoiding that topic. And if you’re the kind of person who was kinda underwhelmed by how b-trees are mostly unrelated to the practical work of performance tuning, then check out my training classes.
Update one week later: okay, I finally taught you about B-trees. It was bothering me deeply.
Free, 3× a week
Get my new posts by email
Three posts a week, plus a Monday roundup of the best database news from around the web.
I totally agree. I have the same problem with the internals of a page. It feels like something you should know about but it never matters! You can read a massive chapter in a book like Kalen’s, but I have never once benefited from knowing what a slot array is or the how the engine knows which rows are ghosts.
That’s my feeling about most internals stuff. It’s thrilling to learn, and I genuinely enjoy learning about it because I care about what I do, to the point of it being a hobby, but … I understand why most people don’t, and I don’t blame them at all.
Completely agree, and love it when you share Adam’s videos – he’s got a great way of communicating.
A few years ago in work i attended a session on delivering presentations. The key takeaway was it’s not about PowerPoints or fancy slides, it’s all about you and how engaging a speaker you are, and how well you can deliver a few key points.
Fast forward a few months at a work staff conference and all but one presentation was crammed with fancy slides, a stupid number of stats and loads of detail.
People listened, but weren’t sure what they were listening to, and why they should care. People were blown away by the presentation that simplified things as it was inclusive and enabled people to follow the thread.
Very few people need to know all of the story, and the great story tellers know which bits to leave in and which bits to cut.
This is perhaps why i too own one of Kalen’s internals book – Microsoft Dave made things sound so simple….
I agree with you. Yet I just need to ask: Have you ever programmed a b-tree?
Nope! And absolutely no interest in doing it.
B-trees? Now, that’s a name I’ve not heard in a long time. A long time. They’re something every programmer learned 40+ years ago right after binary notation, pointers, singly-linked, and doubly-linked lists. In the bad old days of programming, when you were limited to a 16K data segment and needed to process more data than would fit in an array, a b-tree was the quickest way to get to each piece of the data. It was painfully slow, but it was the best alternative. the concept is the same for traversing SQL pages. The only thing I really learned about them is to completely fill them, just reverse the bits and fill in order – in short, 0001 becomes 1000 and starts at the top, then 0010 becomes 0100 and becomes the first leaf on the left, 0011 becomes 1100 and is the first leaf on the right, etc. etc. etc.
I agree don’t teach B-trees, but B+ trees instead 😉
I also agree. That being said — and particularly if you’re a programmer, too — it doesn’t hurt to learn about them elsewhere. As I used to tell my students, never turn down learning. It’s the only thing that’s truly yours 8)
I dunno, I wouldn’t say never there. Remember that your students need a work/life balance. You don’t want to drill into them, “You have more work to do, and never stop doing it” – because there will be times in their lives when they need to invest in their personal life, their health, their relationships, their families, etc.
I’m constantly reminded of Lori Edwards’ saying: “Remember that the people you really work for are waiting for you at home.”
I’ve implemented both B-trees & Red-Black trees (in Borland Pascal). IMO the world might have been a better place w/ Red-Black, but again that train has sailed.
I will have to look up Rad-Black trees. Never heard of that structure before.
Me neither.
Some quick Googling suggests that B+ trees are better optimized for on-disk data-structures than Red-Black trees. E.g., R-B trees are binary trees, so they tend to have more levels and thus more disk traversals than B+ trees.
You’re already more educated on this than me! I’ve never heard of R-B trees.
PASCAL! There’s a name I haven’t heard in a while.
LOL. I was a usenet moderator for Pascal back in the day…
I loved you in wall street!!!!!
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
I have to strongly disagree… Of course, I was also a grand fan of the “Connections” series.
In the world of SQL, learning something “with the case on even though the case shouldn’t be there” is frequent the source of seriously incorrect BandWagon.
I’m curious – which specific part of the post do you disagree with?
My apologies. I didn’t mean to be so vague nor so late on a response.
I agree that trying to teach something like what is in the Wikipedia article that you linked to prior to explaining what an Index Seek is, is, in fact, totally unnecessary overkill. But explaining what is necessary for understanding is not overkill… it’s required. To wit, you post simplified B-Tree diagrams all the time in your ‘tubes, talks, and articles.
Looking back on all of those, have you ever intentionally posted something that was wrong/incorrect in those diagrams just for the sake of simplification or brevity? I cannot remember you ever doing so.
Rather, you teach in a style like the old “Connections” series. You don’t necessary “connect” what seem like totally unrelated things but you always seem to use the correct “order of revelation” for understanding, just like they did in the “Connections” series. To say it again, I’ve never seen you teach something wrong just to simplify that “order of revelation”.
Teaching something wrong to supposedly “simplify things for the layman” is flat out wrong. There are a lot of shortcuts that you can take but those shortcuts should not portray something wrong. Teaching something wrong for simplification is also an insult to the layman AND it discredits the speaker. The simple “bullet in flight with the casing still on” is a perfect example of what to never do. In an attempt to simplify, they have portrayed an untruth… and there are a whole lot of supposed “laymen” that now think that the creator of the presentation is an idiot or couldn’t be bothered or are too arrogant to think “laymen” wouldn’t understand.
Worse yet, such publications of well-meaning but still incorrect information on the internet end up snowballing because AI finds what’s popular, even if it’s wrong, and that causes people to write about it the same wrong way, and it becomes a vicious, rapidly amplified, self-sustaining circle of bad info.
Ah, we totally agree then.
I only learned about the “bullet in flight with the casing still on” last week from Adam Savage’s YouTube channel, hahaha. I don’t know how I missed that. Conceptually, I know exactly how bullets work, but if you showed me a video and the bullet still had the casing on, I wouldn’t have noticed it or called it out. So funny.
Yeah, you’re right, I work hard not to show anything incorrect. In How to Think Like the Engine, for example, I start the nonclustered index part saying I created an index on LastAccessDate and Id, just to avoid explaining how the nonclustered indexes all have the Id in them anyway, and then I proceed to explain that like 10-15 minutes later because it’s important to know too – I just gotta take them on the journey first.
I kinda think of people taking screenshots of individual moments of the training, at any given point in time that I can’t control, and the stuff that’s on the screen at that point has to be correct. I might omit details, but it can’t be WRONG, for sure.
Can you elaborate? I too, was a gigantic fan of Connections.
Hi Chris. Apologies for the late reply. See my response to Brent above and thanks for the question.
[…] can seek to the page that has the row you’re looking for.” That’s always kinda bothered me, so I finally gave in to temptation and whipped up an animated example of a clustered index on the […]
Nice read. Nice animations.
Thanks!
Many, many years ago when I was at Bell Labs and the only database available was Hierarchical database “Ramis” I needed something for an application I was writing that didn’t need the heavy load of Ramis that I could delivery with the tool I was writing. Therefore, I wrote a B-Plus tree database and used it in the application which basically was a spreadsheet written in C using the Curses screen manipulation library. Ya, long before Excel or Supercomp20.