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

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

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.

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👍

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

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 ...

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 channel has been a massive help for me in understanding the concepts in my algorithms class well enough to actually pass the assignments.

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.

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

This is the best visual learning channel for CS on KZfaq

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

Thank you for directly going into the subject.

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

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

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 is literally the best data structure explanation video I’ve ever seen

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

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

Your videos are awesome. Thanks, Brian!

Amazing video and explanation.

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!

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!

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

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

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 elegant explanation and animation, you cleared up my misunderstandings from when I just read about b-trees. Your little blob dudes are great communicators!!

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

One of the best, really liked it♥️🎉

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

Great video please continue making these

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

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

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

Great video! You made it very understadable.

Animation is amazing!

thanks for this bud. love it!

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.

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

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

This was such a nice review, thank you

Please keep uploading more content like this

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!

Great video! Now I understand how it works.

the expression was really simple and understandable thank you!

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.

those animations are amazing 🤩

Thank God your back ❤❤❤❤

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

Excellent article!

Very understandable and nicely taught! thanks

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.

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

Just a great explanation

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

So elegant!

Great explanation. Looking forward to LSM trees :)

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

Thank for the video

This will stay the best video or years to come

Very cool!

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.

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 🙏

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

Great video

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

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

Thanks for the vid! You earned my sub

thank you so much...

Thanks!

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

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

Incredible

Please keep it up❤

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.

spanning tree upload, good day

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

and now i know how my second favorite file system works :)

You are a good person.

Do more video about data structures, please! Thkx!

Mark Zuckerberg teaching me B-Trees, impressive

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

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

Great video. Do LSM trees next!

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.

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

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.

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

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.

Perfect

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.