1
00:00:04,620 --> 00:00:12,590
‫So blusterous, it's exactly like Vetri, but only stores the keys in internal nodes and obviously the

2
00:00:12,600 --> 00:00:13,290
‫road as well.

3
00:00:14,850 --> 00:00:20,220
‫For some reason, I think internal nodes also kind of include the road.

4
00:00:20,380 --> 00:00:25,340
‫I believe that this is a little bit of a nuance of difference, but who cares?

5
00:00:25,350 --> 00:00:27,080
‫It's the same thing, right?

6
00:00:28,680 --> 00:00:35,150
‫If we think about others values or only stored in leaf nodes, very critical here.

7
00:00:35,220 --> 00:00:47,640
‫So now these internal nodes and the root node are slim, which means I can fit more keys in my nodes

8
00:00:48,030 --> 00:00:52,320
‫because I don't need this stinking data, pages and values anymore.

9
00:00:52,570 --> 00:00:56,460
‫I just need to store my beautiful keys.

10
00:00:57,000 --> 00:01:08,850
‫So one I owe to one node, which is one single page will give me way more elements, way more keys than

11
00:01:09,210 --> 00:01:16,260
‫I would have give me if it was a simple B tree because I had to burden.

12
00:01:16,290 --> 00:01:22,710
‫I have the burden of the actual B plus the values and the data pointer, which most of them will be

13
00:01:22,710 --> 00:01:26,010
‫tossed unfortunately during the three traversal.

14
00:01:27,330 --> 00:01:33,270
‫So internal nodes are smaller since they only store keys and and they can fit more elements.

15
00:01:33,270 --> 00:01:36,600
‫I like, as I discussed, here's another important things.

16
00:01:36,600 --> 00:01:40,770
‫But not not all databases actually implement this, but it's very interesting.

17
00:01:41,520 --> 00:01:42,860
‫Leaf nodes are linked.

18
00:01:43,290 --> 00:01:45,390
‫That's what help arrange queries, by the way.

19
00:01:46,260 --> 00:01:47,730
‫They are linked each.

20
00:01:47,730 --> 00:01:51,600
‫So because all the values are stored in the leaf nodes, they are also linked.

21
00:01:51,810 --> 00:01:57,840
‫Each one points to the next leaf, not each one points the next leaf and so on.

22
00:01:57,870 --> 00:02:04,680
‫So once you find a key, you just found everything after it and everything before it.

23
00:02:05,640 --> 00:02:11,580
‫That helps arrange queries so much great for its great full range query.

24
00:02:12,990 --> 00:02:15,080
‫Here is a B of a degree three.

25
00:02:15,390 --> 00:02:16,110
‫So look at that.

26
00:02:16,500 --> 00:02:24,990
‫So you can see now we're only starting the key truly just the keys here and the page pointers, which

27
00:02:24,990 --> 00:02:26,760
‫is these white arrows.

28
00:02:28,620 --> 00:02:31,920
‫So there's the value of five to the left is three.

29
00:02:32,070 --> 00:02:39,330
‫To the right is anything greater than five, which is a beautiful node which has the value of seven

30
00:02:39,330 --> 00:02:39,840
‫and nine.

31
00:02:40,070 --> 00:02:40,450
‫Right.

32
00:02:40,740 --> 00:02:42,240
‫Seven to the left is six.

33
00:02:42,540 --> 00:02:46,190
‫To the right is ten between that is eight and so on.

34
00:02:46,440 --> 00:02:54,240
‫So you can see that the value is the keys are kind of grouped, they are duplicated and we have to do

35
00:02:54,240 --> 00:02:57,930
‫it because the leaf nodes should have everything we need.

36
00:02:58,470 --> 00:03:03,570
‫We need everything in the leifs, including the values.

37
00:03:03,840 --> 00:03:06,330
‫So there are duplicates all the time.

38
00:03:06,600 --> 00:03:10,770
‫Not all of them unduplicated, like 11 is not up here.

39
00:03:11,100 --> 00:03:11,480
‫Right.

40
00:03:12,300 --> 00:03:13,350
‫But some of them are.

41
00:03:13,860 --> 00:03:14,730
‫And that's OK.

42
00:03:14,880 --> 00:03:23,370
‫So that's a cost that have been proven to be very minimum right to the to the to the to the value we

43
00:03:23,370 --> 00:03:24,680
‫get out of this structure.

