1
00:00:04,600 --> 00:00:05,740
‫So let's take an example.

2
00:00:07,120 --> 00:00:13,690
‫So here's my table here, and you can see that I added another column here to correspond to the internal

3
00:00:14,440 --> 00:00:16,580
‫tuple ID or something.

4
00:00:16,620 --> 00:00:19,240
‫Some people called our ID Royte.

5
00:00:20,020 --> 00:00:25,390
‫The page number sometimes is baked into it, applied for for simplicity reasons.

6
00:00:25,930 --> 00:00:28,600
‫But here's here's the tuple ID.

7
00:00:28,630 --> 00:00:29,280
‫It's internal.

8
00:00:29,280 --> 00:00:30,490
‫It doesn't show it right.

9
00:00:31,330 --> 00:00:38,380
‫This is the physical, not the logical primary key or logical field that you have.

10
00:00:38,380 --> 00:00:39,340
‫And this is just the name.

11
00:00:39,790 --> 00:00:46,870
‫So now one choice and this is what Postgres does is actually that.

12
00:00:46,870 --> 00:00:47,160
‫Right?

13
00:00:47,710 --> 00:00:49,030
‫This is my beater here.

14
00:00:49,660 --> 00:00:51,740
‫Let's look at the definitions here.

15
00:00:52,090 --> 00:00:53,320
‫The note is this, right?

16
00:00:53,540 --> 00:00:56,800
‫So this is one node and it has two elements.

17
00:00:57,070 --> 00:00:59,200
‫And this node has three children.

18
00:00:59,560 --> 00:01:02,620
‫And because it has three children, how many elements should it have?

19
00:01:03,010 --> 00:01:03,850
‫Three minus one.

20
00:01:04,030 --> 00:01:04,600
‫Just two.

21
00:01:04,840 --> 00:01:05,160
‫Right.

22
00:01:05,200 --> 00:01:07,480
‫So if it has M, that's a minimalist one.

23
00:01:07,480 --> 00:01:11,650
‫If it has K, children has K minus one, that's the definition.

24
00:01:11,920 --> 00:01:14,170
‫And each element has two things.

25
00:01:15,340 --> 00:01:16,480
‫It has a key.

26
00:01:17,390 --> 00:01:24,020
‫Which is what you search for this case, you're creating this thing about this is an index, create

27
00:01:24,050 --> 00:01:25,640
‫an index on this ID field.

28
00:01:26,210 --> 00:01:29,360
‫So we store the keys as these values.

29
00:01:29,360 --> 00:01:29,680
‫Right.

30
00:01:30,920 --> 00:01:38,660
‫As as these keys in the key space of things, while the value becomes the tuple, that points directly

31
00:01:38,660 --> 00:01:40,790
‫to the row here.

32
00:01:41,090 --> 00:01:44,160
‫So key value also called as data pointer.

33
00:01:45,020 --> 00:01:49,220
‫And you might say, I'm saying I never actually seen this before.

34
00:01:50,600 --> 00:01:54,280
‫All the Beatriz's I looked at, there is no Payatas, only one value.

35
00:01:54,590 --> 00:01:58,060
‫And I blame the author of this over this paper, to be honest.

36
00:01:58,310 --> 00:02:06,890
‫It's like when they originally just drew the keys, although the values or the data point are inside,

37
00:02:06,890 --> 00:02:08,390
‫but they chose not to.

38
00:02:08,630 --> 00:02:15,500
‫And here's a blurb of that proving this and the figure, the A, which is the value pointer are not

39
00:02:15,500 --> 00:02:15,890
‫shown.

40
00:02:16,340 --> 00:02:16,950
‫Why?

41
00:02:17,510 --> 00:02:18,160
‫Beats me.

42
00:02:18,170 --> 00:02:21,800
‫It just all the papers, all the books.

43
00:02:22,070 --> 00:02:23,510
‫Nobody talks about this.

44
00:02:23,540 --> 00:02:32,210
‫They just show this and it confuses B threes from B plus B plus tourism, which is very confusing because

45
00:02:32,210 --> 00:02:35,780
‫that's not the actual representation of the tree to me.

46
00:02:36,020 --> 00:02:39,780
‫That is the actual representation of the actual tree on disk.

