B-Tree & B*-Tree Explained - Algorithms & Data Structures #23

Key Takeaways

[Music] what is going on guys welcome back to algorithms and data structures tutorial series in today's video we're going to talk about b trees which are also self-balancing trees and up until now i've talked about binary search trees and avl trees that are also self-balancing and um the reason we introduce b-trees is because when we get to big data sets or big sets of data we usually don't save these in the ram so the access time is uh much much longer because the random access memory of course is way faster than uh the external storage meter that we save these big data sets on and also these external storage media usually have a block oriented structure which means that when you access one thing you access the full block not just one individual element but you access the full block and because of that it makes sense to come up with a kind of tree structure that allows you to store information in blocks and thus limit the height of the tree because when you limit the height of the tree and you can still do all the operations in logarithmic time it's not only logarithmic runtime complexity which is already very good but you also have a very very small height which means that the logarithmic or the logarithm of the elements is actually very small so you don't only have a very efficient runtime complexity but you also have very few levels that you can navigate to and this is a very good thing because because of that we limit the amount that we have the amount of times that we have to access data or we have to to ask left or right for example or left right or middle for example so this is what we're going to do today we're going to talk about b3 so let us get right into it so now let's look at this example of a b tree here we're not going to talk about the formal definitions the exact formal definitions too much we're just going to take a look at what a b tree has to be kind of and then we're going to talk about how to rebalance it how to insert elements find elements and so on now every b tree has a certain order and this order in this case is 3 so m is the variable for the order in this case we have a b tree of order three uh and this means that we can have a maximum of m child nodes now in this case you can see uh of three child nodes sorry um in this case you can see here we have three child nodes we have so this thing here is one note one block uh and this one block here can have three children as a maximum but at the same time it has to have m divided by two and the result sealed so rounded up uh child notes as a minimum so except for the root note example uh for example the root note has to have a minimum of two children the root note has to have a minimum of two children but all the other notes except for the leaf nodes of course have to be i have to have a minimum of m divided by 2 and the result sealed child nodes in this case 3 divided by 2 is 1.5 and 1.5 sealed is two so we'd have a minimum of two child nodes um what does that mean this means that if we are below the minimum or above the maximum we have to open up a new level we have to reshift values we have to rebalance the tree adjust the structure so that we can fulfill this property also the amount of child nodes has always to be larger than the amount of keys so if i have two keys here i have three child nodes if i have one key i have two child nodes if i would have a b tree of order six or something and i have five keys i would have to have six child nodes and so on so this is another rule that has to be fulfilled when we're talking about b trees and one rule that's also very important is uh all the leaf nodes are at the same level the leaf nodes are at the same level which means that we cannot have um a bunch of them here and then you know i mean doesn't make sense anyway now but i cannot just go ahead and open up this here as a new level and then i have some leaf trees here um leaf nodes sorry leaf nodes here and then some leaf nodes here all the leaf nodes have to be at the same height at the same level and those are basically the criteria for a b tree and once these criteria or as soon as these criteria are not fulfilled anymore we need to rebalance restructure and do something about it so let's go ahead and try to insert a new element and unbalance the tree or violate these criteria to see what happens now let me just delete this real quick and what we're trying to do now is we're going to add the element 80 to the b tree and see what happens and see how we can rebalance it now if you want to add the element 80 i go to root note it's 25 so i need to go to the right then we have 37 44. uh 45 sorry 80 is larger than 37 so we're not going to the left it's also not in between 37 and 45 because then we would have to go down here that's not the case uh but it's larger than 45 so we need to go to the right and then we have those two keys here so we have 67 77 and um actually would have to go to the right but since we're at the leaf level we just append it here into the same block and see what happens now the problem is that we have a block of three with three keys which is not allowed because we have the order three which means that the maximum amount of keys is two because the child notes has always always have to be larger than the keys and the keys cannot be larger than two if the child's notes have a maximum of three or are a maximum of three so what we need to do now is we need to adjust so what we do is we shift up the center value one level uh shift it up one level yes so what we do is we essentially say by 77 and we shift it up uh into this level here so actually let me just delete a bunch of things here so that it doesn't look too messy we'll just delete this uh so actually 77 is removed from this leaf level here and what we would do next is i'm also going to delete the 80 here and rewrite it so now we have 80 down here and we have 77 up here uh but now we have the same problem here because um here we also have three keys and of course you know what i could do is i could say okay then we have 80 because obviously we need to do it like that or something but that doesn't make sense because we are not going to leave 77 here because we have a b3 of order 3. so what we do here next is we shift up the center value again and what happens then is we shift up 45 into the root note um and then essentially what happens is we remove it and we essentially replace it by 77 we replace the position by 77 with 77 and i'm not sure what number it was 45 uh i think it was 45 and then we end up with this year and because we end up with this here we have two keys and three child nodes we cannot just have two child nodes and two keys we need to um say the middle points to 37 and the right points to 77 so let me maybe again clear this up a little bit here so that we don't have it too messy um i'm just going to delete these red arrows here and redraw the 45 so what we would do is we would say okay these are now separate blocks so again we're going to split them like that and we have 37 here and 77 here and then we connect those two and then we say okay to the right you have 80 to the right to the left you have 67 so essentially you also split these two notes here come on don't do any dumb here we have 80 here and 67 to the left it's not the most beautiful tree that you can draw but that's essentially what you do when you enter an element and the structure violates the criteria you shift up the center element because we had three keys at the leaf level so we shifted up the center key then we had three keys at one level above that we had to shift the center key again and now everything's fine because we have two keys that's okay in a b3 of order three we have a balance structure here we can find elements in logarithmic runtime complexity it's not a problem and all these criteria are still satisfied and met remember we had the leaf nodes leaf nodes same level leaf nodes had to be at the same level level uh and all these um all this criteria here is satisfied so the b3 is rebalanced now let's look at what happens when we delete elements and violate the criteria what happens then is uh i mean it depends on what kind of deletion you perform because in b-trees you have many different scenarios for insertion and deletion my recommendation to use if you want to get a basic understanding of what's happening or not a basic but a deep understanding of what's happening i would recommend going online and typing b3 simulator into google or dr go whatever and uh play around with it a little bit because reading the formal definitions you know you can learn it you can memorize everything but i think you'll get more of an intuition by playing around with a simulator with a visualization tool uh you can also additionally uh go to a textbook and read all these definitions there but i think they're going to confuse you more than just playing around with the simulator uh but essentially you know if you delete a read if you delete a leaf node what happens is you essentially just rotate so that the missing place gets filled up so in this case if we delete 22 for example what would happen is we would of course delete 22 and then the obvious thing to do here is you just have to rotate so that 15 ends up at that position here and you shift 11 so you shift 11 up here and 15 down here and you'll rotate basically in similar way to uh the avl tree rotation so that you end up with 4 at the left side and 15 on the right side and in general it's 11 up here so that's a single rotation a very simple rotation if we delete a if you delete a leaf node now what happens when we delete a node in between in a level in between uh this is a little bit more complicated but it's still very similar to the avl rotation so if we delete 15 for example what happens now is we rotate the whole tree so we say this is a rotation here and what happens is we have 25 here now um and we replace 25 by 37 but then we need an additional um so we say 37 but then of course we need an additional rotation here because now we have uh we have this note here removed and we have only one key at this level on the right side and because of that of course we cannot have three children here but it would also not be correct to just take 35 and put it into the same block as 43 because 35 is actually less than 37 and cannot be on the right side so what we do is we actually combine these two blocks here so actually 35 and 22 are combined so 35 and 22 are combined and that's how you rebalance the tree in an avl-like way so you essentially just rotate the way that you need to rotate in order to fill up the empty slots and then you um make sure that the individual elements are on the right side like not on the right side but on the correct side and as i said if you want to get a real good feeling about this a really good intuition about this i would recommend playing around with a visualization tool uh there are a lot of visualization tools for b-trees online because as i said i don't see a lot of value in reading the exact definitions unless you want to program an algorithm with it or something like that but in order to understand what b-trees actually does and how they balance them rebalance themselves and so on i think it's enough to just play around with the simulation tool now last but not least we're going to talk about why this is possible in logarithmic time again uh obviously because the rotations in the same way that it was true for the avl trees we're not going to have more rotations than there are levels um or at least not single significantly more so we'll end up with logarithmic runtime complexity and also when we have when we add elements we need to shift up shift up shift up and so on but we cannot shift up more times than their levels because then of course we would be above the root note and this doesn't make sense so all these operations finding elements adding elements inserting elements removing elements or rebalancing the tree everything is possible in logarithmic time but b trees have the additional advantage that we have data saved in blocks and because we have more data in one node in one block we have less less many times uh we need to access less many times and this is very beneficial when it comes to external storage media with a block-like structure or block-oriented structure so last but not least we're going to talk about b star trees which are a little bit special because all the notes in between here all the values in between here are just used for navigation now the b star tree has the property that all its elements all its actual values that we're interested in are leaf nodes we don't have any value that we're interested in that is not a leaf node all these values here are just values that are guiding us that are navigating us towards these values that we're actually interested in so 3 8 14 27 are just values to tell us you need to go left you need to go right you need to go to the center and so on they're not values themselves that we're interested in now this is essentially what a b star tree is and uh this this number here the value of the navigation key is always the largest element of its uh left child so in this case you know you have three because three is the largest element of its left child tree uh the actual element we're not talking about navigation elements um five is five because it's the largest element of this left subtree eight is eight because it's the largest element of the left subtree 14 is 14 because it's the largest element of its left subtree 18 because 18 left subtree 27 because 27 and so on so it's always like that and this is the pattern here we always have these in between layers in order to navigate um and the amount of actually the amount of elements that we can store at the leaf level is determined by a so-called k star parameter in this case star parameter let's say it's two in this case uh means that we can have from k star up until two k star um elements at the leaf level so you can have a minimum of two or uh a maximum of four so two three or four elements at the last leaf level you can't have less than those you cannot have you cannot have more than those because if you have more or less we're going to restructure the whole tree we're going to add an additional level or we're going to remove a level and restructure everything so that it still fulfills this criterion notice however that this parameter here is different from the m parameter from the order of the tree the order of the tree is still three here so it's an ordinary b tree but we have the property that in the leaf level we can store two to four um elements per node so this is essentially what a b tree is a b star tree is uh a b tree where we have essentially all the layers in between are just used for navigation and all the actual data is stored at the last level at the leaf node level so that's it for today's video we now talked about b trees and b star trees b star trees usually have a smaller height than b trees because you know you only need the navigation tools and all the data is stored in large blocks at the leaf level so you have a smaller size a smaller height of the tree um and you know for now we're done with the algorithms and data structures tutorial series for beginner uh for beginners there are actually more topics that we could cover here um but i want to focus more again on python projects on ai projects it was a uh an interesting tutorial series and i know that a lot of you enjoyed it and it was very popular in the beginning uh the more advanced topic got less views because probably they're either too complex or not too interesting to a lot of you guys um if there is enough demand and if i notice that there is interest in more advanced topics like p problems np problems np complete problems all these dynamic programming issues and so on um if there is demand for that and if i see that people are interested in it i might make some more videos but for now this algorithms and data structures tutorial series for beginners is done if you have any questions you can leave them in the comment section down below if you like this video or the whole series you can leave a like and let me know in the comment section by writing a comment about that also make sure you subscribe to this channel in order to see more future videos for free we're going to do a lot more python now again a lot more projects a lot more networking ai and so on um so we're going to get back to the old kind of videos here so thank you very much for watching see you in the next video and bye [Music] you