Understanding B-Trees: The Data Structure Behind Modern Databases
B-trees are a popular data structure for storing large amounts of data, frequently seen in databases and file systems. But how do they really work? What makes them efficient? In this video, we explore the inner workings of the B-tree, aiming to understand the properties that make them useful and the elegant algorithms that make working with them possible.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
You can support the Spanning Tree channel at ko-fi.com/spanningtree.
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
I really like how the little guys turn their heads to look at the thing you're talking about :)
They are very cute and innocent.
@@sid98geek True dat
He does this in every video, Sherlock.
@@Scrolte6174not everyone watches what you watch, Sherlock
@@Scrolte6174 what does that have to do with anything? even if they do it in every video you can be appreciative of it?
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.
Thank you! Very interesting!
Learning something new everyday! Thanks for the info
Yes, I was thinking about the latter point while I watched: "How do you decide on the number of keys per node? I guess you size it to just about fit into available memory, in order to minimize the number of expendive database queries." If the keys were of consistent size, you could just divide the memory you want to allocate by that size, but in most contexts I can see how it would be more practical to divide keys by size rather than by count. Do you get problems if e.g. you have adjacent large keys? Would that result in "wasted" space in a node?
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.
Lol that's actually my first time hearing about a b tree, looks awesome and elegant and simple
Elegant indeed but far more complex than a binary tree. In this case you're trading simplicity for faster search time.
@@theAcum Some say that a special case of b-tree is equivalent to the red-black tree, another strategy which is, however, a binary search tree as well.
Knock on wood before your up at 2 AM on a Red Bull and adderall fueled binge trying to figure out how to shave off 1 ms of process time.
Ain't nowhere near simple but magnificent for sure
Such a simple but beautiful animation! So many channels do such complex animations but they do not realise simple animations can be so beautiful.
Has a Wall-E kind of feeling 😊
Fed up with my living room being a mess, I decided to watch this. Oddly think it's going to help
Keep the mess in a b-tree?
use c trees
Well you're gonna need to sort it in an ascended or descended order first
@@azizayari252 What for? That happens automatically when putting it in the tree.
Christmas?a@@Y2Kvids
Just saying thank you from behalf of the community for those amazing visualization teaching vids and for the quality you put in them
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.
yeah those are known as B+ Trees
A different approach to concurrency is copy-on-write, where instead of changing a node in place you make a copy of it with the changes. This means changes don’t affect any concurrent readers since nodes are immutable. However, any nodes that point to the modified node also have to be updated to point to the new one, which means a change spreads up to the root node. (This may sound wasteful, but in practice you can modify new nodes in place because no one else can see them. So a node only has to be copied once during any transaction.) In this type of tree you can’t have links between siblings because you’d end up having to copy all the siblings too. Instead, when you’re going down the tree you keep a breadcrumb trail, your path, and to get to a sibling you look up, move one child, and go back down. This type of tree is used by CouchDB and LMDB, among others.
You're a legend bro... Hope u live 100 more years
This channel has been a massive help for me in understanding the concepts in my algorithms class well enough to actually pass the assignments.
MIT opencourseware also do a great series on algorithms plus the professor is SUPER CUTE he's the dude into origami
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.
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)
This is the best visual learning channel for CS on KZhead
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 ...
I love your videos. You somehow always manage to hit the right amount of details. Great job!
Ha! Thanks for this. I remember coding b trees waaaay back in the early 80s. Gawd I'm old.
Which language do you used to code in 80s?
_"early 80s"_ OK boomer! I'm approaching my "early 80's" and I remember coding stuff waaaay waaaay back in the "early 70's" on IBM punch cards.
@@crosswalker45 vb, ada , assembler (for 6809), vulcan then dbase and clipper, kman, pascal... likely a few others i am too to recall.
@@docjoesweeney I always wonder how people in 80s, used to write the code. I'm assuming there won't be any proper documentation or persistent internet connection for that matter.
@@crosswalker45 dig up old editions of Dr Dobbs magazine. I am sure someone would have scanned them for prosperity.
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.
I agree; it's a good example of how different measures of efficiency lead to different solutions.
So well animated, so simply and informatively explained. Thank you!
This is literally the best data structure explanation video I’ve ever seen
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!
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!
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!!
Stumbled upon this video by accident and I knew I heard that voice before 😂Nice to know that you have your own KZhead channel now, Brian!
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!
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!
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.
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.
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?
It depends on your application. For example for a database system I'd go with a node size that can fit in L1 cache of the processor. Or maybe use the filesystem block size? And then delete the size by the size of an element to figure out the number of elements in a block. And then test, modify and repeat.
The best way is to simply try them and see what works best.
In practice comparisons tend to be very cheap compared to main memory access, combine that with the fact that the processor loads memory in lines of cache (64 bytes) you want to pick a node size at least 64 bytes large. The sequential prefetcher makes 128 bytes a good option too
There are a variety of locality effects that can come into play. tactic00l mentioned cache line size which is a good minimum for in-memory b-trees. You might also size them to fit nicely into a block on disk, so you can make more comparisons for each disk read operation. There are subtler impacts from prefetch logic and alignment that might be worth measuring, depending on your microarchitecture or allocator respectively. some considerations might not be just about latency of accessing memory; depending on your concurrency model, likelihood of paging, data structures you are storing as values etc you might find reason to increase or decrease the number of keys stored in a node.
This is a great explainer video. Very easy to follow and I love the little robot guys.
Your videos are awesome. Thanks, Brian!
Surer clear and simple explanation! Thank you very much for your time and effort!
Proud to say that I am following this channel since when it has less than 100K subscribers.
Dude, I just found it yesterday! It's a great channel and deserves the growth.
Amazing video and explanation.
Your homework assignment: write a b tree in python that handles inserts and deletions and unit tests that validate it works correctly
I had to make a goddamn Red Black tree in C without any external library for a single almost worthless point in university. I didn't know a data structure could have that many bugs. That thing python b tree doesn't scare me.
@@lorenzosotroppofigo1641 For real world applications, you *need* to write it in C, or some compiled language.
Very great video! Thank you for sharing, I love the style
the expression was really simple and understandable thank you!
Very good explanation!! Congrats!! Keep it going!
Thanks ! From Université Paris Dauphine students ! Luc, Silva, Faudel, Barbara, Diao, Adlene and Djena
Great video! You made it very understadable.
Thank God your back ❤❤❤❤
This was such a nice review, thank you
thanks for this bud. love it!
those animations are amazing 🤩
Great video please continue making these
awesome, never understood this tree until now. Thanks a lot :)
Great video! Now I understand how it works.
That video was so well made that even I could understand. Code this algorithm is another story, though.
Animation is amazing!
The "monitos" (cute animations) got me engaged to watching, among the interesting information presented/narrated. Great video!🎉😊
This will stay the best video or years to come
i wish i could have a teacher that utilizes simple animations like these in class, the visualisation makes it so clear
Please keep uploading more content like this
Excellent article!
Very understandable and nicely taught! thanks
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.
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 🙏
Just a great explanation
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.
Why didn't I find this great channel with unique presentation earlier?
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
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.
Great explanation. Looking forward to LSM trees :)
So elegant!
I would love to see an implementation of this from scratch!
Thank for the video
Awesome video! Just one clarification: database systems typically use B+-trees rather than B-trees to allow for ISAM (range search on leave nodes).
Thanks for the vid! You earned my sub
Great video
spanning tree upload, good day
This was great! I'd love to see one on lock free ring buffers.
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
Curious. What is your motivation to create your own DB? If you are creating DB for learning or teaching, then it is fine.There are already many open source databases, that are quite good. If you are creating your own DB, you will also need to consider caching, and a lot more features.
@@MK-lh3xd just to learn stuff tbh. In my serious projects i use postgres
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.
Do more video about data structures, please! Thkx!
Please keep it up❤
Great vid. Thanks. And btw which software do you use for animating your vids? They are beautiful.
How have I never heard or thought about that before? Greate idea to fixing binary trees most obvious shortcoming of (comparatively) lots of memory accesses.
Thanks!
Very cool!
Amazing video, I did btrees few weeks ago but I didn't get into nodes holding multiple values. That sure complicates things a whole lot. XD One small critisism I have about the presentation. I was having trouble following which nodes you were trying to highlight. My eyes would get attracted to the ones becoming darker, because those were the only ones being changed. I feel the ones you want to highlight should be the ones changing color/brightness, or both could change, the unwanted one fade away and the ones that need attention get brighter. Maybe it's just me, but I was genuinely getting confused at some points, focusing on the wrong part of the tree during explanations, and I couldn't get used to it even towards the end of the video.
You are a good person.
Great video. I look forward to checking out your channel. Thanks. Subscribed. Cheers ...
Incredible
Mark Zuckerberg teaching me B-Trees, impressive
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
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
Perfect
Great video. Do LSM trees next!
Thank you Brian for the explanation! 🤍
The drawbacks of using a binary tree variant with arrays is that the design can (both positively and negatively) impact performance on machines with varying types of CPUs. Modern CPU's with large L1 Cache sizes might have no problem at all, but if we're on an old machine and the nodes contain large objects we might have to nuke the cache to fetch data a lot more often, making the worst case a lot slower than a plain b-tree. But I wonder if you could get around that by automatically determining the type of b-tree, and size of the list on the nodes based on the CPU's L1 cache over the size of the objects on the nodes ...and also probably have it capped at 4 or something like in the video to maintain the benefits of a binary search. That would in theory give us great performance on fast machines as well as slow machines.
I have a question regarding finding data in a B-Tree. Would it not be more efficient to index all the data in the B-tree in a catalog instead of needing to go up and down the B-tree when searching for data? And would that be an alternate process outside of the tree or an internal process which stores the final data within the tree at fast to access nodes?
Hey Brian, great video! What algorithm would apply, if for instance you delete the root node (then) containing only one (or less than n/2) value(s)? I assume you cannot merge from a sibling (as there aren't any) but rearrange and merge maybe only the n-1 right most value of the subtrees to form a new root node?
In Vietnam, I learn about B-Tree which uses for files in Analyzing And Designing Algorithms. And it has some differences from your video. All key of records (of files) are stored in leaves, and other nodes are just used to storage seperant.
Thank you for this elegant explanation! What I'm wondering about, however, is that, the values in a node would have to be sorted right? That's because we need to know which interval a query falls between so as to traverse to the correct child. I'm assuming the node of a b-tree is like that of any other tree; a data member to store the values and, in this case, an array of pointers to its children. My question is, do we store the values of the node in an array and sort it each time an insertion occurs? Or maybe we could store the values of the node in a binary search tree, which would help in insertion and even in deciding which child to go to while querying. for example, a simple C implementation struct BTreeNode { int *data; BTreeNode *children[]; } OR struct BTreeNode { BST *root; BTreeNode *children[]; } where BST is a binary search tree struct.
Yes, it is fairly common to keep the keys sorted in an array and use binary search to find a match.
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
nicely done video, can we get a follow-up that compares b-tree that you beautifully explained to b+-tree ?
Great video! Could you do segment tree as well?
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
thanks
I just have one question. If you look at 3:32, once we eventually find the key we're looking for, how do we use it to retrieve the database row? If I am looking for a person with age 28, does that 28 key contain primary key or some pointer to the row so I can get the name and email?