1 00:00:04,280 --> 00:00:06,500 ‫Might be trees, so be trees. 2 00:00:07,490 --> 00:00:14,870 ‫It's a balanced data structure for fast reversal, so the goal is to minimize the search space. 3 00:00:15,260 --> 00:00:18,350 ‫I don't want to do all these Io's to find my rose. 4 00:00:18,570 --> 00:00:18,910 ‫Right. 5 00:00:19,610 --> 00:00:20,350 ‫Did that rhyme? 6 00:00:20,360 --> 00:00:21,080 ‫I think it did. 7 00:00:22,640 --> 00:00:26,290 ‫So would be tree has a bee. 8 00:00:26,300 --> 00:00:28,000 ‫Tree has a set of nodes. 9 00:00:28,030 --> 00:00:30,290 ‫I don't want you to focus on those ward nodes. 10 00:00:31,000 --> 00:00:37,700 ‫I'm going to reference the paper or the tree paper written by Steve Fox in nineteen seventy three consist 11 00:00:37,700 --> 00:00:38,510 ‫of nodes OK. 12 00:00:38,660 --> 00:00:40,180 ‫And a B three have a degree. 13 00:00:40,190 --> 00:00:46,280 ‫We call this degree M by default and you can choose what degree your tree is right. 14 00:00:46,280 --> 00:00:51,830 ‫And the choice of how, how big or small really changes the whole equation. 15 00:00:52,040 --> 00:00:57,560 ‫And Daviess pick that automatically by the way, for you, you don't have to do and you can't configure 16 00:00:57,560 --> 00:00:58,360 ‫this to be honest. 17 00:00:59,060 --> 00:01:05,780 ‫So this degree is basically correspond to the number of child nodes each node can have. 18 00:01:06,890 --> 00:01:11,150 ‫I said some in this case because not all nodes can have children. 19 00:01:11,420 --> 00:01:13,310 ‫And I don't really care about these details. 20 00:01:13,310 --> 00:01:14,930 ‫These are all theoretical stuff. 21 00:01:14,930 --> 00:01:16,640 ‫We don't really care about it, to be honest. 22 00:01:16,850 --> 00:01:19,280 ‫We really care about the essence of the tree. 23 00:01:19,730 --> 00:01:29,330 ‫To me, the traversal aspect of this node and an A. has up to M minus one element. 24 00:01:29,510 --> 00:01:39,580 ‫So if if you node has M children, then the it has what we call M minus one elements. 25 00:01:40,010 --> 00:01:46,100 ‫So I it have five children, it must have four if it have three children must have two elements. 26 00:01:46,100 --> 00:01:47,930 ‫So you might say what is an element. 27 00:01:48,260 --> 00:01:49,490 ‫This is a good question. 28 00:01:50,210 --> 00:01:55,400 ‫So each element has a key and the value very critical thing. 29 00:01:55,410 --> 00:02:05,150 ‫So we have nodes, nodes have nodes and each node in, in it inside it has elements and these elements 30 00:02:05,600 --> 00:02:08,840 ‫of keys and a value, a key value. 31 00:02:10,170 --> 00:02:14,800 ‫The value here is usually the pointer to the rule. 32 00:02:14,820 --> 00:02:16,260 ‫It's called a data pointer. 33 00:02:16,290 --> 00:02:23,430 ‫They call it the value sometimes in the in the paper it's referred to as Alpha I. 34 00:02:24,030 --> 00:02:24,380 ‫Right. 35 00:02:24,480 --> 00:02:29,880 ‫So if you read the Bible, reference the paper in the show notes here for you to check it out and the 36 00:02:29,880 --> 00:02:31,460 ‫slides will be in the show and also as well. 37 00:02:31,800 --> 00:02:37,680 ‫So you can take a look at that and the description the value has the data pointed to the role. 38 00:02:37,680 --> 00:02:40,520 ‫And the key itself is what you're searching for. 39 00:02:40,530 --> 00:02:42,980 ‫And we're going to show an example to clarify all that stuff. 40 00:02:43,470 --> 00:02:47,820 ‫So the data point to this is this is where databases can shine. 41 00:02:48,150 --> 00:02:54,330 ‫Each database system does this differently as a data point, which is a value here can either point 42 00:02:54,330 --> 00:03:02,310 ‫to the primary key if you have a secondary index or a component directly to the tuple second indexes. 43 00:03:02,310 --> 00:03:08,300 ‫And A.B. in Mystikal and Oracle, I believe, point to the primary key. 44 00:03:08,760 --> 00:03:14,580 ‫Well, while in Postgres, all secondary indexes point to the tuple directly. 45 00:03:15,300 --> 00:03:25,170 ‫And just that I talked about the this in my YouTube channel discussing how Obama proposed goes to my 46 00:03:25,170 --> 00:03:25,830 ‫school. 47 00:03:25,830 --> 00:03:29,130 ‫And that is one of the reasons, one tiny reasons. 48 00:03:30,450 --> 00:03:31,860 ‫Check out that video if you're interested. 49 00:03:31,860 --> 00:03:36,550 ‫Just say just start from YouTube over Obama Esequiel. 50 00:03:36,930 --> 00:03:38,440 ‫I was saying you're going to find out. 51 00:03:38,490 --> 00:03:40,470 ‫The video is very, very interesting. 52 00:03:40,470 --> 00:03:40,740 ‫Read. 53 00:03:40,770 --> 00:03:47,130 ‫So there's also this Calzado fruit node and internal node and a leaf and a leaf known as well. 54 00:03:47,910 --> 00:03:51,240 ‫And that we're going to describe what all this means. 55 00:03:51,240 --> 00:03:54,620 ‫And like the root node is is very self descriptive, right? 56 00:03:54,660 --> 00:03:56,190 ‫It's the first node at the top. 57 00:03:56,370 --> 00:04:01,670 ‫Internal nodes are below it and the lymph nodes that are out of it at the end. 58 00:04:02,010 --> 00:04:03,120 ‫There is no child. 59 00:04:03,120 --> 00:04:04,200 ‫They don't have children. 60 00:04:05,290 --> 00:04:08,610 ‫A very important concept here and node is equal. 61 00:04:08,610 --> 00:04:12,180 ‫iDesk Beijng here in database's most databases. 62 00:04:12,390 --> 00:04:19,980 ‫I know in computer science they give you this, this, this contrives example where a degree of three 63 00:04:19,980 --> 00:04:26,130 ‫or degree or five and they have some put some values here that doesn't really correspond to anything 64 00:04:26,670 --> 00:04:27,510 ‫practical. 65 00:04:27,840 --> 00:04:31,580 ‫But practically and no it is a complete page. 66 00:04:31,740 --> 00:04:40,320 ‫So if a page is eight K, you better find a way to fit eight K worth of elements in it. 67 00:04:40,860 --> 00:04:42,690 ‫So that's what we try to think here.