What if neither sibling can accept the merge? I was thinking about replacing the underflow and it's left/right siblings with three new pages with the data distributed evenly - a third of the data per page.
at 16:55 you say that by deleting entry with key 73 causes the leaf node to underflow. since there is only one entry remaining in the leaf, we need to merge it with (here) its predecessor in the ISAM. however, what if the pre-/post-successors are full already? this would then trigger a split again, right? and if we split, we distribute the entries evenly among the old and the new leaf.
+Immanuel Haffner yes, this may lead to an oscillating situation; there are many options for handling this; we discuss this as part of the LAB of the database systems course at Saarland University
Why a split is necessary? In that case we might just move some elements from the fully occupied leaves to the underflow leaf and then update the parent node pivot?
at around 10:35 shouldn't the split() function take newChildPivot as argument? i think its necessary to compute the new pivot element. this is similar to 12:38 where the split() function should take the key as argument.
+Immanuel Haffner in 12:38 the split is independent from the key we are trying to insert; the newLeafPivot is then checked in the if-statement to determine whether we need to insert in the old or the new leaf; likewise, in 10:35, for the node split, it is a similar situation: the split on the subtree is independent from the key being inserted; we only know there was a split, i.e. newCHildNode != null, hence we need to perform an insert to a new subtree in this node; the overflow condition for this node follows the same logic as the one for leaves in 10:35
+Jens Dittrich thanks, i now see that the split is independent of the inserted key. however, if i use the key, too, for computing the median, i think we might get a better (more equal) distribution among the nodes. Maybe we can discuss this in the LAB. regards.
Hi Jens, I think what Saikiran Ponnana was saying is that your figure is a little bit misleading, because in the 'after' part, value 73 is doubled in the both in the leaf and in the father nodes. Anyway, thanks a lot for this presentation. Very good stuff!
This is one the best educational online materials on database science.
Thank you very much!
What if neither sibling can accept the merge? I was thinking about replacing the underflow and it's left/right siblings with three new pages with the data distributed evenly - a third of the data per page.
at 16:55 you say that by deleting entry with key 73 causes the leaf node to underflow. since there is only one entry remaining in the leaf, we need to merge it with (here) its predecessor in the ISAM.
however, what if the pre-/post-successors are full already? this would then trigger a split again, right?
and if we split, we distribute the entries evenly among the old and the new leaf.
+Immanuel Haffner yes, this may lead to an oscillating situation; there are many options for handling this; we discuss this as part of the LAB of the database systems course at Saarland University
Why a split is necessary? In that case we might just move some elements from the fully occupied leaves to the underflow leaf and then update the parent node pivot?
Prof. Dr. Jens Dittrich sir source code
at around 10:35 shouldn't the split() function take newChildPivot as argument? i think its necessary to compute the new pivot element.
this is similar to 12:38 where the split() function should take the key as argument.
+Immanuel Haffner in 12:38 the split is independent from the key we are trying to insert; the newLeafPivot is then checked in the if-statement to determine whether we need to insert in the old or the new leaf; likewise, in 10:35, for the node split, it is a similar situation: the split on the subtree is independent from the key being inserted; we only know there was a split, i.e. newCHildNode != null, hence we need to perform an insert to a new subtree in this node; the overflow condition for this node follows the same logic as the one for leaves in 10:35
+Jens Dittrich thanks, i now see that the split is independent of the inserted key. however, if i use the key, too, for computing the median, i think we might get a better (more equal) distribution among the nodes. Maybe we can discuss this in the LAB. regards.
Shouldn't 60 be in one of the leaf nodes/blocks at 3:00?
no, 60 is just a pivot element and not an entry itself, entries are only allowed on the leaf level in this type of b-tree
@@jensdit I see. Thanks for the reply!
In Splitting of BTree,73 will not exist in leaf node further.
+saikiran ponnana not sure what you mean, key 73 is moved to the new leaf which is the expected behavior
Hi Jens, I think what Saikiran Ponnana was saying is that your figure is a little bit misleading, because in the 'after' part, value 73 is doubled in the both in the leaf and in the father nodes. Anyway, thanks a lot for this presentation. Very good stuff!
Thumbs up for using polymorphism in implementation. You make me regret not going German for undergraduate education.
Source code
nice! Thank you :)