47
00:02:39,980 --> 00:02:40,760
‫If you think about it.

48
00:02:40,760 --> 00:02:41,060
‫Right.

49
00:02:42,410 --> 00:02:50,420
‫So anyway, because why am I why am I hammering on this point is because it's very critical to understand

50
00:02:50,420 --> 00:02:59,600
‫that the keys and the values exist and all nodes in a tree structure, and that is important for memory

51
00:02:59,690 --> 00:03:00,480
‫efficiency.

52
00:03:00,950 --> 00:03:03,120
‫So in the street through all this stuff right here.

53
00:03:03,410 --> 00:03:04,790
‫So one more thing here.

54
00:03:06,140 --> 00:03:13,370
‫So this root node has a value as has two elements, two and four.

55
00:03:13,670 --> 00:03:14,080
‫Right.

56
00:03:14,510 --> 00:03:14,870
‫And.

57
00:03:15,890 --> 00:03:22,720
‫Elements, nodes that is less than two goes to the left of the that element, right?

58
00:03:22,930 --> 00:03:26,990
‫This is the children child nodes between the two on four goes here.

59
00:03:27,380 --> 00:03:30,720
‫Child nodes greater than the four goes to the right.

60
00:03:31,220 --> 00:03:36,890
‫And that's that's why the trick is it has to be M minus one for this to work.

61
00:03:37,070 --> 00:03:39,300
‫Let's search for idea number three.

62
00:03:39,530 --> 00:03:44,840
‫So if you're searching for number three, you're going to read this node, which is almost one single

63
00:03:44,840 --> 00:03:45,830
‫item on disk.

64
00:03:46,010 --> 00:03:50,280
‫And think of this really on a real production database.

65
00:03:50,330 --> 00:03:52,940
‫This is going to have a lot of elements to be on.

66
00:03:52,940 --> 00:03:54,820
‫This is not just one game.

67
00:03:55,400 --> 00:04:01,090
‫So it's just going to have thousands of elements because we want to fit in single page.

68
00:04:01,340 --> 00:04:04,590
‫So there is so much stuff we can put into game.

69
00:04:05,630 --> 00:04:09,080
‫And then I'm going to read this and I'm going to ask my question.

70
00:04:09,500 --> 00:04:11,600
‫Where is idea number three?

71
00:04:11,810 --> 00:04:13,580
‫All three is between two and four.

72
00:04:13,580 --> 00:04:16,760
‫So I just eliminated this and I just eliminated this.

73
00:04:16,940 --> 00:04:24,530
‫So I'm only going to pull the pointer, the page pointer or the something called the child pointer to

74
00:04:24,530 --> 00:04:25,040
‫this role.

75
00:04:25,460 --> 00:04:28,370
‫So I'm going to take so that is another thing that I didn't show here.

76
00:04:28,370 --> 00:04:31,900
‫But it's shown as a graphic here, which is this pointer.

77
00:04:32,240 --> 00:04:35,870
‫So there is there's another value that we store here which takes space.

78
00:04:36,350 --> 00:04:37,640
‫I'm putting all the way here.

79
00:04:37,970 --> 00:04:39,860
‫So pull go there.

80
00:04:39,860 --> 00:04:41,650
‫And I just found three.

81
00:04:42,110 --> 00:04:44,960
‫Now, I'm not finding three for the sake of three.

82
00:04:44,960 --> 00:04:45,950
‫I really want seven.

83
00:04:45,950 --> 00:04:46,370
‫All three.

84
00:04:46,370 --> 00:04:46,700
‫Right.

85
00:04:46,970 --> 00:04:50,090
‫So if I find seven or three, I jump and get the value.

86
00:04:50,480 --> 00:04:58,140
‫And even even we're not really seven or three is useless here because you're going to do a full tables

87
00:04:58,160 --> 00:04:59,240
‫can define seven or three.

88
00:04:59,810 --> 00:05:06,380
‫There is more information in seven or three that tells the database which page actually to pull.

89
00:05:06,620 --> 00:05:15,050
‫Pull is not is not going to fetch the entire table is going to fetch the exact page which has seven

90
00:05:15,050 --> 00:05:15,350
‫or three.

