‫So let's take an example.
‫So here's my table here, and you can see that I added another column here to correspond to the internal
‫tuple ID or something.
‫Some people called our ID Royte.
‫The page number sometimes is baked into it, applied for for simplicity reasons.
‫But here's here's the tuple ID.
‫It's internal.
‫It doesn't show it right.
‫This is the physical, not the logical primary key or logical field that you have.
‫And this is just the name.
‫So now one choice and this is what Postgres does is actually that.
‫Right?
‫This is my beater here.
‫Let's look at the definitions here.
‫The note is this, right?
‫So this is one node and it has two elements.
‫And this node has three children.
‫And because it has three children, how many elements should it have?
‫Three minus one.
‫Just two.
‫Right.
‫So if it has M, that's a minimalist one.
‫If it has K, children has K minus one, that's the definition.
‫And each element has two things.
‫It has a key.
‫Which is what you search for this case, you're creating this thing about this is an index, create
‫an index on this ID field.
‫So we store the keys as these values.
‫Right.
‫As as these keys in the key space of things, while the value becomes the tuple, that points directly
‫to the row here.
‫So key value also called as data pointer.
‫And you might say, I'm saying I never actually seen this before.
‫All the Beatriz's I looked at, there is no Payatas, only one value.
‫And I blame the author of this over this paper, to be honest.
‫It's like when they originally just drew the keys, although the values or the data point are inside,
‫but they chose not to.
‫And here's a blurb of that proving this and the figure, the A, which is the value pointer are not
‫shown.
‫Why?
‫Beats me.
‫It just all the papers, all the books.
‫Nobody talks about this.
‫They just show this and it confuses B threes from B plus B plus tourism, which is very confusing because
‫that's not the actual representation of the tree to me.
‫That is the actual representation of the actual tree on disk.
‫If you think about it.
‫Right.
‫So anyway, because why am I why am I hammering on this point is because it's very critical to understand
‫that the keys and the values exist and all nodes in a tree structure, and that is important for memory
‫efficiency.
‫So in the street through all this stuff right here.
‫So one more thing here.
‫So this root node has a value as has two elements, two and four.
‫Right.
‫And.
‫Elements, nodes that is less than two goes to the left of the that element, right?
‫This is the children child nodes between the two on four goes here.
‫Child nodes greater than the four goes to the right.
‫And that's that's why the trick is it has to be M minus one for this to work.
‫Let's search for idea number three.
‫So if you're searching for number three, you're going to read this node, which is almost one single
‫item on disk.
‫And think of this really on a real production database.
‫This is going to have a lot of elements to be on.
‫This is not just one game.
‫So it's just going to have thousands of elements because we want to fit in single page.
‫So there is so much stuff we can put into game.
‫And then I'm going to read this and I'm going to ask my question.
‫Where is idea number three?
‫All three is between two and four.
‫So I just eliminated this and I just eliminated this.
‫So I'm only going to pull the pointer, the page pointer or the something called the child pointer to
‫this role.
‫So I'm going to take so that is another thing that I didn't show here.
‫But it's shown as a graphic here, which is this pointer.
‫So there is there's another value that we store here which takes space.
‫I'm putting all the way here.
‫So pull go there.
‫And I just found three.
‫Now, I'm not finding three for the sake of three.
‫I really want seven.
‫All three.
‫Right.
‫So if I find seven or three, I jump and get the value.
‫And even even we're not really seven or three is useless here because you're going to do a full tables
‫can define seven or three.
‫There is more information in seven or three that tells the database which page actually to pull.
‫Pull is not is not going to fetch the entire table is going to fetch the exact page which has seven
‫or three.
‫So it can have more than seven.
‫All three can have seven or two, one on one.
‫Anything nearby.
‫Right.
‫So finding one similar one is less than two goes to the left.
‫I cancel these right and then get seven or one jump in five.
‫Very simple.
‫Go here, jump and then go to zero.
‫We can add and delete keys very similarly.
‫And I took this from University of San Francisco.
‫I just animated this or that JavaScript.
‫Just adding elements.
‫Right.
‫I'm adding elements from one to eleven because he value one at two.
‫And this is a degree of three, by the way.
‫Right.
‫Which means it can have up to three children and up to three minus one, two elements or so we have
‫one.
‫And to add three, we split the route and then go here.
‫As you as we add, we can see we're splitting the pages and that's split also has a cost.
‫Right.
‫That's why you want you don't want to split pages so often.
‫That's why the M value should be so large that you don't really need to split as often.
‫OK, and and these the order of elements here also matter of these, these are random.
‫The inserts will be slower if you think about it, because you will the randomness will will cause the
‫pages to be stored in an unordered manner.
‫And if you added a new element that is has to go into the page or in or order fashion, then you have
‫to split the page, split the pages expensive.
‫So this is just a side effect of things.
‫So this is how you add it?
‫I don't I'm I'm not going to go through the actual theory of adding and deleting and splitting.
‫Really.
‫It's not.
‫It's not I'm not interested in that.
‫So here's the same tree that we're looking at that we just added animated.
‫And it's very critical to understand this is the internal nodes, the middle these are leaf nodes and
‫these are root nodes we can follow.
‫This story essentially was like, OK, the ten is greater then.
‫That's why you see the values of ten here.
‫Right.
‫And then nine is less than ten and eleven is greater than ten.
‫So so you can search very efficiently and imagine this is expanded to thousands and thousands and thousands
‫of nodes.
‫Right.
‫You can see the value of them.