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/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at [email protected] to suggest a future topic.
Support the channel: ko-fi.com/spanningtree
Пікірлер
Mark Zuckerberg teaching me B-Trees, impressive
Brian is that you? I'd recognise that voice from a mile away
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?
Never heard it called a binary search tree before. A binary tree, yes. The fact is, the algorithm employed to read data out isn't a binary search.
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!
Very understandable and nicely taught! thanks
Just a funny comment: Town C should be located exactly in the middle of town E and B 😁
Awesome video! Just one clarification: database systems typically use B+-trees rather than B-trees to allow for ISAM (range search on leave nodes).
Isnt a standard bst actually just an array? This negates all memory locality benefits of a b-tree
omg awesome
Bottom up, not top down. I get it!
Really great explanation, need you as a teacher lol, thanks
Great video. Note: At 5:43 the voice explanation on key vs left/right is incorrect and reverted.
Bro your voice, feel like I've seen a video with you in it, your face I mean Edit: Are you a Harvard prof? 🤔 Think you're one of the instructors from CS50...
What are the numbers representing? In other words is all data numbers? If so, what number is John Doe?
nicely done video, can we get a follow-up that compares b-tree that you beautifully explained to b+-tree ?
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!
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.
Modern dbs? I remember learning this over a decade ago
Or just do random access lookup in an array of data using a known index. People needlessly complicate matters.
This video is GOAT
What do you mean when you say that it's the data structure "behind modern databases"? Does this mean that a database in SQL or MongoDB is really just a B-Tree behind the scenes?
Probably a b-tree per index
@@jonathancrowder3424 What do you mean by index?
Excellent article!
Thanks!
I should subscribe only for the name of this channel ❤
So, for something like MongoDB, is your reference the ObjectID? As in, it's comparing this in order to find the document? What about finds which use another field? Also, where does indexing fit in?
I loved thisñ
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
Nice animation, how did you do it?
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.
What's the cost of the algorithm? O(logk(n))? where k is the maximum number of keys in a bucket + 1
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.
FINALLY UNDERSTAND 🔥
Perfect
B-Trees are great but Spanning-Trees are better!!!! 😉
Spent the first 10 minutes of this course thinking, 'This guy sounds so familiar!' Then I checked the description and realized, it's Brian from Harvard! Mind blown!
Hello, thank you so much for the content, It's awesome. you're talented when it comes to explaining stuff. Thank you.
That is a fascinating idea, and so succinctly and beautifully explained. Thank you so much!
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
please get new music
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!
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
The best of algorithms are always incorporated into libraries and standard libraries . Just need to know their properties
This was great! I'd love to see one on lock free ring buffers.
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.
I have one more question about databases. I know when inserting into a database that have a clustered index than it will perform a full-table sort on the indexed column so that the physical data will be sequential. But I know when performing search then it will do search as a B-tree but I know even if non-sequential data then the B-tree can still be constructed for search efficiency then why database must always sort the clustered indexing column? If the data is sorted then why not just use binary search?
But if each node has multiple pieces of data, you are still in theory dealinmg with the fetch limitation. Are the nodes sized with respect to the cache size so that in theory you will get the entire node as a chunk?
What happens if you need to delete the root node?
How do you create those animations, do you create tham programatically?
z x