Summary
Simple Insert:
Leaf Node Overflow:
Internal Node Overflow:
Root Overflow:
Simple Deletion:
Redistribution/Borrowing:
Merging Nodes:
Key Alignment Rule:
Notes
Transcript
So in that way, you're going to see, hey, we are actually coming up with a tree. This is where the tree, the binary tree came from. Came from one level of index, have a building to another and then providing that all in the effort of speeding up retrieval. So larger multi-level have one problem, you've got to maintain it. So if I introduce you to the beef tree family, which is very common in new databases, especially the order preserving.
which is the main widely used variance. Then they pick B asterisks, the B link. All of these you find that they all fit into the B plus tree. Now, there's a difference between the B tree and a B+. Now, the difference only lies with the storage. You find that in just a bee tree, We're going to store We're going to store the key and the pointer.
It has a key and it's going to have the value. Hold the record. While in the B+3 this is only done in the lymph node.
So that's the difference between the B+ and the B3. Now. Yeah, so the link and then the B*, all of them fit some features into the B+3. Now how does the B+3 structure look like? First of all we say it should be a dynamic multilevel. We have seen that our tree comes from So it should be self balancing. Regardless how many operations of inserts you want to do, how many operations of deletions you want to do, there should always be a balance.
If it has one or more children, And of course This kind of algorithm is widely optimized for large large Systems. that are applied Um. commercially. So if I talk about perfectly balancing, that means every node at the leaf node or every leaf node is at the same depth.
Not the length, not the height, but the depth. Okay, so that is how you can say perfectly balancing. And if you have something like this, this is not perfectly balancing.
So A single node which is going to be our 4kb.
Key and the value pair So it can be from Q1 Value 1 key to value 2 and then key N to value N We fill up that. The arrows are kept in the sorted order so the keys are kept in the sorted order. That must be the case. Okay.
And I'm going to show you, I'm going to emphasize this when I show you an example, what I mean by a certain order in an idea. So keys are derived from the attributes that the index based on so our attributes basically generate are the keys and then the value would differ because the value is where our record is gonna be, especially if you're talking about the leaf node. But we note that hate The value in the live node and the value and the inner nodes are going to define.
So the inner nodes I'm going to have pointers Okay, so in a node, connect pointers to other nodes.
Three, So, each node is a 4KB. Okay?
The inner node and the outer node, they do not store the same data. And that's why we say, hey, if you go and look at the array inside the inner nodes, it's going to contain pointers to other blocks.
that is going to point you to the location of the two polesThe index. corresponds to And the tuple data is actually going to store the actual tuple. in the leaf node, stored in the leaf node. The actual tuple data is stored in the leaf node. These are two approaches that can help us realize this structure here, storing the actual record I'm storing a pointer pointing us to the physical location or even storing the actual record in the block.
So what is the solution here? Someone is thinking of something half semi-full. If I have, if I'm not supposed to be filled by four kids, okay, let's keep it half and just say we're only going to fill theThis we've lived in empty.
And I can ask, why are they going to emphasize the size? Sometimes the size is, they tell you n is equal to 3 and you know what n is? What did we say it is guys? Thanks, man. Yes. -Values, values, that kind. Keys, yes. So N is the maximum number of keys. And then we also have sometimes we represent it as M pointers. which is n plus 1. So n plus 1 pointer is always going to be the pointer. So this is going to be 4.
I don't want to see selecting here. Because we are going to be inserting, you cannot put 17 here. Then by principle, the first, I refer you to the first slide. They always gonna follow an order. And I've given an example of a binary search algorithm. If you give it records that are not arrayed, the first application is going to apply an array.sort. Then it sorts it, then it can apply its Binary. Get rid of one half, get rid of another half, It's so easy to get rid of husks because they're already sorted.
N. Yes, you get N and M. You can use keys. Of course, if you have keys, you can get the pointer. If you have pointers, you can get the key. So if you are given key, this is the only parameter I'm going to be giving you. I see. Assume n is 4. Can you perform these deletions? Can you perform these insertions? And then you're gonna go on with the computation. So, Why am I having these nodes that all my nodes are going to have four keys?
So this is a tree but each node is seen to be fixed size by This end. And you know what is n maximum number of keys in every single note. Thank you. That is why even if this is drawn as small, we can still see the same size of it. This is a 4KB. If we go back to our page size or a block size, 4KB, 4KB, 4KB, 4KB. Here is n is equal to 3, n is equal to 3, and it's the same thing. These are fixed size nodes.
Then we're going to look at the scenario where we need To create a new node So our leaf is going to overflow. And what does it mean to overflow? Remember if they say 1 and 3 If I say 2, 9, 10 and I'm trying to add 15, this is overflowing. You are trying to make... you're breaking the barrier. You're trying to tell me that in this note your keys are gonna be four. No! We can't do that.
So we're going to look also at the overflow and Overflow, overflowing at the null leaf and then when we are inserting in the roots. Let's look at the first scenario which we say is a simple insert And... What are we inserting? They're telling us, "Hey, We are working with the n is equal to 3.
So the reason why I'm asking you where, I want you to always be clear. Be careful that we are inserting numbers in each node should be arranged. From left to right we are arranging in ascending Order from small Go to Lines. Our power lift load needs to be like you see 3 to 32 So this is called a simple insert and now you can see it in their illustration. 32 goals right there. Okay. Let's look at the second scenario where we are going to require to insert we are going to see that the overflow, one of the nodes is going to overflow at this level here, which we call the nifnode.
which is copy app So copy up the first key In L1, first key in L1.
needs to be copied up so the word is copy up So what am I going to do? I am going to copy up to the next level. What's the next level? It's 7. So it's going to find 7.30. It's gonna find 7-30. And this is going to be our new This is going to be our new, it's going to replace this. And then of course, on top we are not replacing anything.
116 is not less than One twin. Okay. Boom. 160 is not greater than 180. But what is it? 160 is between 150 and 180. And this is the node of interest. Now, Pull out the node of interest. And what are we trying to insert? 160. So that means we are going to have 150, 156 160 and 179 in that order don't forget and write the 160 at the end just put it in the order Now we are going to apply the knowledge we just acquired.
It's going to replace this. But you know that hey, there should be an extra That extra pointer is going to come into play if you are going to copy the first key of L1. Which is 160. Where are you pushing it? Pushing it to the next level. Now the next level is also here. It's also full. You say, "Hey, I cannot squeeze you. We only three." so how is it going to be? it's going to be 120 150 160 and 180 divide also this by 2 so at this point also we are going to have L1 and L2 With only three spaces So, L1, this is going to be 120, this is going to be 150, and this is going to be 160 and this is going to be 180.
However, At the NAN lift, we are not going to use copy app. We are going to use what they call push app. So this 160 should not be here. This 160 is going to be pushed up. And here you're going to have Where's the next level? The next level we have 100.
Here it is pushed up Push up Here we copy up So when you push up here, you're going to see it right here.
Now lastly, For instance, in session,Is you are inserting a new A scenario that requires you to insert a new route. What are we doing here? They're telling us, hey, N is three. and try to insert 45. And automatically someone will see where the fortified needs to be. The root of interest is this one. But you cannot come here and say 45 and close it. No, you're violating the N-3.
There is going to be 30. It's gonna be... Let me first do it here. If I'm breaking up this, this is going to be 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Two. So this is going to be 10, 20, This is going to be, if 40, we're pushing 40 up, this is going to be 40. But because this doesn't need to be here. This needs to be pushed up so we are going to have a new route Showing 40. Pointing one there, pointing one here.
Please show each tree Show me a tree at each insertion. OK? So after you do that, please cancel that answer that you know you trapped. Just imagine you miss out a number like 31. Your tree is going to be different and you're going to fail the entire question.
So assume that each B plus three node can hold a maximum of three keys. So they give you what is N already. That is A. Construct.
And they're telling you that show individual tree at each insertion. Even if it's a simple insert, can you redraw the tree?
I provide enough space for you to draw the tree. Now, On Monday, next class, I'm going to show division. Now the previous classes have shown that about 90% get 15 out of 15 in this session. And then only 30% will get this 15 out of 15 deletion. What does it tell you? Deletion is a more complicated algorithm. Nicky?
Um 25, 30. If you remove that 30 and you're still maintaining what we call a half full, Okay. maintaining what they call a half food They say Then the deletion is straightforward. It's a simple deletion.
If this is not possible Maybe you're deleting and you're violating. N is equal to 2. They say, "Hey, we're going to try to redistribute." Try to reproduce with All borrow from Sibling. So if these two fail If redistribution fails Then we're going to match. Okay. If your neighbor cannot give you one, If your neighbor cannot give you, basically the neighbor has minimum number of keys, I cannot give you.
Thank you. Then, We are going to march. The siblings. Okay, so we're going to match the original node of interest L and the sibling on the left. We're going to first be aligning on the left. So they also note, they say, hey, Every time you do a match Make sure that you remove the entry from the parents. So the first key of L should be removed from the pair, meaning that It's coming down. It is only need to be showingSo I get this question a lot.
And I've already told you, hey, B3 remove the key from the leaf node. So not necessarily from other laws. Okay. So you have a study. You only remove the keys from the leaf nut. So, with this algorithm I am going to go back to the hour tree that we last inserted. And then we're going to continue. You're going to give me random-numbers that we need to delete based on the numbers that appear in the info.
So Three. 3 is basically going to be a simple leaf. So before you delete, you're going to calculate. Your minimum. So I need three. N plus 1 divided by 2. minus 1, you're going to find that the answer is going to be 1. That's the minimum acceptable. Here it's gonna be two. With this entrance quantified by the law. Definitely. We can play around with the mission. but do not go below two if you are a newbie.
meaning the entries okay so you can see three I am going to My next is going to look like this without that. Without that, Now in the exam, I don't want you to do this. In the exam come and draw the tree and write it 54 with the changes. The change is here which is only two alike. The rest remains the same. So, Someone is going to ask me, oh, you're using the points.
Okay, so this is minor three done. That is the three. Bill. 21 So 21. 21 is here. So 21, if I wanna get off 21, it's going to violate my n2 here. What are we going to do? You're going to ask the left sibling. This guy has a left sibling and a right sibling. Ask the next sibling. Can you help? and he has minimum number of kids. Two. Okay, cannot distribute, cannot give you. Thank you. So we go to March We're going to March.
I'm going to give you some and the ones that will still remain, I will still be okay. So, what are we giving? We are giving 54. But through again the parents. Um... through the parent so what is it gonna be so 54 is going to We are deleting Tally 8 Yeah, so it's going to be if I move It's gonna be 36. And this is going to be 80, 81. Update the parent. with the fast Now, I have to tell you that, hey, The algorithm maintains A kind of alignment between the first key of the first key in the leaf node should be corresponding to a key, an entry in the...
So 36 is goneRemember what we noted? And hey. We are deleting number from the leaf node does not necessarily mean you delete the the number from either the leaf node or the leaf. But the final answer, I'm gonna show you to update the final answer. So you can still live there as long as your route is is clear.
The other ones are going to fly out by themselves. So, um... But this is going 12, let's do 12. Well, we just came back to the initial. Okay, please draw Draw the tree minus 12. If you do this, you're going to lose marks.
Five, eight. 54, 80, and this is going to be 2, 23, 28. So this is the final tree. With this kind of alignment, make sure that the first key that we will remove should be updating the parent.
So Why am I asking you random? I want you, when you go back to Try out these numbers. Don't have to wait for an example, just generate Um... Fifteen numbers It's not them. The exam I'm bringing in is equal to three. Okay, so we're working with only three teams. Next week. In the exam. So practice that. Then after you delete everything, you can check with me, you can check with your neighbor. I want you to first check with your neighbor before you come to me.
The textbook notation requires a full node like this 21 to be written like this 21. But because it's in the exam, you just know that there are two more spaces here. So I will allow you to just write You just write your points like this. Okay, I'm not gonna penalize you. Okay, so if you have And please make sure your trees are clean, just like mine. I don't want you to, you know, Cancel, I don't want to do, let it just be clean.
Deletion. I'm bringing 14 in session. And also, I'm bringing 7th deletion So this is the deletion. And so imagine if at this point You have failed the last insatiable.
I'm not going to waste time. Everything is going to be wrong.
And The TA is going to compare your tree and my tree. And then I have a rubric that says if it's exactly this point, give two points. If someone has everything corresponding, that means you're exceptional, you did everything right. I'm going to give you two points. If you missed one thing, One or two things. We're going to give you one point. If you have more than two things wrong We're going to give you between 0 and 1.
And that section, what we've done alone, Peace. 30 out of 30. So our paper is going to be after 70. So if you do the B-trip very well, You already almost have 50%. But that is if you get it perfectly right. because the relational object perception is not going to be easy. Okay. So I wanted to do another insertion for you but you guys did not do the homework. So go back Do the summer paper. And then on Tuesday I'm going to do the same.
So that's really quick. Okay. So most of you are done for 25 and you must have come across These two right over here. Relax, too. So go to Google and just type Relax tool. Is there a relational algebra calculator or generator? How many of you have used this tool before? How many of you have used this tool? One. Two. Only two of you? Okay, this will be helping you. So this is a GitHub page by Sam University.
If I can just copy this and maybe take it somewhere So, the original algebra expression used to be like that.
Okay, if you've come up with a logic Now someone would say, hey, I don't want to use the Cartesian I want to useA joint. And this is an inner joint. Our joint is on. Those two queries are the same. The results are the same, but is the expression the same? No. Look, I'm using a bow tie. Let me take you here. These two expressions give the same result. The table is the same. But the way the query are expressed It's different.
These are called equivalent queries. Keith?
Kubernetes queries are the queries that have the same output. but they are actually not expressed the same way.
Now, When you use the tool, I want you to pay attention. to how things change How things change. Now, if you have some knowledge of the Russian algebra which I showed you You realize that This on is the same as where. Which is going to be my condition? Predicate of predicate. And the predicate is this is a join condition. It's telling me R and S are joining, but they are joining on the condition. Now If someone says let me actually add natural join Instead of joy And I broke out this Those three queries I have presented, let me take this.
And Nacho joined is going to have a unique set of attributes. So, the common attribute that is duplicated in other joints is actually is actually blocked out. And that's the only difference between natural joint and any other joint.
Natchezhene will not will return a unique set of attributes. The common attribute will not be repeated like an alger.
The tea D. I want to sum the Let me first count how many of these. Uh. T dot D as Count C&T. You see? Here's the expression I want. When they knew, expression which is a gamma Okay. I write my aggregate function And there are four items in B, unique items in B.
I want to Bye. I hate to beBye, I don't know if you-Okay. So, this is It's going to be the right.
So, if you have a challenge, You know how to write s2l. Most of you know how to write s2l. Do you know how to translate it? Do you know the symbols to use? When you click Rational Algebra, have not gone through all the symbols. This is all your own way.
Go and see how the symbols are used. Okay, lastly. You may want to do set or not Sit. Membership? So this is S. Uh, Union.
plus the folder I earlier shared Please look at the content there.
| --- | --- |