91
00:05:15,350 --> 00:05:18,530
‫So it can have more than seven.

92
00:05:18,530 --> 00:05:20,510
‫All three can have seven or two, one on one.

93
00:05:20,510 --> 00:05:21,980
‫Anything nearby.

94
00:05:22,310 --> 00:05:22,690
‫Right.

95
00:05:23,930 --> 00:05:28,640
‫So finding one similar one is less than two goes to the left.

96
00:05:28,640 --> 00:05:33,560
‫I cancel these right and then get seven or one jump in five.

97
00:05:33,560 --> 00:05:34,300
‫Very simple.

98
00:05:34,320 --> 00:05:37,670
‫Go here, jump and then go to zero.

99
00:05:38,510 --> 00:05:42,410
‫We can add and delete keys very similarly.

100
00:05:42,410 --> 00:05:46,480
‫And I took this from University of San Francisco.

101
00:05:46,480 --> 00:05:48,800
‫I just animated this or that JavaScript.

102
00:05:49,610 --> 00:05:51,380
‫Just adding elements.

103
00:05:51,380 --> 00:05:51,590
‫Right.

104
00:05:51,590 --> 00:05:56,390
‫I'm adding elements from one to eleven because he value one at two.

105
00:05:56,720 --> 00:05:59,150
‫And this is a degree of three, by the way.

106
00:05:59,300 --> 00:05:59,600
‫Right.

107
00:05:59,600 --> 00:06:08,030
‫Which means it can have up to three children and up to three minus one, two elements or so we have

108
00:06:08,030 --> 00:06:08,270
‫one.

109
00:06:08,270 --> 00:06:11,360
‫And to add three, we split the route and then go here.

110
00:06:11,870 --> 00:06:18,950
‫As you as we add, we can see we're splitting the pages and that's split also has a cost.

111
00:06:18,950 --> 00:06:19,340
‫Right.

112
00:06:19,930 --> 00:06:23,120
‫That's why you want you don't want to split pages so often.

113
00:06:23,120 --> 00:06:28,670
‫That's why the M value should be so large that you don't really need to split as often.

114
00:06:29,570 --> 00:06:38,480
‫OK, and and these the order of elements here also matter of these, these are random.

115
00:06:39,170 --> 00:06:48,470
‫The inserts will be slower if you think about it, because you will the randomness will will cause the

116
00:06:48,470 --> 00:06:52,550
‫pages to be stored in an unordered manner.

117
00:06:52,550 --> 00:06:59,210
‫And if you added a new element that is has to go into the page or in or order fashion, then you have

118
00:06:59,210 --> 00:07:01,390
‫to split the page, split the pages expensive.

119
00:07:01,600 --> 00:07:03,350
‫So this is just a side effect of things.

120
00:07:03,350 --> 00:07:04,550
‫So this is how you add it?

121
00:07:05,460 --> 00:07:11,930
‫I don't I'm I'm not going to go through the actual theory of adding and deleting and splitting.

122
00:07:12,530 --> 00:07:12,890
‫Really.

123
00:07:12,890 --> 00:07:13,370
‫It's not.

124
00:07:13,370 --> 00:07:15,200
‫It's not I'm not interested in that.

125
00:07:15,440 --> 00:07:19,940
‫So here's the same tree that we're looking at that we just added animated.

126
00:07:20,300 --> 00:07:27,440
‫And it's very critical to understand this is the internal nodes, the middle these are leaf nodes and

127
00:07:27,440 --> 00:07:30,260
‫these are root nodes we can follow.

128
00:07:30,260 --> 00:07:33,980
‫This story essentially was like, OK, the ten is greater then.

129
00:07:33,980 --> 00:07:36,200
‫That's why you see the values of ten here.

130
00:07:36,530 --> 00:07:36,890
‫Right.

131
00:07:36,890 --> 00:07:41,600
‫And then nine is less than ten and eleven is greater than ten.

132
00:07:41,600 --> 00:07:49,700
‫So so you can search very efficiently and imagine this is expanded to thousands and thousands and thousands

133
00:07:49,700 --> 00:07:50,330
‫of nodes.

134
00:07:50,330 --> 00:07:50,720
‫Right.

135
00:07:51,380 --> 00:07:52,940
‫You can see the value of them.