Understanding B-Trees: The Data Structure Behind Modern Databases 

I really like how the little guys turn their heads to look at the thing you're talking about :)

Beautiful explanation. I love the animations. As someone who's implemented a few persistent B-trees, allow me to point out a few more details: * This is the classic original B-tree. However, most databases use a B+tree, which is different in that the values are stored only in the leaves; keys in upper nodes just point to lower nodes. When a node splits, you don’t move the middle value up, it stays in one leaf or the other. * B-trees I’ve looked at, like SQLite, don’t have a fixed number of keys in a node. In real usage, keys and/or values are variable size, like strings, and the nodes are fixed-size disk pages (often 4kb.) The number of keys or values that fit in a node is highly variable. So instead you keep adding to a node until its size in *bytes* overflows a page, and then split. Some nodes might have a hundred keys, some might have only four. It doesn’t matter; the algorithms still work.

I didn't understand B-trees from university classes but now I do. 3 days before exam. Thank you!

Lol that's actually my first time hearing about a b tree, looks awesome and elegant and simple

Fed up with my living room being a mess, I decided to watch this. Oddly think it's going to help

Man, I remember having balancing B-Trees as assignments in my CS exams and failing to get the right answers. This video does a much better job of explaining it than any class I took in university in a fraction of the time we spent learning it. Thanks for finally getting me to understand👍

Such a simple but beautiful animation! So many channels do such complex animations but they do not realise simple animations can be so beautiful.

This is a great video. Normally, databases do not store data in internal nodes, only leaf nodes and function as intermediate pointers. Leaf nodes on the other hand contain the actual data entries or pointers to those data entries. Additionally, most databases have pointers to neighboring leaf nodes. By the way, these pointers to neighboring leaf nodes help lot with solving concurrent operations on the B-Tree.

I've been a professional developer for 17 years now. A really good one. I always knew that BTrees are used to store database indexes and that they reduce search complexity to logarithm. I knew how binary trees and AVL trees work. I always wondered how BTrees work. I was too lazy to do the reading. Now I know. Thank you.

There's an additional bonus -- nodes tend to be able to fill in some special size, like a disk block or a cache line, which allows further efficiency when doing comparisons for a search. That's why for some applications it's objectively better than even the red-black tree.

Just saying thank you from behalf of the community for those amazing visualization teaching vids and for the quality you put in them

Wow! Great explanation! Basically the same as how we learned it 45 years ago, but with these animations it takes much less time. Back than, the professor was running around with chalk to change the diagrams on the chalkboard ...

2:36 When designing a b-tree, how does the programmer determine what the maximum amount of keys in a node should be? For which applications is it appropriate to set the limit to 2, and which applications should have a limit of hundreds? There's a happy medium somewhere, but how is that happy medium calculated?

This channel has been a massive help for me in understanding the concepts in my algorithms class well enough to actually pass the assignments.

Your homework assignment: write a b tree in python that handles inserts and deletions and unit tests that validate it works correctly

I more or less knew how B-trees work already, but this was just such a neat refresher that I now want to implement it (maybe together with a couple of formal verification proofs, to show that all these properties are always maintained)

So good, the easiest explanation for such a common data structure I've seen. It's crazy how we teach all these other trees in computer science classes but leave out the most used one. I especially appreciated the performance advantages against binary trees being explained.

Awesome explanation. I always had the feeling that I almost understand how B-trees work, but I wasn't quite there yet. This video showed me the things that I was missing. Thank you!

Ha! Thanks for this. I remember coding b trees waaaay back in the early 80s. Gawd I'm old.

I love your videos. You somehow always manage to hit the right amount of details. Great job!

Thanks ! From Université Paris Dauphine students ! Luc, Silva, Faudel, Barbara, Diao, Adlene and Djena

So well animated, so simply and informatively explained. Thank you!

This is the best visual learning channel for CS on RU-vid

I've just started the CS50 AI course as background learning at work, and imagine my surprise to hear this voice again. I really enjoy your teaching style, and I'm so glad to have found more content from you!

Fantastic! I’d love a video on LSM trees and SSTables next!