44
00:03:25,500 --> 00:03:28,710
‫So, no, look at this.

45
00:03:28,980 --> 00:03:35,640
‫If I find value one, if I find the key one, I can find the value.

46
00:03:35,940 --> 00:03:43,140
‫And there is a nice leaf pointer that points me to the next sorted key directly.

47
00:03:43,410 --> 00:03:46,710
‫So you can just jump directly to the next one.

48
00:03:46,710 --> 00:03:47,160
‫The next one.

49
00:03:47,250 --> 00:03:54,210
‫And when you look at this, this looks really terrible in a database perspective because a single node

50
00:03:54,210 --> 00:03:55,680
‫is a single page, right.

51
00:03:55,680 --> 00:04:00,960
‫As we discussed, and a single page, we have one element only that's a complete waste.

52
00:04:01,300 --> 00:04:05,370
‫You our pages in an actual database speak or large.

53
00:04:05,370 --> 00:04:10,090
‫So you going to see so many things here, not just one element.

54
00:04:10,090 --> 00:04:16,260
‫So this is a terrible example, but I can to draw a bit of a degree, I don't know, a thousand twenty

55
00:04:16,260 --> 00:04:16,620
‫four.

56
00:04:16,920 --> 00:04:18,750
‫It's very, very hard to draw.

57
00:04:19,140 --> 00:04:19,490
‫Right.

58
00:04:19,500 --> 00:04:20,850
‫It's just doesn't fit here.

59
00:04:20,850 --> 00:04:26,580
‫But you think of this does have a lot of elements and as a result, one read gives you one a lot of

60
00:04:26,580 --> 00:04:27,750
‫elements and their values.

61
00:04:27,960 --> 00:04:35,010
‫And also you get a pointer to the next one, which has a rich set of other elements that are next to

62
00:04:35,010 --> 00:04:35,430
‫each other.

63
00:04:35,660 --> 00:04:40,050
‫Let's take an example, find rows, same example that we did for the B three.

64
00:04:40,410 --> 00:04:44,010
‫But this is for the B plus three, but all the rows between four and nine.

65
00:04:45,240 --> 00:04:52,200
‫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

66
00:04:52,670 --> 00:04:54,510
‫all right, OK.

67
00:04:54,510 --> 00:04:57,270
‫Four is less than five.

68
00:04:57,270 --> 00:04:58,410
‫So I'm going to take this.

69
00:04:58,410 --> 00:04:59,970
‫I just eliminated half the three.

70
00:05:01,080 --> 00:05:01,920
‫More than that.

71
00:05:01,920 --> 00:05:03,250
‫Three I go five.

72
00:05:03,340 --> 00:05:03,920
‫Two, three, OK.

73
00:05:03,940 --> 00:05:07,760
‫Three is four is greater than three, so I'm going to take this then.

74
00:05:07,780 --> 00:05:09,310
‫OK, here's four.

75
00:05:09,760 --> 00:05:15,910
‫But really, this is still an internal node, so I have to take four is equal to four.

76
00:05:15,910 --> 00:05:17,510
‫So I also go to the right.

77
00:05:17,890 --> 00:05:19,810
‫That's one of the conditions I forgot to mention.

78
00:05:19,810 --> 00:05:25,330
‫If it's equal or equal, go to the right then we just reached here for.

79
00:05:25,960 --> 00:05:32,110
‫But guess what you find for you find five, you find six, seven and eight and nine.

80
00:05:32,350 --> 00:05:38,670
‫And if you're lucky, all of this is just a single aisle, right?

81
00:05:39,220 --> 00:05:40,930
‫Because this is just five elements.

82
00:05:41,890 --> 00:05:49,780
‫Even if it's like most of the time, like four, 400 or 500 fit in a single page, it really depends

83
00:05:50,020 --> 00:05:51,740
‫on the data pointer.

84
00:05:51,880 --> 00:05:52,590
‫What is this?

85
00:05:52,900 --> 00:06:02,020
‫If it's a short integer, like, I don't know, four bytes, then it can fit you can fit a lot of elements

86
00:06:02,020 --> 00:06:02,290
‫there.

87
00:06:02,560 --> 00:06:10,940
‫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

88
00:06:10,990 --> 00:06:12,190
‫would be really terrible.

89
00:06:12,190 --> 00:06:13,690
‫You can't find much stuff there.