‫So blusterous, it's exactly like Vetri, but only stores the keys in internal nodes and obviously the
‫road as well.
‫For some reason, I think internal nodes also kind of include the road.
‫I believe that this is a little bit of a nuance of difference, but who cares?
‫It's the same thing, right?
‫If we think about others values or only stored in leaf nodes, very critical here.
‫So now these internal nodes and the root node are slim, which means I can fit more keys in my nodes
‫because I don't need this stinking data, pages and values anymore.
‫I just need to store my beautiful keys.
‫So one I owe to one node, which is one single page will give me way more elements, way more keys than
‫I would have give me if it was a simple B tree because I had to burden.
‫I have the burden of the actual B plus the values and the data pointer, which most of them will be
‫tossed unfortunately during the three traversal.
‫So internal nodes are smaller since they only store keys and and they can fit more elements.
‫I like, as I discussed, here's another important things.
‫But not not all databases actually implement this, but it's very interesting.
‫Leaf nodes are linked.
‫That's what help arrange queries, by the way.
‫They are linked each.
‫So because all the values are stored in the leaf nodes, they are also linked.
‫Each one points to the next leaf, not each one points the next leaf and so on.
‫So once you find a key, you just found everything after it and everything before it.
‫That helps arrange queries so much great for its great full range query.
‫Here is a B of a degree three.
‫So look at that.
‫So you can see now we're only starting the key truly just the keys here and the page pointers, which
‫is these white arrows.
‫So there's the value of five to the left is three.
‫To the right is anything greater than five, which is a beautiful node which has the value of seven
‫and nine.
‫Right.
‫Seven to the left is six.
‫To the right is ten between that is eight and so on.
‫So you can see that the value is the keys are kind of grouped, they are duplicated and we have to do
‫it because the leaf nodes should have everything we need.
‫We need everything in the leifs, including the values.
‫So there are duplicates all the time.
‫Not all of them unduplicated, like 11 is not up here.
‫Right.
‫But some of them are.
‫And that's OK.
‫So that's a cost that have been proven to be very minimum right to the to the to the to the value we
‫get out of this structure.
‫So, no, look at this.
‫If I find value one, if I find the key one, I can find the value.
‫And there is a nice leaf pointer that points me to the next sorted key directly.
‫So you can just jump directly to the next one.
‫The next one.
‫And when you look at this, this looks really terrible in a database perspective because a single node
‫is a single page, right.
‫As we discussed, and a single page, we have one element only that's a complete waste.
‫You our pages in an actual database speak or large.
‫So you going to see so many things here, not just one element.
‫So this is a terrible example, but I can to draw a bit of a degree, I don't know, a thousand twenty
‫four.
‫It's very, very hard to draw.
‫Right.
‫It's just doesn't fit here.
‫But you think of this does have a lot of elements and as a result, one read gives you one a lot of
‫elements and their values.
‫And also you get a pointer to the next one, which has a rich set of other elements that are next to
‫each other.
‫Let's take an example, find rows, same example that we did for the B three.
‫But this is for the B plus three, but all the rows between four and nine.
‫So, OK, that's fine for WRVO for just over one one one of the OK for I'm going to read this one I
‫all right, OK.
‫Four is less than five.
‫So I'm going to take this.
‫I just eliminated half the three.
‫More than that.
‫Three I go five.
‫Two, three, OK.
‫Three is four is greater than three, so I'm going to take this then.
‫OK, here's four.
‫But really, this is still an internal node, so I have to take four is equal to four.
‫So I also go to the right.
‫That's one of the conditions I forgot to mention.
‫If it's equal or equal, go to the right then we just reached here for.
‫But guess what you find for you find five, you find six, seven and eight and nine.
‫And if you're lucky, all of this is just a single aisle, right?
‫Because this is just five elements.
‫Even if it's like most of the time, like four, 400 or 500 fit in a single page, it really depends
‫on the data pointer.
‫What is this?
‫If it's a short integer, like, I don't know, four bytes, then it can fit you can fit a lot of elements
‫there.
‫If it's a good or a eweida or a string or a blob, I don't know why would you index a blob, but that
‫would be really terrible.
‫You can't find much stuff there.