I know that this video is very old, but I just wanted to leave a comment and say thank you so much! My teacher didn't really go over insertions very well, so I didn't understand why nodes would split in certain ways and why some keys would copy up while others moved. Your explanation for why that happens made it all click.
Thanks a lot for this video Sir, you are very good at explaining things! Today I'm having an exam at Data base subject, and this video helped me a lot! Thank you!
Excellent question! If nothing was ever deleted from the tree, then you are right that we would expect that every key that appears in an internal node would also be present in a leaf (but not vice versa obviously). So, withOUT deletes, we'd expect 30* as a leaf, and also 13*. But, even though I don't address deletions, the example trees that I show assume that deletions might have occurred, and when you delete a 30*, for example, you would not (necessarily) delete the 30 in an internal node
Literally only decent video on youtube about this subject that's not in indian english... Crazy. Too bad it's not a dynamic video but still really helpful
You have saved me from trying to imagine the meaning that my prof's garbled teaching about this intended to convey. It's really not hard to understand when *you* explain it.
Hello, thanks for sharing your learnings. I have a question in inserting 8 into the tree. In the root node there's a key 13. But in the leaves of the same tree, no key 13. Is that a misdrawing?
No its not. Its basically, in the given state of the tree, there would have been a possibility that the node is pushed up instead of copied up, and only represented once in the index.
Oh thank you, redistribution of keys was actually a concern of mine when trying to conceptualize making a functional B+Tree algorithm, mentally I've kept thinking, "well I'm going to have to redistribute at the root node and so what is an efficient algorithm for doing so?"
Thank you very much! Can someone explain to me, at the point when "19" is copied up for the first time and the root is full after and with the root split "19" moves up again, why is there no remaining copy on that second level of "19" in the right split? (as shown in 4:50)
Hi, Sandipan -- this video does not cover DELETION, and as I have responded a couple of years ago, it possible to have a value in an internal node (like 30) that is not in a leaf (lowermost level). So the situation, as presented, is entirely possible, representing the case where a 30 was inserted in the past, and then deleted. Remember it is at a leaf that additional information that is associated with a key (like 30) is actually stored. So when that associated information (associated with 30) is deleted, it need only be deleted at the leaf. The key (30) can still remain at an internal node to direct search of the tree. I chose to represent such cases precisely so that learners would recognize the potential for such situations that result from insertion and then deletion. Thanks for your comment!
I feel it is a valuable case which derived from 1:50 case: Add 17* instead of 19*, then after the split and sort, the copy-up value should be 20, and the one-layer-above chart should be 13-20-24-30. Am I correct?
If what I discribed is the correct procedure, then 1:50: You should not say update the "middle" value, but instead saying update the left-most value from the dynamic allocated node.
The size of the node can be anything you want, and all nodes need to have the same size. In this example the size of the nodes are 4. Then the B+ tree properties apply that all nodes need to be at least half full. So in this case all nodes need to contain at least 2 values.
At 4:30 AFTER you inserted 8 into the tree you added new nodes to the right sub tree without any explanation. I'm pretty sure its just a inconsistency but I found that confusing. Thanks the videos though.
After inserting 37, why is it also a parent node and a leaf node? This is in contrast to 13. It is a parent node, but it is not on a leaf node. Could someone please explain this to me please?
When inserting 37, we needed to create a new node or sibling, which means the parent would need another pointer to point to it. To determine the new value in the parent, by convention, we take the min value of the right child, which happens to be 37.
Hi, Tufail -- a comment that I have under my "B+ Trees Basics 1" video (B+ Tree Basics 1) might be helpful, so I repeat it here. It may be the case that your textbook has used a differing convention from mine: "Regarding the order of a B+ tree ... I have seen definitions of B+ trees that state the ORDER of a B+ tree is the MINIMUM number of entries (and therefore, each node holds between the ORDER and 2 * ORDER entries) -- this is the way I defined B+ trees. But, I have also seen B+ trees defined so that the ORDER corresponded to the MAXIMUM number of entries (and so a node holds between 1/2 * ORDER and the ORDER entries). I think its easy to adapt to the inconsistency if aware of it."
This is so perfectly pedagogical that I almost started crying, thank you.
Instablaster
yes, particularly when he gives time to do practice questions AND when he presents the prerequesites at the start!
Really great series on B+ trees. I love how specifically you speak and that you carefully choose all of your words to be extremely precise. Thank you.
Man you're a genius! Thanks a lot, my prof explained that I didn't get anything but I just watched your video and now I get it! thanks really
Best video ever on B+trees ! Thank you very much sir ! Greetings from Athens,Greece
Glad I found this. Two days before an exam and this helped me understand a whole new subject completely :D
I know that this video is very old, but I just wanted to leave a comment and say thank you so much! My teacher didn't really go over insertions very well, so I didn't understand why nodes would split in certain ways and why some keys would copy up while others moved. Your explanation for why that happens made it all click.
Douglas, thank you! I need this visual explanation with every step along the way explained!
Thank you for this, this was the best video I've seen for insertion in a b+ tree online!
it took me more time to find your video among all the not-understandable ones than to to understand once I found it. Thanks.
First time in my life I comment on a youtube. You deserve it. Thanks
This is so helpful with the adv. database I am currently studying. Thanks for the detailed demo!!
This video is great! It has helped me SO MUCH while studying for my graduate databases course! Thank you!
Thank you for the step-by-step and clear explanation!!!
When someone really knows, even baby can understand! Thanks 👌🙏
Clear and simple. Exactly what I needed. Thanks!
Just saved me! Was having some trouble understanding insertion when overflow occurs, great video!
Best video for quick knowledge about B+ tree.Thanks for uploading.
That is a great way to make us do things (pause is necessary :D )..and yes, lucidly explained..thanks a lot
Thank your for sharing your knowledge in such a simple and understandable way.
You are a champion mate. Thanks a lot Mr Douglas
This was very handy! I was trying to get a better understanding of btrfs's underlying data structure, and this video did the trick!
love this! thanks for the very clear explanation, your videos are a great resource
thank you so much sir!!! Your lecture video helps me a lot. You are a legend!!!
Thanks a lot for this video Sir, you are very good at explaining things! Today I'm having an exam at Data base subject, and this video helped me a lot! Thank you!
Amazing. Still helping people in 2023
10X better than my school professor. Hats off!
Fantastic explanation! Just what I needed for upcoming exams!
Thank you Douglas! Very well explained. Great help :)
Excellent question! If nothing was ever deleted from the tree, then you are right that we would expect that every key that appears in an internal node would also be present in a leaf (but not vice versa obviously). So, withOUT deletes, we'd expect 30* as a leaf, and also 13*. But, even though I don't address deletions, the example trees that I show assume that deletions might have occurred, and when you delete a 30*, for example, you would not (necessarily) delete the 30 in an internal node
Thank you so much.This is exactly what i needed. :)
NO Words, JUST YOU ARE THE BEST!
Literally only decent video on youtube about this subject that's not in indian english... Crazy. Too bad it's not a dynamic video but still really helpful
please make a video on B+ tree deletion also. Noone can explain better than u. Awesome lecture.
i really much impressed. thank you . before watching this video, i'd like to almost die. (final exam i have..)
Explanation on point. I recommend this video
Very clear lecture, well done. Thank you so much.
Clear voice and explanation. Thanks
Thank you for the explanation about copy and removal!
this is amazing work answers all of my question thanks so much
Very clear and very simple. Thank you sir!
Thank you for the video! It saved my grades
Thanks Douglas! Great help!
simple but best one.. save my time..
good luck..
You have saved me from trying to imagine the meaning that my prof's garbled teaching about this intended to convey. It's really not hard to understand when *you* explain it.
wow amazing demo for insertion, would like demo for deletion too
Hello, thanks for sharing your learnings. I have a question in inserting 8 into the tree. In the root node there's a key 13. But in the leaves of the same tree, no key 13. Is that a misdrawing?
+Jane Choi you are absolutely right. I am also confused by this as 13* should be in a leaf node
Error: Node overflow unhandled
No its not. Its basically, in the given state of the tree, there would have been a possibility that the node is pushed up instead of copied up, and only represented once in the index.
DAMN!! A LOT BETTER MY ******* INSTRUCTOR....THANKS
thank you very much, you save my time
THANK YOU SO ****ing MUCH! exam starts now and this is the only thing that confused me. :D
Oh thank you, redistribution of keys was actually a concern of mine when trying to conceptualize making a functional B+Tree algorithm, mentally I've kept thinking, "well I'm going to have to redistribute at the root node and so what is an efficient algorithm for doing so?"
Contrary to you belief, there aren't any videos on B+ tree deletion. I've only found B tree deletion. Everyone seems to be avoiding it
very very good explanation sir. good video.
thanks alot!!
Thank you very much!
Can someone explain to me, at the point when "19" is copied up for the first time and the root is full after and with the root split "19" moves up again, why is there no remaining copy on that second level of "19" in the right split? (as shown in 4:50)
great vid, thanks!
Fantastic video
Great video. The case of the very first insert (though trivial) should also be presented for completion though
It helps! Thanks, Fisher @Douglas Fisher
Thank you for this video.
This is perfect. Wow
very good explanation on insertion, but the b-tree to begin with is wrong. Any parent key has to be present in one of the leaf nodes.
but this can happen if you remove that key, no? I mean, you insert 5, then 5 is the key, but if you remove 5, 5 keep being the key, no?
There is an error. There is no '30' in the lowermost level.The pointer to the right of 30 in Level 1 must point to {30,33,34}
Hi, Sandipan -- this video does not cover DELETION, and as I have responded a couple of years ago, it possible to have a value in an internal node (like 30) that is not in a leaf (lowermost level). So the situation, as presented, is entirely possible, representing the case where a 30 was inserted in the past, and then deleted. Remember it is at a leaf that additional information that is associated with a key (like 30) is actually stored. So when that associated information (associated with 30) is deleted, it need only be deleted at the leaf. The key (30) can still remain at an internal node to direct search of the tree.
I chose to represent such cases precisely so that learners would recognize the potential for such situations that result from insertion and then deletion. Thanks for your comment!
At 4.31 the blue line from the root to the left child should point to the pointer that is left side of 5? Am I right? Or is it not necessary?
badass voice and great video
Great content!
I feel it is a valuable case which derived from 1:50 case:
Add 17* instead of 19*,
then after the split and sort, the copy-up value should be 20,
and the one-layer-above chart should be 13-20-24-30.
Am I correct?
If what I discribed is the correct procedure, then 1:50:
You should not say update the "middle" value, but instead saying
update the left-most value from the dynamic allocated node.
Thank you so much, wish you were my prof
Not bad, it is helpful.
great work thanks a lot !
really helpful !!! thank you a lot :)
Great advice.
thanks
Why is the node size of the internal node or root node the same i.e. 4? What size should we choose?
The size of the node can be anything you want, and all nodes need to have the same size. In this example the size of the nodes are 4.
Then the B+ tree properties apply that all nodes need to be at least half full. So in this case all nodes need to contain at least 2 values.
thanks, in b-tree stores key in internal node, but in b+tree stores key in leaf node
Very helpfull . Thank you
that's excellent
At 3:28 can't we just replace 13 at the root by 8 and change to second leaf node to 8, 13, 14, 16?
thank you very much problem solved
Good video
Thanks man
How about if we select 16* instead of 19* to add to the ROOT When splitting the tree?
By convention, the min value of the right child is chosen to be pushed to the root
Great!
thank you!
very understandable :) Thanks
At 4:30 AFTER you inserted 8 into the tree you added new nodes to the right sub tree without any explanation. I'm pretty sure its just a inconsistency but I found that confusing. Thanks the videos though.
Which would mean that its the tree after you inserted 8 and added two more nodes.
يسلم من ربااااااك
sholdnt 30 also be in a leaf node?
thanks for video
After inserting 37, why is it also a parent node and a leaf node? This is in contrast to 13. It is a parent node, but it is not on a leaf node. Could someone please explain this to me please?
When inserting 37, we needed to create a new node or sibling, which means the parent would need another pointer to point to it.
To determine the new value in the parent, by convention, we take the min value of the right child, which happens to be 37.
superb :)
thanks
Thanks.
Thanks a lot
if max key is odd , then how to divide ?
Sir I have a confusion. How is its order 2 when it's having maximum child's 3
Hi, Tufail -- a comment that I have under my "B+ Trees Basics 1" video (B+ Tree Basics 1) might be helpful, so I repeat it here. It may be the case that your textbook has used a differing convention from mine:
"Regarding the order of a B+ tree ... I have seen definitions of B+ trees that state the ORDER of a B+ tree is the MINIMUM number of entries (and therefore, each node holds between the ORDER and 2 * ORDER entries) -- this is the way I defined B+ trees. But, I have also seen B+ trees defined so that the ORDER corresponded to the MAXIMUM number of entries (and so a node holds between 1/2 * ORDER and the ORDER entries). I think its easy to adapt to the inconsistency if aware of it."
What is the order of the above tree?
nice thanks..
thanks dad
ty bro
great
i love you
Anybody please clear my confusion