I'm listening to "designing data intensive applications", and wasn't quite able to visualize a b-tree through audiobook only. This really cleared everything up. Thanks!

This is literally the best data structure explanation video I’ve ever seen

Thank you for directly going into the subject.

This is a great explainer video. Very easy to follow and I love the little robot guys.

Surer clear and simple explanation! Thank you very much for your time and effort!

Very elegant explanation and animation, you cleared up my misunderstandings from when I just read about b-trees. Your little blob dudes are great communicators!!

Your videos are awesome. Thanks, Brian!

you published this at the exact right time I have a final exam today and this will be on it and I needed to study up on it.

Very great video! Thank you for sharing, I love the style

Thank you a lot for the beautiful explanation of this topic! I always encounter the question about indexing algorithms and used data structures in databases for a data engineer position. So this video helps a lot in understanding b-trees. Thanks again!

the expression was really simple and understandable thank you!

One of the best, really liked it♥️🎉

Amazing video and explanation.

Mark Zuckerberg teaching me B-Trees, impressive

Awsome expl🙏🙏🙏 For me personaly at first was confusing that you dim not related part, I would intuitively expect get brighter the part where change was happening instead of dimming the rest.. Great work, thx for expaining 🙏

You're a legend bro... Hope u live 100 more years

I was looking to implement btrees a while back and all the literature on it were conflicting and varying. I like how you handled all the variances subtely. This is a great video, the definitive one on btrees for sure. Cheers.

There is also the B-Tree with prefix compression, which is particularly relevant if you need to store long strings as keys in the B-Tree. Once a leaf page is overflowing after a key insert, simply split it to create two leaf pages. Promote a copy of the first key from the right new page up one level, but only take as many characters from that key as are necessary to differentiate it from the last key in the left page. Do this only when a leaf page needs to be split. This approach will help save space in the upper pages up to the root. Additionally, keep in mind that if you feed a B-Tree with already sorted keys, you will end up with half-filled pages, wasting space. In this situation, the point where you split the pages will give you a choice on how to balance the B-Tree effectively.

awesome, never understood this tree until now. Thanks a lot :)

Animation is amazing!

Great video! You made it very understadable.

Very good explanation!! Congrats!! Keep it going!

thanks, very easy to understand

Great video! Now I understand how it works.

THIS IS JUST BEAUTIFUL !!!! THANK YOU SO MUCH

Great video please continue making these

That video was so well made that even I could understand. Code this algorithm is another story, though.

Stumbled upon this video by accident and I knew I heard that voice before 😂Nice to know that you have your own RU-vid channel now, Brian!

This was such a nice review, thank you

Please keep uploading more content like this

Proud to say that I am following this channel since when it has less than 100K subscribers.

Awesome video! Just one clarification: database systems typically use B+-trees rather than B-trees to allow for ISAM (range search on leave nodes).

those animations are amazing 🤩

thanks for this bud. love it!

is the first time i subscribe to a channel after i saw 5 seconds and skipped a couple of minutes after other 3 seconds. All your effort needs to be encouraged

Very understandable and nicely taught! thanks

Great explanation and graphics; however, I often used hash functions with an indexed sequential pointer search for fast record look ups. One hash, a couple of pointer traversals and I had the record needed. Very simple adds and deletes via pointers to dynamic memory.

Thank God your back ❤❤❤❤

Just a great explanation

I would love to see an implementation of this from scratch!

3:35 "Because each node branches in so many different directions we cut down on the search space quickly and we can find what we're looking for by checking far fewer nodes than a binary search tree would require" I think the video could better motivate why checking fewer nodes might be better. We check fewer nodes, but we do more work per node, so at least on the surface one might think it doesn't make a difference. I think it was also a little bit glossed over that B-Trees are self-balancing, whereas regular old binary search trees are not, at least this was the property of B-Trees that was emphasized in a DS/Alg course I took at uni.

Brilliant video! I had no idea that it was so closely related to binary trees.

Hello, thank you so much for the content, It's awesome. you're talented when it comes to explaining stuff. Thank you.

So the 'B' in 'B tree' DOES NOT stand for 'Binary'. Definately a chance for confusion there!

Excellent article!

Great explanation. Looking forward to LSM trees :)

This will stay the best video or years to come

So elegant!

Very helpul , thanks a lot you are the best ❤❤❤

Why didn't I find this great channel with unique presentation earlier?

Thanks for the vid! You earned my sub

The "monitos" (cute animations) got me engaged to watching, among the interesting information presented/narrated. Great video!🎉😊

i wish i could have a teacher that utilizes simple animations like these in class, the visualisation makes it so clear

im not joking when i say, i was literally looking into making my own db 2 days ago, but then the optimization algorithms discouraged me because it looked so complex. however, this video was so easy to grasp that i might just end up committing to the project

Thank for the video

I prefer an offset tree. Say you have a buffer or file full of nodes. Every node has a fixed offset from the head. As long as you know the head's pointer or file id you can get any node by it's offset. This causes the offset to work as a node ID which is useful for fast record access. Sticking to only offsets/indices can create an issue around adding/removing nodes at random places. This is fixed by building 2 pairs of "next" & "previous" members into the nodes. One pair is for tracking removed nodes, the other pair is for tracking assigned nodes. In code the node access would look something like this: next = head + node.assigned.nextOffset or prev = head + node.assigned.prevOffset You can attach the pairs directly to the node or via a separate list - in which case you use the determine the offset of the data by the offset of the node like this: index = (node - nodeList) / sizeof(node) data = dataList + (index * sizeof(data)) An example of where you'd want to do the latta is text. You'd want to perform common string operations on the text such as finding a sequence of characters. There're ready made functions for that sort of thing but they assume continuous data, not nodes. Identifying the node from the data can also be done easily by a similar process: index = (data - dataList) / sizeof(data) node = nodeList + (index * sizeof(node)) This gives the best of all worlds. Fast adding/removing of nodes via linked list format, fast node lookup via indices/offsets, easy to perform common operations via preexisting functions. Sorting can be fast too simply by making a list of ID & integer value pairs to be sorted by integer value. Then simply going through the actual list and 1 by 1 swapping the existing data with the data that should be there. For a file the swapping would look something like this: read( nodeList, offsetA, nodeA, sizeof(node) ) read( nodeList, offsetB, nodeB, sizeof(node) ) read( dataList, offsetC, dataA, sizeof(data) ) read( dataList, offsetD, dataB, sizeof(data) ) write( nodeList, offsetA, nodeB, sizeof(node) ) write( nodeList, offsetB, nodeA, sizeof(node) ) write( dataList, offsetC, dataB, sizeof(data) ) write( dataList, offsetD, dataA, sizeof(data) ) The integer values is a case by case thing that can be calculated upon creating the data so the sortable integer list can just be kept as a 3rd list along side the node list and the data list. I've never had a reason to use binary trees as of yet.

thank you so much...

Very cool!

Thanks!

This was great! I'd love to see one on lock free ring buffers.

Great video

Do more video about data structures, please! Thkx!

The joy of ternary hardware is comparing three keys in one op.

spanning tree upload, good day

You are a good person.

I can't believe I missed the existence of these things for decades. Wow. I just assumed B-tree was short for binary tree 🤦‍♂ I have to make one now, and plenty of tests to measure and abuse it.

Incredible

Great video. Do LSM trees next!

Great vid. Thanks. And btw which software do you use for animating your vids? They are beautiful.

Great video. I look forward to checking out your channel. Thanks. Subscribed. Cheers ...

Ok but where's the complexity comparison, time and memory complexity gains of b-trees woud have been a nice addition. Nonetheless beautiful animations and you have a great, calm explaining voice

Somehow simpler than red-black trees. I still have flashbacks to algs and data structures course where we had to make that in java, it was a pain. I could probably maybe do it now with 5 more years of experience. :P

Another amazing video! If possible, I would suggest making a video about 10-adic numbers, numbers that go off infinitely to the left of the decimal, and possibly its variants which are in other bases and prime, p-adic numbers. :D

Please keep it up❤

This is actually a beautiful data structure, it's just so well explained. I suppose you can also perform binary search on the list of numbers WITHIN a node? because it's all sorted already