WEBVTT 1 00:00:02.580 --> 00:00:21.150 William Cheng: Okay, this is the second part of the lecture. So now we're going to look at the directory implementation in the fast file system and also see how to speed up, you know, the data directories. Okay. And also we're going to briefly look at namespace management. 2 00:00:22.380 --> 00:00:29.490 William Cheng: All right, so some of the desire property of directories, I think, you know, you've seen the code in the RAM file system. 3 00:00:30.240 --> 00:00:39.720 William Cheng: The directory structure is very, you know, very simple. So the system file system you have the header file, you can look at it this way it looks. I again, they're very similar 4 00:00:40.530 --> 00:00:52.140 William Cheng: So what we would like a directory is to have no restriction on names right so in the system file, file system and also in the room file system directory file has these 5 00:00:52.800 --> 00:01:01.440 William Cheng: Fixed size records. Each record is 32 bites long right there's four bytes of I know number followed by 20 bytes of 28 bytes of component name. 6 00:01:01.890 --> 00:01:09.390 William Cheng: The last character has to be zero. So the component in can only be 27 characters long. Some people really like the component name to be as long as possible. 7 00:01:09.810 --> 00:01:16.680 William Cheng: Okay, so, so it will be nice if there's any no restrictions on names. So the question is that, you know, what is the right size. 8 00:01:17.100 --> 00:01:22.590 William Cheng: You know, maybe it's not a good idea to have them all have the same size. So you want a sort of a variable size data structure. 9 00:01:23.010 --> 00:01:29.250 William Cheng: So in that case, how, how, how does it actually work. Okay, so we're going to sort of talk about that and also the directories are pretty slow. 10 00:01:29.580 --> 00:01:41.760 William Cheng: Because, will you. Will you try to form a look up operation that directory file is a bunch of directory entry. So you're performing a linear search, right. So, linear sure if there's 1000 items over here the linear search will be really slow. 11 00:01:42.450 --> 00:01:50.490 William Cheng: So if you look at the directory on Linux. There's a directory called slash users slash Ben. Right. So he said that directory there. It's all your executable file. 12 00:01:50.850 --> 00:01:56.280 William Cheng: If you try to do an ls in this directory Linux actually going to ask you, are you sure because there are too many files in them. 13 00:01:56.790 --> 00:02:07.680 William Cheng: Okay, so. So in this case, every time we try to run a program. What do you will do is that it will go to this directory, try to look for the name of the program. So if there's 1000 or more than your 2000 entries in them. 14 00:02:08.040 --> 00:02:13.920 William Cheng: So every time. What it will do is that it will go through these directory entry and try to look it up. And if the file is the program is not there. 15 00:02:14.370 --> 00:02:18.300 William Cheng: For example, in warm up. One is a long one. The reason we don't run warm up why 16 00:02:18.900 --> 00:02:26.910 William Cheng: Warm up right one over here. We don't run the program like this is because we don't want to search for warm up one slide. You're just like baby because we know that it's not there. 17 00:02:27.810 --> 00:02:31.170 William Cheng: Okay, so, so we wasting our time, right. So that's why we always run with us. 18 00:02:31.470 --> 00:02:37.830 William Cheng: Warm up one. So this way, doesn't have to search. So if you have to search and the directory is really, really big than a performance is going to be really bad. 19 00:02:38.190 --> 00:02:41.850 William Cheng: Okay, so we also going to look at a solution to try to make this faster. 20 00:02:42.210 --> 00:02:51.030 William Cheng: And also, you know, we need to be space efficient right because, you know, there's always a space time trade off. If you want to make your data structure to be super efficient that. What about space. 21 00:02:51.450 --> 00:02:58.500 William Cheng: Okay, you might have to use all the sort of the large space for the data structure. So, in that case, even though you might be able to improve the performance 22 00:02:59.010 --> 00:03:10.410 William Cheng: But this space that you took up the space if sitting on this. Well, then you have to go to the desk and we all these data structures in from the desk that will also slow you down because there's kind of a tricky sort of trade off between, you know, 23 00:03:11.940 --> 00:03:17.790 William Cheng: Sort of space and time when you try to implement a file system. Yeah. So we're going to sort of see what people have done. 24 00:03:18.930 --> 00:03:28.830 William Cheng: Alright, so, so, again, a reminder, or the system of our system directly looks like the ramp our system directory every records 32 by four bytes for the I know numbers 28 bytes. 25 00:03:29.220 --> 00:03:39.090 William Cheng: For the component name right over here. When you have component name like Dada, dada. I mean, there are a complete waste of space, right, because you're going to end up using 28 bytes to store a to buy or three bite. 26 00:03:39.360 --> 00:03:49.710 William Cheng: You know component name. Okay, so, so, you know, we're we're wasting space already. Is there any way to save space. And is there any way to have really long component name. So that's the, that's what trying to achieve. 27 00:03:51.390 --> 00:03:54.660 William Cheng: All right. So in the first loss of them are they tried it, they they improve on this. 28 00:03:55.050 --> 00:04:04.560 William Cheng: They make it so that the component name can be as long as you want. Okay. I mean, I mean what is as long as you want. I mean, you cannot have a component that's four gigabytes. So that would be ridiculous. 29 00:04:04.950 --> 00:04:14.400 William Cheng: So still there's going to be a limit. But the limit is going to be really, really big and also they don't allocate a fixed size record. So this way you know some of the components will be small Symposium, a company that will be long. 30 00:04:14.820 --> 00:04:25.920 William Cheng: So, India, you want to be able to save your space using this data structure that. So the way the fast losses and there was that every directory entry. Now it's a variable size record, right. How do you know 31 00:04:26.370 --> 00:04:32.070 William Cheng: So, so in that case how do you figure out how big you know how, how big is every director entry. 32 00:04:32.910 --> 00:04:37.860 William Cheng: Yeah. So in that case, in order for you to figure out directory entry every direct we entered. Now the data structure. 33 00:04:38.010 --> 00:04:43.110 William Cheng: The beginning part will tell you how big the rest of the data structure is right. So the beginning part. We're going to call the header. 34 00:04:43.290 --> 00:04:51.930 William Cheng: So every directory Angie has a header, the headers always fixed size, right. So in this example over here the header is always the headers always eight bytes long 35 00:04:52.260 --> 00:04:57.420 William Cheng: Yeah, the first four by is going to be the I know number. So that's the one that you need to perform a look up. Yeah. What number is 36 00:04:57.900 --> 00:05:04.080 William Cheng: The rest of it. It tells you the first number over here. It's a two by number, it tells you how big this data structure is 37 00:05:04.500 --> 00:05:09.120 William Cheng: Okay, so that means that the remaining part of that data structure is the size of the Danish or minus eight bytes. 38 00:05:09.690 --> 00:05:20.520 William Cheng: Okay, so therefore you know exactly, you know how much data structure is there. And the next one over here to tell you what the string length is ok so the requirement for the festival system is that this number has to always be a multiple or four 39 00:05:21.210 --> 00:05:30.030 William Cheng: Okay, so therefore, in this case, you know, if you don't you have a stream that's not exactly eight bytes long, you need to remember how long this is so the next one over here tell you the name, the length of the name. 40 00:05:30.510 --> 00:05:37.230 William Cheng: So even if a component name is Unix right in this case you need five characters to store right Unix followed by backside zero 41 00:05:37.500 --> 00:05:40.950 William Cheng: So in this case, the string length or units equal to four. So their store right here. 42 00:05:41.130 --> 00:05:49.350 William Cheng: And then the entire record over here. Well, if you want to store five bites and you have to be a multiple of four. So, therefore, you're gonna end up using a bias. So it's going to be a bite of 43 00:05:49.590 --> 00:05:56.550 William Cheng: The, the rest of the data structure and eight bytes header. Right. So therefore, the entire data show to 16 bytes. So this one tells you how big that record is 44 00:05:56.940 --> 00:06:01.680 William Cheng: OK, so this way. Some of the component and can be long. Some of them come home component and can be sure 45 00:06:02.040 --> 00:06:13.020 William Cheng: So the next one over here. I know number equal to for the total size of the records equal to four and the string length equal to three. So you need four bytes. Right. So there's four bytes over here, a batch header. So the entire records 12 46 00:06:13.710 --> 00:06:24.030 William Cheng: Okay. And also there's another another thing that you need to do is that you know that you know this is a directory file. So how long have this, you know, how long is this particular file or you can find out you can find that information out from the I note. 47 00:06:24.720 --> 00:06:32.130 William Cheng: That they also allow the status or to have holes in them. So what they did over here is that the last entry over here is going to be special. So, so, you know, you 48 00:06:32.520 --> 00:06:44.010 William Cheng: have reached the end. Okay, so typically from the string. The string length over here, you can actually figure out what is the size of the record over here, so they don't match, that means that this is going to be the last one, and the space over here include all the 49 00:06:45.480 --> 00:06:54.420 William Cheng: All the free space in the remaining part of the directory file. Okay, so this way, it makes it easy for you to actually a pennant items over here at the end of this particular file. Yeah. 50 00:06:55.620 --> 00:07:04.020 William Cheng: All right. Um, so in this example over here I since this number is three. This you know the the the size of the data structure should be 12 since this one is is not able to 51 00:07:05.490 --> 00:07:13.500 William Cheng: Includes you know all the other free space. Okay, so this is the entire directory file. So again, that directory file is the content as so 52 00:07:13.890 --> 00:07:23.160 William Cheng: This is the content of the directory file. Okay, so the content of a file is, you know, I guess what JPG file is going to be an image for impact was going to be an image. So it's going to be the video. 53 00:07:23.700 --> 00:07:29.820 William Cheng: For a directory file is going to be these directory entries right except this directory entries. Little weird because there are different size. 54 00:07:30.000 --> 00:07:34.800 William Cheng: OK. So again, this is the content of a directory right that directory is also an I know 55 00:07:35.010 --> 00:07:41.910 William Cheng: That I know also has this map all that they you know that data structure and that this map point to the content of the directory file. Okay, so this directory 56 00:07:42.180 --> 00:07:48.690 William Cheng: You can be as long as you want, can be four gigabyte. You have a really, really big directory. Okay, so when you to perform a search operation. 57 00:07:48.900 --> 00:08:00.240 William Cheng: We, what do we have to do right we read the header and then we know the how big the rest of the record is right. So. So this way we can do a string compare if they're not the same. We can go to the next record and go to the next record networker 58 00:08:01.050 --> 00:08:07.470 William Cheng: Okay, so this way, even though every records of different size. Are we be able to starting from the beginning traverse all the way to do it. Yeah. 59 00:08:08.370 --> 00:08:15.480 William Cheng: Alright, so the data is over here or unsorted. So, therefore, you know, sort of directly. I know can look like this, right, the director. I know is the one that has 60 00:08:15.720 --> 00:08:24.000 William Cheng: This map in at the end over here at the end over here. The 13 pointer. The first 10 point directly to this page is over here. So each one of them. 61 00:08:24.300 --> 00:08:34.020 William Cheng: As I mentioned before, this is like one kilobytes. You know, one kilobytes per this block. So it's gonna be some of them. If you concatenate all these this blocks together, you get this 62 00:08:34.590 --> 00:08:42.060 William Cheng: OK. So again, this is so yeah, the way you sort of think about a file, it's a stream of bytes industry my bicep divided into this data structure. 63 00:08:42.240 --> 00:08:54.030 William Cheng: Okay and this data structure is a contract is a contiguous bytes. So here's the first one kilobytes, here's the next one kilobyte so it is possible one directory entry can actually go go across from one day to stretch it to the next one. 64 00:08:54.750 --> 00:09:04.290 William Cheng: Okay, so again it's really up to the that's the fastest is the implementation, they can decide how this exactly how to implement this data structure. Yeah. So in this case, every this block over here, they don't 65 00:09:04.980 --> 00:09:14.160 William Cheng: You know, the, the directory entry is not a fixed size anymore. So therefore, the number of directory entry, you can have per block over here it says on the order of 100 to 200 66 00:09:14.400 --> 00:09:22.980 William Cheng: Again, it depends on the user some user like to create really really long files in that case, you know, the record will be be some people I decrease your file. So in that case, the you know the 67 00:09:23.340 --> 00:09:28.410 William Cheng: The, the director entry will be small. Right. So again, this is hard to predict exactly how big it is this. Yeah. 68 00:09:29.220 --> 00:09:36.480 William Cheng: Alright, so this is what the fastball system look like in order for you to perform a look up, you need to stop on the beginning over here. You have to keep going down over here. So, 69 00:09:36.780 --> 00:09:42.210 William Cheng: So, so if you have a really, really large directory like slash users slash Ben then in order for you to 70 00:09:42.630 --> 00:09:47.580 William Cheng: To to to reversals and harless, you have to keep going to the dentist, because every one of this is that this block. 71 00:09:48.060 --> 00:09:55.200 William Cheng: Right, so therefore you need to go to the fastest and get the data from the data into memory and they can scan it when you scan to the. Yeah, you gotta read the next this blog and 72 00:09:55.530 --> 00:10:01.530 William Cheng: This blog and I'll continue to like that. Right. So this case your directory performance can be really, really, really, really poor. 73 00:10:01.890 --> 00:10:14.790 William Cheng: Because in the end, the way to have good performance inside. Inside of our system is to go to the disk as few times as possible right every time you see it this block, you have to go to the desk. Well, that will actually kill the performance of your file system. Yeah. 74 00:10:16.620 --> 00:10:26.670 William Cheng: All right, so, so this data structure over here, right, in order for you to search for something. It's an order and operation where n is the number of directory entries. Okay, so that's really, really bad, right. 75 00:10:27.240 --> 00:10:37.920 William Cheng: So again, it's a typical computer science, you know, sort of scaling problem. You know, if you have an order and problem. How do you solve it. Well, either you build a tree. So you have Otter login or you build a hash table we have order one. 76 00:10:38.970 --> 00:10:46.200 William Cheng: Okay, so. So again, we're going to see both solutions. One is to build a tree will use a special kind of tree called the p plus treat 77 00:10:46.650 --> 00:10:53.190 William Cheng: Those of you have taken a database class, you're probably familiar with B plus tree. So again, I'm going to sort of give a quick introduction to show you what 78 00:10:53.460 --> 00:11:00.750 William Cheng: You know what it looks like. And then we're going to move on. And the second one over here. So, of course, use a hash table, we use a hash table is going to be order one. 79 00:11:01.290 --> 00:11:06.960 William Cheng: Okay, so first one is going to see the highest level implementation and then we're going to look at a tree implementation. Yeah. 80 00:11:09.060 --> 00:11:17.970 William Cheng: Alright, so for this. So again, the goal for this data structure over here is to perform the lookup operation right so so you don't look up in Colonel to right 81 00:11:18.270 --> 00:11:28.410 William Cheng: Guys have given a component name you want to find the I know number right that's the purpose of a directory far right. You can use any data structure that you want as long as you can find that you'll be fine. Okay. 82 00:11:29.190 --> 00:11:37.110 William Cheng: All right, so, so one of the solution overhears use the hash table. So remember what a hash table does, right. So this is a typical, you know, sort of a software a hash table. 83 00:11:37.530 --> 00:11:39.930 William Cheng: That you probably have learned in a data structure class. 84 00:11:40.320 --> 00:11:47.940 William Cheng: So what you do is that up by your data structure into buckets. Right. You take your key you feed it to a hash function and the hospital. She will give you a bucket number 85 00:11:48.150 --> 00:11:56.970 William Cheng: Inside the bucket. There's a link list implementation. Right. The liberalism is called a collision resolution chain or conflict resolution chain, right, because these are all the 86 00:11:57.300 --> 00:12:02.790 William Cheng: Things all the keys to hash to the same bucket right when you have keys to the same punk. Okay. It's called a collision. 87 00:12:03.120 --> 00:12:11.790 William Cheng: Right. Or it's called a conflict. So we have a collision resolution chain or conflict resolution chain. So what you need to do is I need to walk down that list of conflict resolution channel collision resolution chain. 88 00:12:11.970 --> 00:12:18.870 William Cheng: And try to look for that key. If you can find it will then then you got the ID number that you want. If you cannot find it, you will say that I cannot find the item number 89 00:12:19.890 --> 00:12:29.040 William Cheng: Okay, so, so as long as you can get hash to a bucket you read that bucket. So, so in the hash table implementation over here, what we can do is that every this block correspond to one bucket. 90 00:12:30.210 --> 00:12:37.830 William Cheng: OK, so the guy that when you said a look up something you hash it that will give you one of these bucket. You go to the discovery one data blog over here and then 91 00:12:38.070 --> 00:12:47.310 William Cheng: In that case, you know, the key that you're looking for, has to be inside this block you will no longer be another BBB inside another block, right, why wouldn't be inside another block. 92 00:12:47.730 --> 00:12:50.850 William Cheng: Well, because inside another block. It's a different. It's a different bucket. 93 00:12:51.420 --> 00:13:01.170 William Cheng: Okay, so why don't you get hash, you know, which bucket. You're going to and that bucket correspond to one this block. So you only have to go to the disk once and then you can find out whether you have that data or not. 94 00:13:01.710 --> 00:13:10.800 William Cheng: Okay, so this is why it's order one performance is really, really great. Okay. You want to have to go to this one. This one's no matter. You know how big your English original link that says 95 00:13:11.310 --> 00:13:20.040 William Cheng: Okay, so what is it was. Oh, so what could be the downside, right. This is the typical problem with a hash table implementation every time, will you, you know what, we try to deal with a hash. 96 00:13:20.430 --> 00:13:25.110 William Cheng: Hash table implementation is what if this particular you know this blog over here is for 97 00:13:26.070 --> 00:13:38.220 William Cheng: Now, why would it this blog before, right, because what happened is that, you know, for directory. We need to keep adding entries into the directory we if we keep adding entry into this bucket at some point the bucket is going to be full. Okay, so what happened when the bucket is full. 98 00:13:39.390 --> 00:13:45.750 William Cheng: Well, I mean, you know, we can't really get a bigger block, right, because that's really not allowed every block stores a conflict with collision. 99 00:13:46.320 --> 00:13:54.090 William Cheng: Collision resolution chain. So you can really get a bigger block. So the typical solution for the hash function is that we need to get a different hash function. 100 00:13:54.600 --> 00:14:04.560 William Cheng: Okay, so in this example over here we have a hash function that has two three bucket when one of the bucket over here is become full. We need to get a new hash function and this hash function will hash to for bucket. 101 00:14:04.800 --> 00:14:17.640 William Cheng: And what's even worse is that we need to take all the keys that are stored inside these three buckets rehash them using a new hash function. And now, if you have a good hash function. What it will do is that what you rehash them, they will be evenly distributed among all these four buckets. 102 00:14:18.660 --> 00:14:26.310 William Cheng: Okay, so, so, so, so if you have a good hash function. Every time you need to edit entry this empty the directory and we'll go to a random hash bucket. 103 00:14:26.490 --> 00:14:33.300 William Cheng: So therefore, the, you know, it's going to take you a while before one of the highest bucket over here is going to become for when that hash function big warehouse bucket become for 104 00:14:33.570 --> 00:14:43.230 William Cheng: All the other hash bucket. They're also they're also they're almost completely fall. So in this case, again, you need to go go go go to the next hash function and you need to create more more bucket. 105 00:14:43.980 --> 00:14:50.760 William Cheng: Okay, so in that case this operation is going to be really slow, right, because every time when you run out of space is that one bucket. You need to rehash everything 106 00:14:52.110 --> 00:15:04.680 William Cheng: Okay, so, so, so the usual problem with other the hashtag hash table is that you know there's collision. That's why you use, you know, use a key and use a conflict collision resolution chain. But then eventually is going to run out of space. So we need a solution for that. Yeah. 107 00:15:06.120 --> 00:15:13.140 William Cheng: Alright, so the solution. I'm going to look at as a specialized solution over here is no is extensible hashing. It's a specialized hash function. 108 00:15:13.410 --> 00:15:16.440 William Cheng: Okay, so let's talk about this hash browns, it's a it's a family of hash function. 109 00:15:16.710 --> 00:15:23.010 William Cheng: And their related. We're going to call these high functioning hmm 01 or two or three dot all the, all the way to whatever he is 110 00:15:23.220 --> 00:15:32.370 William Cheng: Okay, every one of these function hash so hmm I hashes. The names to to to the ice buckets. Okay, so H zero has to one bucket at one or 111 00:15:32.670 --> 00:15:39.510 William Cheng: Two buckets as to how to for bucket age of three, a hash to a bucket and 16 bucket. So, so basically we're doing pair of shoes. 112 00:15:40.410 --> 00:15:48.540 William Cheng: Or assets. That's one special, special thing about these hash function is that the age with a subscriber I hash to to to the ice buckets. Okay. 113 00:15:49.110 --> 00:15:58.140 William Cheng: The other reason that this is called the extensible hashing over here is that for any name X rays, X could be a string, whereas over here could be you know food.ca or something like that. Right. 114 00:15:58.350 --> 00:16:06.930 William Cheng: So, therefore, you know, for any string of, you know, x over here. The lower order I bits of H I have x, right. So over here, don't say that we have this age to have x 115 00:16:07.590 --> 00:16:17.700 William Cheng: When you hash it with age to have X, how many choices do you have, are you going to hash it into a two bit number. There are four choices. So therefore, the possibility is going to be 000110 and one one. 116 00:16:18.780 --> 00:16:34.830 William Cheng: Okay, so let's say that we actually were has food RC using it. So that's it. We'll get we'll get we'll get one, zero then this one tells you that the lowest order to better base to buy are the same in H3 H3 of x there. So therefore H3 of food RC. 117 00:16:36.750 --> 00:16:46.080 William Cheng: Okay, as three or four Darcy over here it says the lowest two bids over here has to be one zero. I said last week is over here, it'll be one zero. That means that the Thurber can either be zero or one. 118 00:16:46.560 --> 00:16:53.220 William Cheng: Okay, so if this is zero is gonna be like this if this one's gonna be like this. So, therefore, if you know that H2 or food RC is equal to two. 119 00:16:53.580 --> 00:16:58.500 William Cheng: Then you know the H three or four Darcy can be either two or six and then nothing else. 120 00:16:59.370 --> 00:17:09.660 William Cheng: Alright, so, so, so he is an extension of so he have i plus one. It's an extension of a try, because the lowest order iPads are exactly the same. And they just get one more bed. 121 00:17:10.080 --> 00:17:17.430 William Cheng: Okay and this one more big can be either one or zero. Okay, so there are we're hash function like that, it's okay. You can also construct your own to have this property. 122 00:17:17.880 --> 00:17:30.630 William Cheng: Yeah. Alright, so, so, so we're going to take a look at example to see how this one actually works and how does it actually speed things up. Yeah, also to use extensible hashing. We also need one level of indirection because we love interaction. 123 00:17:31.890 --> 00:17:37.170 William Cheng: You know, a lot of times when we're stuck with certain kind of problem we use one level indirection. And he gave us a lot of flexibility. 124 00:17:37.560 --> 00:17:48.060 William Cheng: So when we're using extensible hashing. You know, we also going to use one this block to do it to to to to handle interaction. Okay, so let's take a look at the example to see what is look like 125 00:17:51.510 --> 00:18:02.970 William Cheng: All right, so instead of going to the this blog for the collision resolution chain right away. We're going to use an indirect blog and they were indirect blog tells it tells us. Tell us, tell us which this block to go 126 00:18:03.630 --> 00:18:11.010 William Cheng: Okay. All right. So, so we, here we have a ship to and then on the right hand side over here on this block right so he have to hash you to four bucket. 127 00:18:11.220 --> 00:18:22.410 William Cheng: Here's bucket 0001 bucket 10110 over here. Again, this is the indirect block it will point to the data bra that store all the keys to hash to the same bucket. 128 00:18:22.860 --> 00:18:30.270 William Cheng: OK, so the idea over here is that all these things over here. They all have the bucket zero. So that means that Ralph has to bucket zero Lily has to be 129 00:18:30.840 --> 00:18:39.930 William Cheng: above zero. And then over here, they store the I know, so, so, so, so, so, so that I know inside that that directory entry. 130 00:18:40.290 --> 00:18:48.030 William Cheng: Okay, so, so you may say, in this case, every one of our this block store and most to directly entry right because I don't want to draw 100 entries or 200 entries 131 00:18:48.450 --> 00:18:54.480 William Cheng: Or they'll be too much work. So in this again so silly example every this block and store only up to two directory entries 132 00:18:55.140 --> 00:19:00.660 William Cheng: That. So in this case, Ralph has to zero and Lily has zero. They all have zero using age of two 133 00:19:00.990 --> 00:19:13.230 William Cheng: Okay, Joe. When you try to hash it with HTTP or hash 201 Belinda, and George if you have some with age of today will become one zero and Harry and Betty when you have them into using age of two, you're going to get the number three. 134 00:19:13.710 --> 00:19:23.370 William Cheng: Okay, so again, when you try to look up, you know, we're going to look up, George, you will take GA or hashtag ways. You have to, and you know that you're gonna get bucket equal to two, you come down to over here. 135 00:19:23.760 --> 00:19:37.410 William Cheng: To this block this, this book is sitting on the desk. You read the entire this book into memory and then you scan only this this blog and you try to look for. George, do you find George than Georgia says here. Otherwise, you know that George's not anywhere inside your directory. I know. 136 00:19:38.760 --> 00:19:50.070 William Cheng: OK. So, again, in this case, you actually, you have to go to get to this blog, you need to get that the indirect this law and also you get the direct the final data blog that contain all the keys. Okay. 137 00:19:51.060 --> 00:19:59.820 William Cheng: All right, so, so, so this is the using the, the other this particular hash function. So, again, not much different ball we had before, except that we add indirect law. Yeah. 138 00:20:00.300 --> 00:20:04.920 William Cheng: Alright, so let's try to insert a key into it, right. So we're here, we're going to insert Fritz 139 00:20:05.340 --> 00:20:12.150 William Cheng: So let's say he to have friends is also equal to two, right. So, okay, H2O, you go to to to is one zero. We hear you follow this pointer over here. 140 00:20:12.330 --> 00:20:16.590 William Cheng: You to perform a look up operation right so if you try to insert something into the directory 141 00:20:16.830 --> 00:20:26.160 William Cheng: I mean you implement this in Colonel to write what you need to do is I need to perform a look up first. Make sure that the key is not inside this data structure if it seems that is the researcher that you have to return an error. 142 00:20:26.910 --> 00:20:37.020 William Cheng: Okay, so we try to insert threats we need to look out for. It's over here. So again we hash the two and we go to this data blog we read it on the desk and then we go down this list linearly 143 00:20:37.500 --> 00:20:45.540 William Cheng: You know, Belinda is not equal to fret George is not equal to for us. That was a Fritz is not in here, grey, we should be able to insert this into into this this this block. 144 00:20:45.900 --> 00:20:55.260 William Cheng: Yeah, but this this block number to over here is for. Okay, so what we need to do is that we need to rehash all the all the keys over here using age of three. 145 00:20:56.490 --> 00:21:01.080 William Cheng: Okay. All right, so, so, so how do we actually rehashing using age of three. Okay, so, so 146 00:21:01.560 --> 00:21:06.840 William Cheng: The solution over here using extensible hash is actually really simple. I'm going to change this function to age of three. 147 00:21:07.320 --> 00:21:09.090 William Cheng: Okay, I'm going to take the indirect 148 00:21:09.480 --> 00:21:21.270 William Cheng: Bucket. I'm going to make a duplicate of it at the bottom. Over here, they typically will be here like this. Right. And I'm going to a meme copy from the top to the bottom. Over here when I finished doing that, I'm going to claim that I have finished rehashing everything 149 00:21:23.220 --> 00:21:29.700 William Cheng: Okay, so that's really simple. Right. So in this case, I don't have to touch any of this book over here. Okay. All I have to do is to take the indirect this block. 150 00:21:29.880 --> 00:21:40.740 William Cheng: Make it twice as big, copy the top part into the bottom part over here. So when you copy pointer. They point to the same place. So, therefore, this will point here. The second one will point here that the whole point here is the fourth all right here. 151 00:21:40.950 --> 00:21:51.360 William Cheng: Right. So when I'm done the data structure look like this. Okay, so how can I claim that, you know, I just finished rehashing everything right. If you're has Ralph using age of three, what should you get 152 00:21:51.870 --> 00:22:03.210 William Cheng: So remember when you hash Ralph using a job to you get the value of zero, right, you get a value of zero. So, therefore, when you hash Ralph using age of three. The only two possibilities. Either you get 000 or 100 153 00:22:04.170 --> 00:22:10.590 William Cheng: Okay, if it turns out rough, you know, Ralph. If you have to H3 is go to zero. Can you find route Inbox Zero, right. 154 00:22:10.830 --> 00:22:21.390 William Cheng: Zero is right here. So get this will be 01234567 if you go to bucket zero, you will find Ralph. Ralph sitting on the right place. Right. What if it turns out route hashtag for 155 00:22:21.690 --> 00:22:27.840 William Cheng: Okay, so forth, right here, right, if you follow this pointer. You can also find Ralph. So now that you know Ralph is in the right place. 156 00:22:28.200 --> 00:22:33.810 William Cheng: Okay, if you go to Lily. Lily. Use the hashtag to and now you can leak and only has two two or four so 157 00:22:34.230 --> 00:22:39.090 William Cheng: Lydia, use the hash to zero. Now they can only has two zero or four, so again it's sitting on the right place. 158 00:22:39.330 --> 00:22:47.910 William Cheng: What about Joe. Joe used to hash to one right that's that's 01 over here. So now if you add another bit you can only have two one or one, zero why that's equal to five. 159 00:22:48.060 --> 00:22:54.570 William Cheng: So it is equal to one then can find it right here. If it's equal to five, you're gonna find it right here. So, therefore, Joe is sitting at the right place as well. 160 00:22:55.320 --> 00:23:07.080 William Cheng: Okay, Belinda, and George they use the hash the one zero right so now use age of three going to get an extra bit over here so we can be either two or six. If it's too. You find it this way. The 61 of the unified it this way. 161 00:23:07.470 --> 00:23:17.640 William Cheng: Similarly, Harry and Betty. They use the hash two three right so now if you add another bit, it can be equal to three, or it can be equal to seven. If it's equal to three, you find it this way. If it's equal to 75 this way. 162 00:23:18.600 --> 00:23:28.590 William Cheng: Okay, so by using one level in directions over here where you try to rehash everything using h3. As it turns out, is really, really easy. All you have to do is to access this this block. 163 00:23:29.190 --> 00:23:35.310 William Cheng: Okay, you just need to make the table. The indirect block over your choices, big and then you copy from the top to the bottom and then you're done. 164 00:23:36.690 --> 00:23:44.850 William Cheng: Okay, so it's really super easy to rehash everything. So what's going on over here is that this particular your this blog over here is being shared by 165 00:23:45.210 --> 00:23:53.550 William Cheng: By backpacking number zero bucket number four is over here. Now over here the bucket number over here is change to bucket number for zero comma for so they're sharing the same bucket. 166 00:23:53.760 --> 00:24:00.990 William Cheng: This one is shared by one and five just want to share by two and six and this was shared by three and seven. Okay, so that's why this is done, you know, this is super fast. 167 00:24:01.860 --> 00:24:12.120 William Cheng: Okay, all right, but we haven't really done adding Fritz into the data structure over here. So we need to go back and do it right. So now we just finished rehashing everything. And now we need to go to the next step and try to 168 00:24:12.810 --> 00:24:24.180 William Cheng: Try to figure out where does the fridge really belong. So in this case we switched to age of three. Now it's just me over here, for it has to be equal to either one is a tour six. It cannot be, you know, a both value. 169 00:24:24.690 --> 00:24:32.400 William Cheng: You also cannot be other value. So it has to be two or six now. So in this case, we're going to assume that h h three or four, it's going to be able to say, I will go to the six pointer. 170 00:24:33.000 --> 00:24:44.310 William Cheng: Get 01234566 partners right here. This is six we follow the pointer over here, we found that this bucket is completely full and also this bucket is being shared by by by two different buckets two and six. 171 00:24:45.360 --> 00:24:50.850 William Cheng: Okay, so therefore we need to do is, I will need to create a to bucket. We need to split this bucket into two and six. 172 00:24:51.090 --> 00:25:00.900 William Cheng: Right, so it will not create a new bucket over here. We're going to call this one too. And this one says we're going to take all the data in the original bucket that's shared by two and six. We're going to rehash all those keys. 173 00:25:01.620 --> 00:25:09.900 William Cheng: Okay, so we're going to go to this this this bug over here right before we read it already. We know that there's no Fritz and inside of that. So now this this box is already memory. 174 00:25:10.200 --> 00:25:20.220 William Cheng: Because all we have to do. So take all the key rehash them using HTTPS, which was two and which one is six. If we have a good hash function 50% will go to two and 50 years old, got a sex. 175 00:25:21.180 --> 00:25:30.450 William Cheng: Okay, so we're going to end up with this situation over here. So let's say like this case Belinda stays in two and George go to 650 percent goes to 250 percent or six and now again. 176 00:25:30.720 --> 00:25:40.080 William Cheng: You know, age of three is equal to six. So now we're going to come to this this blog over here 50% of this is going to be empty. So therefore, we can easily insert it into the into the data structure. 177 00:25:40.440 --> 00:25:52.380 William Cheng: Okay, so therefore, when we're done over here will look like this. Right. We efforts into, you know, into this particular disbar so in this case to perform we hash everything and also insert Fritz, how many this block that we have to modify 178 00:25:53.760 --> 00:26:01.200 William Cheng: Okay so India will only have to modify three this blocks in the worst case, we have to modify this this block. We need to modify this this blog and this this box. 179 00:26:02.100 --> 00:26:08.850 William Cheng: Okay, so no matter how many, how many boxes were using in the worst case, we only have to modify three this blah. So, India, we're still order one. 180 00:26:09.930 --> 00:26:15.270 William Cheng: Okay, so therefore extensive what hashing is actually really good. Because in the end, it's still order one now. 181 00:26:16.050 --> 00:26:21.630 William Cheng: Alright, there's also show you the power of indirection without this indirect block. This will be very difficult to implement. 182 00:26:22.620 --> 00:26:30.510 William Cheng: Alright, so the guy using whatever in direction you're going to get a lot of flexibility. So in the end, you actually have very, very good performance are using this trick. Okay. 183 00:26:35.910 --> 00:26:39.750 William Cheng: Alright, the next thing that we're going to look at is to use tree data structure. 184 00:26:40.740 --> 00:26:47.730 William Cheng: We're not going to use a binary tree because binary tree is really, you know, so what's wrong binary tree right binary tree that the height will be really, really big. 185 00:26:48.210 --> 00:26:57.300 William Cheng: So if you need to go down. Many, many levels. Every node you you know you know every note on your binary tree you stored in this blogs and I perform really really poor right 186 00:26:58.200 --> 00:27:03.300 William Cheng: So there are different solutions are the one going to look at this borrow from the database community is known as a bee tree get 187 00:27:03.690 --> 00:27:09.480 William Cheng: A, b tree of order em has the following property. Okay. Every know has less than em children. 188 00:27:10.290 --> 00:27:16.620 William Cheng: Okay. So, m is an integer. Right. So over here. Every know has, you know, has has no children. So let me go to three. 189 00:27:16.860 --> 00:27:23.040 William Cheng: Right. So what does that. What does that look like right every know it has less than or equal to two, three children. So you're gonna have a know that has three children. 190 00:27:23.280 --> 00:27:31.410 William Cheng: Okay, and then you have another know here. How to children, maybe the other way over here has three and this one has three or something like that. Okay, so it doesn't look like a binary tree anymore. 191 00:27:32.130 --> 00:27:41.130 William Cheng: Okay, so typically this image, really, really big. It can be 50 can be 100 because the basic idea over here is that every node over here corresponding to one disbar 192 00:27:41.760 --> 00:27:50.100 William Cheng: Okay. So inside this block you can store a lot of information, right. Okay, so what's stored inside this note over here, right. So, so if you have three children. 193 00:27:50.520 --> 00:27:59.280 William Cheng: We don't know if you remember your binary tree right we insert a performer look up in a binary tree, you have to use one key. If it's less than or equal to the key you go live is bigger than the Q go right 194 00:27:59.730 --> 00:28:11.670 William Cheng: Yeah. So now if I have three children. How many kids do I need, what I need to keys right K one and K to over here, right. If it's less than or equal to one, I go left. If it's greater than one, but less than equal okay to go to the middle. If it's greater 195 00:28:12.480 --> 00:28:14.160 William Cheng: Greater than K two or we go to the right. 196 00:28:15.210 --> 00:28:22.260 William Cheng: Okay. So, therefore, you know, you know, for this one, this blah, you do store a bunch of this pointer. How many disappointed. We can actually store. 197 00:28:22.860 --> 00:28:32.850 William Cheng: Okay, so when we saw before. Why we have one kilobyte this block and we can still afford buys for every a pointer over here. So in this case, we actually store. You know, you know, easily over 100 198 00:28:33.870 --> 00:28:39.630 William Cheng: Right, we can easily. So, you know, over 100 pointer over here. So typically, the EM over here is a really big number. 199 00:28:40.680 --> 00:28:50.310 William Cheng: Okay, so if it's a really big number. You can you can imagine that will have one note over here has 100 children over here, right. So, in that case, the height of the binary. The height of the beach typically is going to be very, very small. 200 00:28:51.630 --> 00:28:56.520 William Cheng: Alright so this way. If you need to perform a search, you need to go all the way to the binary tree so 201 00:28:56.910 --> 00:29:05.280 William Cheng: You have to go all the way to the end of the end of the b tree, but the beach at the height of the beach is very, very small. So, therefore, the number of this blog, you need to access is very, very small. 202 00:29:06.150 --> 00:29:10.830 William Cheng: Okay, it's almost the same as order one because in this case the performance over here will be log 203 00:29:11.340 --> 00:29:23.790 William Cheng: Log of air and it's a number of keys that you have. So in this case, the base over here is not to because to is for binary file. This one is order and if this mo. Here is a number like 100 or then log base 100 domains going to be a tiny number 204 00:29:24.510 --> 00:29:27.330 William Cheng: Okay, so therefore using Petri you also can get very good performance. 205 00:29:28.050 --> 00:29:32.730 William Cheng: Then, as I said, let's go over the differential between we're going to see some example of what it looks like. Over here. 206 00:29:33.000 --> 00:29:44.100 William Cheng: So every now has less than or equal to n children right so the an example of your is equal to three, and also every know has greater than or equal to the ceiling of em over to children. Yeah. So em over to over here. 207 00:29:44.400 --> 00:29:51.120 William Cheng: M is equal to three, three divided by two is equal to 1.5 the seating function well rounded up to the next integer, right. So this one is going to be able to to 208 00:29:52.050 --> 00:30:01.860 William Cheng: Okay, so if me go to three over here in order three Petri okay every know will have either two or three children. Okay. The only exception are the root and the leafs 209 00:30:02.610 --> 00:30:09.060 William Cheng: Okay, because the leaf is the one actually pointed the, the actual data. So therefore, the lever, we can have only one can only one children. 210 00:30:09.450 --> 00:30:12.840 William Cheng: The route over here. It is possible. You have the case where you only have one root node. 211 00:30:13.080 --> 00:30:26.340 William Cheng: Well, in that case, there's no children. Why is it so again it's a special case. Okay. Otherwise, if you have a tree that has multiple level, then every know well we'll have, you know, at most three children, three children and has, you know, at least two children. 212 00:30:27.540 --> 00:30:36.900 William Cheng: Okay, the rude also have at least two children, unless it's also the leaf. Again, if the rule is also believe your data. So it only has one know again it's not very interesting. It's a special case. 213 00:30:37.620 --> 00:30:43.740 William Cheng: Now, here's one of the weird thing about the tree or the leaf appear at the same level and carry no keys. 214 00:30:44.370 --> 00:30:50.220 William Cheng: Okay, so, so, so, so typically a pitcher is drawing like this, right. He is drawing like a big triangle. 215 00:30:51.090 --> 00:30:57.450 William Cheng: Okay, why does it run like a big triangle, right, because all the leaf nodes over here appear the same level. So all the leaf over here is actually at the bottom right here. 216 00:30:57.720 --> 00:31:05.010 William Cheng: Okay. So over here, this, this is the leaf node over here that the leaf node over, he has no keys to all the keys over here are stored inside the beach right here. 217 00:31:05.340 --> 00:31:14.310 William Cheng: Yeah, so over here. So, okay, what is this is known as the bee tree Index. Index. Right. It's an index data structure that allow you to find something 218 00:31:14.790 --> 00:31:22.800 William Cheng: Okay, so therefore, when you're coming down this between the infrastructure, you're going to use a key and you try to go to decide what do you want to go left or right or they're 100 different ways to go. 219 00:31:23.100 --> 00:31:28.560 William Cheng: Guys, are you trying to sort of go go here. So in the middle part over here, there are these keys that are storing them to tell you to go left or right. 220 00:31:28.830 --> 00:31:38.310 William Cheng: Right. But when you reach the bottom over here at the bottom part we here just had the data and the data is what we saw before, right, the date the bottom over here is just this block that this block is store what what what what 221 00:31:38.520 --> 00:31:42.510 William Cheng: What a data, what data is for, you know, for, for, for a bunch of components. 222 00:31:42.960 --> 00:31:49.530 William Cheng: OK, so the this blog at the bottom over here. Again, the example that we saw is one kilobytes data when you just throw a bunch of 223 00:31:49.830 --> 00:31:55.500 William Cheng: You know that directory entries over here, again, that can be different size. So in the end over here. We're going to do a lot of entry for you. 224 00:31:56.100 --> 00:31:59.520 William Cheng: Guys, okay. The, the, the, the, the purpose of the b tree index. 225 00:31:59.700 --> 00:32:09.510 William Cheng: Is to get you to the rhino at the bottom. Once it gets to the right at the bottom. Over here you open it up and you look for inside if it's there. That means you found it. If it's not there. That means that it doesn't exist. 226 00:32:10.020 --> 00:32:15.300 William Cheng: Guys are just like before, in the hash table right, all you need to do is try to get to the bottom. Yeah. All right. 227 00:32:15.870 --> 00:32:22.110 William Cheng: When we talk about a B2B typically there are you know the the leaf nodes are admitted for joining. So you see the picture you're 228 00:32:22.470 --> 00:32:26.070 William Cheng: Like this, right. So again, the goal is to get to the bottom over here at the bottom is not draw 229 00:32:26.550 --> 00:32:35.310 William Cheng: Okay, another leave no with K children contain k minus one key right so if you have children over here while you need to have k minus one keys or you know which way to go. 230 00:32:35.820 --> 00:32:43.050 William Cheng: Okay, so again, I mentioned that before, right, for, for, you know, for three children are the two keys for two children, you had one key now. 231 00:32:43.860 --> 00:32:56.730 William Cheng: M is often lost to reduce the number of this accesses over here. So typically want to see a b tree. Sometimes they only have two levels where you're at the bottom right because over here, the number of children, you have is 100. So there are two levels is actually enough 232 00:32:57.750 --> 00:33:02.370 William Cheng: Okay, so a lot of times when you use the feature inside the house is there, it will only go to two levels. 233 00:33:02.730 --> 00:33:09.990 William Cheng: Even in the directory in slash slash user guide. If you use a b tree implementation, maybe there will be two level, maybe in the worst case, it'll be three level. 234 00:33:10.500 --> 00:33:19.500 William Cheng: Three level you guys just saw a lot of entries. So if this one has 100 children over here. Each one of them has 100 children that will be 10,000 entries 235 00:33:20.430 --> 00:33:26.250 William Cheng: Okay, so, so, so again in your services. In that case, you're going to end up with a lot of direct entry instead of directly far 236 00:33:27.030 --> 00:33:31.020 William Cheng: As typically two to two levels should be enough. But sometimes you need to go to three levels. 237 00:33:31.860 --> 00:33:40.170 William Cheng: Yeah. All right. So every node in the beach or a corresponding to one this blog right every one of these notes over here. So what you need to do is that in order for you to figure out 238 00:33:40.410 --> 00:33:46.770 William Cheng: You know what is M. You need to figure out what, how big is this block right that size of the this blog will tell you what is the order and 239 00:33:47.370 --> 00:33:55.440 William Cheng: Okay, and he typically try to cram as much stuff into A into a note over here, the internal know container so so so for p plus treat 240 00:33:55.920 --> 00:34:03.870 William Cheng: The internal know contain no data just keys again to the beach street index data structure is a look. It's a data structure that let you get to the bottom. 241 00:34:04.170 --> 00:34:13.950 William Cheng: Okay, there are some other version of the trees. Okay. Be tree coming from the database community if you have taken a database class, you know that they're there because zillion different version of the tree. 242 00:34:14.550 --> 00:34:26.910 William Cheng: Okay, some big tree then into internal notes has data storing them some between only uses the index Archer so so so this class we talked about something called a b plus tree where the internal notes has no data only has keys. 243 00:34:27.540 --> 00:34:37.440 William Cheng: Yeah, they're also one one feature over here is to say that the leaf nodes are linked together to ease sort of sequential reversal. Yeah, you probably heard of a 244 00:34:38.730 --> 00:34:46.980 William Cheng: binary, binary tree there. Why do we tree, you know, something called a binary surgery. So, so the the order over here is actually a sort it 245 00:34:48.030 --> 00:34:53.550 William Cheng: Okay. Oh, yeah. So in order for you to to do a sort of retrieval for your binary. Sure. Sure. Yeah. What do you do 246 00:34:53.910 --> 00:35:03.150 William Cheng: Right, I guess there's, you know, pre order that's in order the post order traverse. Oh, if you use it in order to reversal of your binary surgery, you will visit all the leaf node over here in a sort of sequence. 247 00:35:04.230 --> 00:35:09.450 William Cheng: Okay. So, therefore, you know, so sometimes you want things to be sorted right if you try to scan a particular directory 248 00:35:09.690 --> 00:35:21.600 William Cheng: Or you try to you know to ls right for directory file. So in this case you want to print out every entry in the direct without over here. So this guy's you don't want to go up and down. You know, so, so again of us are picture look like this. Sorry. 249 00:35:22.560 --> 00:35:27.180 William Cheng: Okay, if you have an index or look like this. If you want to list your directory structure. 250 00:35:27.840 --> 00:35:34.470 William Cheng: by by by sorting these keys over here. You don't want to go up and down the beach, we have here I because that will record too many operations. 251 00:35:34.980 --> 00:35:40.740 William Cheng: Okay, so what do you will do is it, why should find the smallest element over here. And then if the note over here at the bottom. 252 00:35:40.980 --> 00:35:46.950 William Cheng: They're all linked together in a single link list right so every one of them has a link as a next pointer over here on to the next one over here. 253 00:35:47.280 --> 00:35:54.840 William Cheng: Why, in this, in this case, when you try to list it directly contact. All you do is to go to the the leftmost one over here because that will be the one with the smallest key. 254 00:35:55.110 --> 00:36:00.540 William Cheng: Once you find out why. You just, you just follow the pointer at the bottom over here and then you can print out the entire directory content. 255 00:36:01.980 --> 00:36:04.110 William Cheng: Okay, so this will be this will be super fast. 256 00:36:04.350 --> 00:36:14.880 William Cheng: Okay. So in this case, if there are any notes at the bottom. Over here, the number of this blog you have access is that you have to find the first one over here using log in and then use log in and then followed by an operation over here. 257 00:36:15.870 --> 00:36:28.020 William Cheng: Okay, if you don't do it this way. If you need to go up and down the this particular feature is over here. How many internal notes over here are in the are inserted between what the number internal notes over here is going to be n minus one. 258 00:36:29.340 --> 00:36:36.270 William Cheng: OK. So again, you know, if you have a full binary tree. It's going to be a minus, whereas over here the you know the number of nodes over here is going to be on the order of an 259 00:36:36.870 --> 00:36:44.490 William Cheng: OK. So in this case you need to go up and down the status Joshua order event. And then you have to go through all these data structure. So you got to be tight. A. Are you going to be twice as slow 260 00:36:45.900 --> 00:36:53.430 William Cheng: Or is it again, the number of how you go to the this matter, right. So, therefore, using a peep plus street data structure. If you want the list that directory content sorta 261 00:36:53.670 --> 00:37:02.070 William Cheng: All you have to do is to go to find the first one and then you can actually go horizontally across the bottom of the tree. And this way you could actually list all the directory content that 262 00:37:03.030 --> 00:37:10.680 William Cheng: All right. There are a lot of B2B variation in various application areas over here. So again, if you're interested in that. You take a database class. 263 00:37:10.890 --> 00:37:16.980 William Cheng: This is all we're going to talk about, you'd have the basis that one kind of bees bee tree, which is the p plus tree. Okay. And without going into too much detail. 264 00:37:17.370 --> 00:37:27.060 William Cheng: Alright, so we're going to illustrate the basic idea using an example, the real B plus tree algorithm is very complicated. So we're not going to go into the detail of the algorithm. Okay. 265 00:37:29.190 --> 00:37:39.660 William Cheng: All right, so here's an example. A B plus three with order three right get me close to three, so three go to em over here every internal note has two or three children right so this this know has three children. 266 00:37:39.900 --> 00:37:45.120 William Cheng: Three, three and two over here. If a nose has greater than three children, that's not allowed. 267 00:37:45.630 --> 00:37:51.990 William Cheng: Okay, so therefore you should have asked up to a note that will make it into four make it, make it into pointing to for children. What do you have to do. 268 00:37:52.200 --> 00:37:59.100 William Cheng: You have to take that. No, you need to split it in half. When you split it in half. Now it will point to two children each there'll be okay. Yeah. 269 00:37:59.760 --> 00:38:02.340 William Cheng: What if you're going to end up with a know that has less than two children. 270 00:38:02.910 --> 00:38:13.080 William Cheng: Okay, so. So you start with two children. If you're going to delete one of the pointer over here and now they want to point to one thing that's not allowed. So therefore, in this case, you need to merge it with this neighbor if your neighbor has 271 00:38:13.500 --> 00:38:19.110 William Cheng: Has two pointers. If you merge it with your neighbor and I have three pointer is going to be okay. What if your neighbor has three pointer. 272 00:38:19.470 --> 00:38:22.560 William Cheng: Well, maybe you can borrow one point for them. Now you're gonna end up with two pointers. 273 00:38:22.860 --> 00:38:34.320 William Cheng: Okay, so okay in the, in the real Petri the algorithm is very, very complicated, right. So, would you just going to sort of look at a visual example. So you can actually get a feel of, you know, what do we have to do. Yeah, right. Without going into too much detail. Yeah. 274 00:38:35.340 --> 00:38:45.810 William Cheng: Alright, so we're assuming that this is also true for, you know, for, for, for, for, for the leafy note over here. So living over here. I'm going to assume that you can only store three keys. If it's more than three keys over here that is for. We need to split it up. 275 00:38:46.320 --> 00:38:49.470 William Cheng: Yeah. Alright. So in this example, we are again. 276 00:38:49.740 --> 00:38:56.340 William Cheng: Every note over here. If you have three children. Right. You need to keys. If it's less than or equal to that key. The first key want to go left. 277 00:38:56.520 --> 00:39:02.370 William Cheng: If it's greater than the first key, but less than equal to the second key. We're going to go to the middle. If it's greater than a second here. We're gonna go to the right. 278 00:39:02.880 --> 00:39:15.480 William Cheng: Okay, so you can actually verify that this data is correct. There are sorted alphabetically. OK. So again, if we go to the bottom. Over here you can see that you see that all these these these strings over here. They are sorted alphabetically. Yeah. 279 00:39:16.530 --> 00:39:24.450 William Cheng: Alright, so again, another code review this data structure that's running example over here. So first we're going to insert Lucy into our data structure just that before, we're going to insert Fritz 280 00:39:24.750 --> 00:39:28.950 William Cheng: And I'm going to insert Lucy. So when you try to insert something into the binary search. She 281 00:39:29.370 --> 00:39:36.900 William Cheng: Don't know if you remember your binary search tree algorithm, right, in order for you to insert something the first you have to perform a look up operation you're going to make sure that look up or fail. 282 00:39:37.080 --> 00:39:42.240 William Cheng: And more importantly, when you finished your look up, you need to remember what is the last know that you visited 283 00:39:42.600 --> 00:39:46.470 William Cheng: Okay, because that will be to know that you have to square to create a new create a new data structure. 284 00:39:46.860 --> 00:39:51.720 William Cheng: Okay, so for people. Sure. You also do exactly the same. Now we're that we're going to first do a lookup for us. 285 00:39:52.200 --> 00:39:56.970 William Cheng: Okay, and we're going to make sure that we cannot find it. And the last know that we visit. That's what we're going to add Lucy. 286 00:39:57.480 --> 00:40:03.150 William Cheng: Okay. Alright, so how do you actually look for Lucy, right. You go to the root of the BP plus three, four a, b plus three. All you need to 287 00:40:03.420 --> 00:40:16.080 William Cheng: Know is the root of the tree and that will lead you to all the rest of the data structure. So welcome to the route over here, compare Lucy against Ivan is Lucy bigger than Ivan or less than either right i j k l. So, therefore, is bigger than I then 288 00:40:16.830 --> 00:40:21.060 William Cheng: L M N O P Q R. So there was less than Richard so devil going to follow the pointer in the middle. 289 00:40:21.330 --> 00:40:32.850 William Cheng: There Lucy and Lisa, which one is bigger, while they tie for the first character but you is after i. So, therefore, you're going to follow the middle point over here and click the new season is an auto right you go to the bottom over here. 290 00:40:33.030 --> 00:40:39.720 William Cheng: Lucy is between Lisa and Matthew, right. So, therefore, we need to insert a right here. Right. Right. Okay. 291 00:40:40.380 --> 00:40:48.570 William Cheng: So you need to first verify that the data storage. It doesn't contain Lucy, then you're allowed to add Lucy. And then the last know you visit. That's exactly what you're going to insert Lucy. 292 00:40:49.050 --> 00:40:56.430 William Cheng: There. So we try to insert Lucy over here, this know will be too big because we can only store three keys. Okay, so now we need to split it into two 293 00:40:57.150 --> 00:41:03.810 William Cheng: So I'm going to sort of create some space over here to show you how to create them in design. So I got this picture is exactly the same as the previous picture. I just, you know, shuffle things around. 294 00:41:04.020 --> 00:41:09.210 William Cheng: So now what we need to use that we need to create a new note over here. There's no can actually store up to three data over here. 295 00:41:09.600 --> 00:41:19.290 William Cheng: Lucy is going to go right here right right here between Lisa Matthew. So in this case, we're gonna put Matthew and the call to the new note right over here, this one will be Matthew over here. 296 00:41:19.440 --> 00:41:24.600 William Cheng: And this one will be in the call. So these two will be gone over here, I create a space for Lucy so Lucy will be right here. 297 00:41:25.470 --> 00:41:37.710 William Cheng: Okay, so therefore, in that case, when I finished over here. Again, this picture is a little messy over here. Okay, we're going to actually move Matthew and Nicole right here. So on the left hand side over here. We're going to have Lucy. 298 00:41:39.210 --> 00:41:48.330 William Cheng: Okay, but it would have when we do that, we're going to end up with four pointers over here, right, the full partners over here doesn't fit into this data structure of business because there's a tragic only still up to three pointers. 299 00:41:48.570 --> 00:41:53.280 William Cheng: So therefore, we also need to split this no need to to notes. Right. So again, when you split this into two nodes. 300 00:41:53.730 --> 00:42:01.410 William Cheng: The two pointers on the right, need to go to the new node and the US is because the new ones actually add it right here. Right, we're going to add, I read it. 301 00:42:01.680 --> 00:42:04.920 William Cheng: The, the new ponder over here is going to be between the second point. And the third pointer. 302 00:42:05.100 --> 00:42:12.930 William Cheng: So therefore, the two pointer to the right is going to go to the right over here. So this new block over here. One of them will point right here. And the whole point right here right and this 303 00:42:13.560 --> 00:42:17.970 William Cheng: This part over here appointed this fog and this is that the law and the third partner over here will disappear. 304 00:42:18.870 --> 00:42:26.610 William Cheng: Okay, so in that case we need to also move auto right here. Right. So again, when we do this. The Parent Partner over here need to point to 305 00:42:26.850 --> 00:42:31.200 William Cheng: You know, for things now. So the parent over here has a split are going to allocate a new note over here. 306 00:42:31.350 --> 00:42:35.670 William Cheng: Take these two pointers over here, move them to the right and this one will be this point or be gone. 307 00:42:35.820 --> 00:42:46.950 William Cheng: So this point of view, appointed a two things that Richard is going to be copied to the right over here. And now we're going to end up with two routes. You're not allowed to have two routes in the in any tree. So therefore, we're going to end up adding a new route over here. 308 00:42:48.630 --> 00:42:55.830 William Cheng: Okay, so, so this is how the beat the beat. Plus tree grow when b plus tree grow it has to grow at the top right. Does that make sense. 309 00:42:56.760 --> 00:43:02.250 William Cheng: Well, it kind of makes sense, right, because he will be tree over here. If you are, you know, if all the leaf nodes are at the same level. 310 00:43:02.400 --> 00:43:13.380 William Cheng: Therefore, you cannot grow this way right if you grow this way you can enter one leaf know at the wrong place. So therefore, the only way you can actually grow the beach is like this is like this over here, right. So now the picture over here at get one more level. 311 00:43:13.830 --> 00:43:21.750 William Cheng: Okay, and that's exactly what we did over here, we make the big tree, you know, you know, by by by making a little wider and also we can actually make a little taller. 312 00:43:22.620 --> 00:43:24.960 William Cheng: That. So in the end, when we're done. It will look like this. 313 00:43:25.560 --> 00:43:34.860 William Cheng: Okay, so you can see that right now. The performance going to be much worse, right, because before when we try to get to any data at the bottom. Over here, right. So yeah, the beach is just an index structure let you to get to the bottom. 314 00:43:35.340 --> 00:43:39.420 William Cheng: Right, so every time we need to get the data we need to retreat to internal notes. 315 00:43:40.020 --> 00:43:43.530 William Cheng: Okay, so now when we go to the new Beatrice over here. How do you get to the bottom. 316 00:43:43.740 --> 00:43:54.270 William Cheng: In order for you to get to the bottom. Now you need to go to this three times. So therefore, you're going to slow down by 50% i'd before it's two times I used to buy. So now you still down by by 50%. So, this is terrible. 317 00:43:55.350 --> 00:44:01.770 William Cheng: There. So what do you need to do is that you need to make sure that he needs to try to not grow the height of the tree as much as possible. 318 00:44:02.640 --> 00:44:10.110 William Cheng: Okay, if he if there's a way for you to avoid growing the height of the tree, you need to try your best. Right. So that's why the actual between our them is actually very complicated. 319 00:44:10.530 --> 00:44:18.150 William Cheng: Because we need to avoid growing the height of the tree. Yeah. So what can we do right. So in our example over here, which are the air Lucy right here. 320 00:44:18.780 --> 00:44:26.820 William Cheng: That we tried not to grow the beach. What can you do. Right. So one thing that you can do that. You can actually look around over here to see their space your neighbors. 321 00:44:27.360 --> 00:44:33.150 William Cheng: Okay, if there's space in your neighbor, maybe can actually tell one of your roommate to say, hey, could you move to our neighbor. And this way you can create space. 322 00:44:33.360 --> 00:44:45.450 William Cheng: There. So in this case we will see that the neighbor over here actually has an extra space. So if we ask Nicole to actually move over to the neighbor's house we actually end up creating a room in our house. So the this over here, we could actually create okay 323 00:44:46.740 --> 00:44:57.300 William Cheng: With no with a place we can put Lucy in that. Okay. So this guy is how do we actually move Nicole to the neighbor. Okay, so if you have taken an advanced data structure class. 324 00:44:57.810 --> 00:45:06.510 William Cheng: You probably, you know, seeing the data search and know as the ABL tree right so he is the balance binary tree or by a panel balance by which a surgery. 325 00:45:07.050 --> 00:45:12.660 William Cheng: The way you can actually perform this operation exactly the same as the ABL tree, you need to perform a rotation operation. 326 00:45:13.020 --> 00:45:20.100 William Cheng: Okay. So, okay, I'm not going to get into too much detail we Rotation. Rotation is pretty complicated. If you really want to know, you should take a test data structure class. 327 00:45:20.520 --> 00:45:26.220 William Cheng: Would take a database class over here. So what we need to do that, we need to rotate Nicole, you know, to the right over here. 328 00:45:26.280 --> 00:45:34.770 William Cheng: So when we do that, Nicole is going to go up over here, auto is going to come down over here and I'm going to end up Nicole, going to the note on the right and this key over here will be changed to Nicole. 329 00:45:35.700 --> 00:45:41.520 William Cheng: OK. So again, it makes sense. Over here, because anything greater or equal to Nicole is going to be on the rise. So, therefore, this key also have to change. 330 00:45:42.030 --> 00:45:48.210 William Cheng: We perform this operation. It is possible. You need to propagate all the way to the root of the tree. So again, we're not going to go through that detail. 331 00:45:48.750 --> 00:45:56.700 William Cheng: All right, so we just want to sort of warm up on a point of the possibility to be here is that in order for you not to grow the tree. Usually you need to look at all the possibility to 332 00:45:56.970 --> 00:46:03.810 William Cheng: Move this data around you can shuffle the data at the bottom of this tree over here. This way you can create space. So you don't grow the height of the tree. 333 00:46:05.280 --> 00:46:11.490 William Cheng: Alright, so the question is over here is a, how far do you want to go right if all the notes over here are actually occupied except for the last note over here. 334 00:46:11.670 --> 00:46:21.570 William Cheng: Do you want to propagate all the way to the end over here in order for you to create data create space. Yeah. So remember that, you know, for, for the B plus g at the bottom. Over here, all the keys over here are sorted 335 00:46:22.590 --> 00:46:30.480 William Cheng: Okay. So, therefore, you can't really just, you know, move one, you know, one key all the way to the end of the linguists over here. You have to actually show for everybody, you know, 336 00:46:31.050 --> 00:46:35.970 William Cheng: Towards right there. So again, in reality, this is very complicated. All right. 337 00:46:36.690 --> 00:46:42.900 William Cheng: Similarly, you know, when you go to perform delete operation. Right. So again, when you send it to be something you need to first football. Look up. 338 00:46:43.080 --> 00:46:49.020 William Cheng: He defined that key. If the key is not there. There's no if we need to delete it. Right. Otherwise, if we can find it. You have to leave. On that note, 339 00:46:49.380 --> 00:46:55.440 William Cheng: Yeah. So over here I went into the auto auto is bigger than Matthew would go to the right, auto is less than Richard, we're going to go to the left. 340 00:46:55.650 --> 00:46:59.940 William Cheng: Auto is greater than or equal to auto. We're going to go to the right over here, when we find out all right here. 341 00:47:00.240 --> 00:47:02.940 William Cheng: Okay, so when we delete this one over here this 342 00:47:03.150 --> 00:47:11.970 William Cheng: You know, there's only one key over here is too small. We need to combine with a neighbor. So in this case, the neighbor OB only has two key we combined with them, you can end up with the three key that will be fine. 343 00:47:12.180 --> 00:47:16.770 William Cheng: The problem is that the parent over here only has one pointer that will point to the combined note over here. 344 00:47:17.100 --> 00:47:27.780 William Cheng: That. So therefore, the parent needs to come back with a neighbor, you will come back with a neighbor over here. Now you can end up with three pointers. So, therefore, that will be okay. But the parent over here also point to only on 345 00:47:29.070 --> 00:47:37.860 William Cheng: Only one child, right. So the guy you need to merge it with a neighbor over here as well you merge with the neighbor you going to point to three different data structure over here, there will be ok and now the route will be gone. 346 00:47:38.760 --> 00:47:43.920 William Cheng: Okay, because the road is required to have to have more children right in this case if the route or has one children that's also the law. 347 00:47:44.100 --> 00:47:52.560 William Cheng: So therefore greet Petri grow at the top. They also shrink at the top, which also makes sense, right, because again, all the nodes that about them. They all have to be required to be at the same level. 348 00:47:53.100 --> 00:47:58.770 William Cheng: Yeah. Similarly there, you know, you know. Will you try to perform this operation over here. 349 00:47:59.190 --> 00:48:04.650 William Cheng: In my change a lot of the data structure there. So again, it is possible that you don't have to do this. Okay. 350 00:48:05.040 --> 00:48:15.930 William Cheng: Because if you need to change all the data search over here is going to be pretty costly, but something you're willing to do this right, because you know if you actually can collapse the height of the tree from this point are you going to be you're going to perform much better. 351 00:48:16.530 --> 00:48:18.570 William Cheng: Okay, but you don't really want to do this very, you know, 352 00:48:19.710 --> 00:48:31.800 William Cheng: Be again. You got to be very careful. What if you shrink the height of this tree in one operation. Next time you add another know you grow the height of the tree and then you shouldn't have to go. So in this case is going to end up with very, very poor performance. 353 00:48:32.910 --> 00:48:39.480 William Cheng: Or so. So, India, this is a very complicated. So again, maybe, will he take a graduate level class, you can add they can actually address this problem. Okay. Okay. 354 00:48:39.810 --> 00:48:44.670 William Cheng: Take a database class. Yeah. So the other possibility that you will do over here is that will you delete out over here. 355 00:48:45.360 --> 00:48:49.440 William Cheng: Then we do the auto. So let's take a look at the example here, if we try to delete outdoors. I'll be here. 356 00:48:49.680 --> 00:48:57.480 William Cheng: All we need to do is to borrow one roommate from the neighbor over here. So Richard can actually move right here, then we don't have to, you know, change all these data structure. 357 00:48:57.810 --> 00:49:05.940 William Cheng: Okay. But in order for Richard to be moved it back here, over here, some of those key over here. They always have to change. So in da going to end up changing order login 358 00:49:06.240 --> 00:49:16.380 William Cheng: You know, a number of these notes, right, so remember the login over here. The base is equal to m and m is a very, very large number. So even when you try to use order log, you know, a 359 00:49:16.770 --> 00:49:21.780 William Cheng: Log base. Mmm, this will be a very, very tiny, tiny number. So, only a few notes have to change. 360 00:49:22.170 --> 00:49:27.720 William Cheng: Okay, relative to actually changing the height of the tree that's going to be a major operation. So again, between is complicated. 361 00:49:28.140 --> 00:49:35.160 William Cheng: You need to look at all these different situation and try to find out what is the best way to do that. Alright, anyways, that's the database topic. So we're going to move on. 362 00:49:37.860 --> 00:49:43.200 William Cheng: Alright, the last part over here. We're going to take a look at briefly I'll take a look at namespace management. 363 00:49:43.740 --> 00:49:50.700 William Cheng: What if you have two different discs. Okay, if you have two different days you're gonna end up with two different file system. Okay. Each one of them has a route. 364 00:49:51.180 --> 00:49:53.220 William Cheng: How do you actually named these different file systems. 365 00:49:53.820 --> 00:49:55.890 William Cheng: Okay. I mean, this was a route as well as a new route. 366 00:49:56.190 --> 00:50:06.180 William Cheng: Okay, so how do we actually, you know, sort of, you sort of a uniform a name to actually named these multiple file system. Right. It's also possible that if you have one does. You can actually partition them into different partition. 367 00:50:06.540 --> 00:50:13.620 William Cheng: Right, so you're going to end up with multiple facets them. So again, each one of them has a roof assist them different operating system, they have a different approach. Okay. 368 00:50:14.190 --> 00:50:23.610 William Cheng: So for example, you know, for for Windows right windows was famous for Dr. Letters. If you have drive that is once you have 26 harddrive they're going to be in trouble. 369 00:50:23.910 --> 00:50:32.640 William Cheng: OK. So again, windows, you know, in the beginning, you know, they could never imagine anybody web 26 hard drives, but today is our data center, you can actually have, you know, tons of this Dr. 370 00:50:33.510 --> 00:50:41.310 William Cheng: Alright, so, so Windows Azure as a new naming convention, right, we're starting with window and Windows NT they have another way to name them a resource or this 371 00:50:41.700 --> 00:50:50.790 William Cheng: This always backslash backslash and then followed by you need name a device and then followed by, you know, the, the, the file system on that particular device like 372 00:50:51.210 --> 00:51:01.020 William Cheng: A Unix. Unix, what happened is that what they would do is that they will actually, you know, combine these multiple file system into 1000 of them using something called file system mounting 373 00:51:01.800 --> 00:51:09.330 William Cheng: Okay, so when you're doing your carnal to you already see this word mounting. Right. So yeah, what's that all about, we see that we're going to start with a device like dev slash 374 00:51:11.400 --> 00:51:22.980 William Cheng: I guess, you know, the, these, these are called St zero st one. So I think in a way. Nice is called slash Deb such HD zero or something like that was what he stands for hard drive. 375 00:51:23.610 --> 00:51:34.680 William Cheng: Okay, so what happened is that you can actually met one of these folks, you know, 111 of these files to send in another directory. Whereas when we met this particular policy. So we will now the into the slash directory 376 00:51:35.190 --> 00:51:39.390 William Cheng: Okay. So in this case, your directory your root directory started out actually on a hard drive. 377 00:51:39.930 --> 00:51:49.680 William Cheng: Okay, so this one would either remember which harddrive. It is so what we'll do is that will mount this file system in another directory. I know. And this director. I know typically is going to be was one of the choice over here is going to be 378 00:51:50.130 --> 00:51:57.240 William Cheng: The root of the fastest, then we can also mountain harddrive in any way instead of directory hierarchy, as long as it's a directory. I know. 379 00:51:58.380 --> 00:52:09.090 William Cheng: Okay, so, so again units this local file system out here, we're going to create an entry in the I know to point to the file system, but we only do this in memory and not actually inside of our system. 380 00:52:10.050 --> 00:52:13.290 William Cheng: Okay. So, therefore, this is just a trick that the file system will play 381 00:52:13.680 --> 00:52:24.960 William Cheng: Okay. So inside the in memory. You know, in memory data structure you mount a particular you know amount of particular hard drive into the directory. I know into the directory. I know of another system. 382 00:52:25.680 --> 00:52:34.140 William Cheng: OK. So the picture. So look like this right over here, I one passes me. Here's another forces him. I can mount this file system. Now the route and process them in a directory. I know. 383 00:52:34.410 --> 00:52:38.490 William Cheng: Okay, if it's a file. I know that you're going to get a permission denied. Otherwise, we're going to be able to mount 384 00:52:39.570 --> 00:52:50.970 William Cheng: Is that another directory. So this way we perform path name resolution. Now, we won't pass the resolution, you start with slasher style, you go to a and then when you reach see then see what notice that I'm actually a file system. 385 00:52:51.600 --> 00:52:56.850 William Cheng: Whereas, in this case. Okay, you got to start a path of resolution again starting from the root of another file system. 386 00:52:57.960 --> 00:53:04.680 William Cheng: Right. So again, this all this all happened inside you know he he inside of our system. Okay, so therefore 387 00:53:05.370 --> 00:53:10.620 William Cheng: You know, therefore, this is how you actually implement this. Well, you're going to use polymorphous that 388 00:53:11.430 --> 00:53:21.210 William Cheng: Right, so, so this directly. I know can act as a directory can also add as a file system. Right. So again, if you look at your kernel to co that's already happening, you know, entire Colonel to go. Yeah. 389 00:53:23.040 --> 00:53:30.270 William Cheng: Alright, so, so, so, so the you know the the the place you can actually mount another another file system is known as the mount point 390 00:53:30.510 --> 00:53:39.720 William Cheng: Okay. On mount point over here. So, so maybe we can make slash user into a mount point. So, this way we can actually mouse slash dev dev side this to into slash user 391 00:53:40.290 --> 00:53:44.760 William Cheng: OK, so the way with this is done is, is that we're going to issue a command. So this is a UNIX command. 392 00:53:45.150 --> 00:53:55.470 William Cheng: You need to do this when you are a super user you say mouse like deaths. I showed this to and slash user slash user is going to become a mount point and this point, we're going to mount this particular file system. 393 00:53:55.830 --> 00:54:03.300 William Cheng: Okay, so when we finished doing this again inside memory, is it you, you're using polymorphous them to say that this particular directory is no longer directory 394 00:54:03.450 --> 00:54:11.280 William Cheng: And now it's the fastest them right took on a different personality. So when you perform path of resolution, you need to go to slash deselect is too and starting 395 00:54:12.120 --> 00:54:16.140 William Cheng: Starting to look for data over there. Right. So each other access slash user 396 00:54:16.530 --> 00:54:23.040 William Cheng: User slash been right when you get a slash user, you're going to realize that this is the file system. So you go to slash slash this to 397 00:54:23.220 --> 00:54:30.360 William Cheng: You go to slash their search. There's two and then you look for the bin directory been is actually right here and then continue to perform path and resolution over there. 398 00:54:31.650 --> 00:54:33.720 William Cheng: Right, so it's almost like you know 399 00:54:36.210 --> 00:54:45.360 William Cheng: I guess it's almost like a symbolic link. Okay. But again, a symbolic link is a different kind of file. So in this case is just using polymorphous them that you can actually get to 400 00:54:46.680 --> 00:54:51.570 William Cheng: The using polymorphous that you can actually restart your path and resolution operation. Yeah. 401 00:54:52.590 --> 00:55:01.080 William Cheng: Alright. So for example, you can add your mouse like Jeff said this to into slash user. Okay, so from this point now where you type slash user slash slash bash 402 00:55:01.320 --> 00:55:08.160 William Cheng: So when you again traverse like user, you're going to realize that you reach a mount point. So in this case, instead of mount point, they will store. 403 00:55:08.490 --> 00:55:19.710 William Cheng: This is, again, it's almost like a symbolic link actually store the the the the the the the name of the real path and you perform path of resolution starting from here again when you finish that over here. 404 00:55:20.460 --> 00:55:29.100 William Cheng: Okay, when you perform that path of resolution over here. You're going to save the contacts. When you finish traversing that positive resolution, you're going to restore the context and continue to perform path of resolution. 405 00:55:29.640 --> 00:55:41.190 William Cheng: Okay, so you will go to slash user, you will save the contest. Go to reverse slash slash this to once you go to sidestep that this to you restore your contacts and you continue to look for Ben and continuous loop of ash. 406 00:55:42.210 --> 00:55:51.630 William Cheng: OK. So again, even though the slash steps I said there's two sessions I express look like an alias is as if you're going to replace the strings slash user slash test if there's to 407 00:55:51.870 --> 00:55:58.770 William Cheng: This particular mechanism is not an aliasing operation right when you, when people talk about aliasing. They basically talk about a nickname. 408 00:55:58.980 --> 00:56:08.580 William Cheng: All you need to do is to build a lookup table to translate one string to another string. Okay, that's not what we're doing over here because we're, what we're doing over here is using polymorphous 409 00:56:09.600 --> 00:56:19.320 William Cheng: Okay. So, therefore, this has nothing to do with aliasing. Okay. Alright. So this is, again, this is done in UNIX for for for typical UNIX system over here. 410 00:56:19.740 --> 00:56:28.050 William Cheng: They actually create a bunch of mount point in the size empty directory as I get this for Linux is them. So, in such a venti. There's a lot of, you know, the 411 00:56:28.590 --> 00:56:35.370 William Cheng: Directory over here. Maybe you can actually create a directory for a USB guys are some of the dynamically creative process then 412 00:56:35.580 --> 00:56:42.540 William Cheng: They will automatically create a mount point in the search empty directory and then they will basically execute this command. So once you 413 00:56:42.960 --> 00:56:51.150 William Cheng: You know, a discovery device like a USB device, you will create a mount point and then you will mount the fastest among us ESP device on to that mount point 414 00:56:52.110 --> 00:57:03.210 William Cheng: Okay, so this is done in the unit system for Mac OS X, and they also run Unix right but instead of calling them slash M AMP t they call a slash volumes, right, if you're a Mac user you've seen that already. 415 00:57:03.720 --> 00:57:08.850 William Cheng: Mac actually go to extreme every time when you try to download a file. So let's say that you are downloading 416 00:57:09.420 --> 00:57:18.960 William Cheng: A Chrome, the Chrome browser or you're downloading the Firefox browser and you try to install it on the Mac, when you double click on it, what happens, right. So those of you actually 417 00:57:19.680 --> 00:57:26.250 William Cheng: On the Mac, you will see that you're going to end up with the file system that can mountain in the slash volumes are the site volume file, file system. 418 00:57:26.610 --> 00:57:31.290 William Cheng: Okay, so what you are downloading, you know what, what we're doing is 419 00:57:32.070 --> 00:57:39.150 William Cheng: We're down in something like the Chrome browser or any kind of application software while you're downloading downloading is actually a file system. 420 00:57:39.720 --> 00:57:42.630 William Cheng: Okay, so what it will do is that it will create a mount point, he says, large volume. 421 00:57:42.900 --> 00:57:51.210 William Cheng: And then mount that process them into the into the mount point over here. And now to become accessible and you can actually double click it and it will install the software from this point. 422 00:57:51.510 --> 00:58:03.810 William Cheng: When it finished it will ask you whether you want to, you know, a mountain. Right. So in that case, you drag into the trash can, where you drag a you know this this particular thing inside into a trash can. It will disappear from the in memory file system. 423 00:58:05.070 --> 00:58:13.620 William Cheng: Alright, so again, you know, Mac OS is one of units. And that's why they have the similar data structure that, for we next we need to can actually implement mounting 424 00:58:14.160 --> 00:58:19.350 William Cheng: So right now, mounting equal to zero in conflict I ok so again I recommend you not to do that right now. 425 00:58:19.860 --> 00:58:27.630 William Cheng: You only play around with this maybe when the semester is over. So what is the message. So I always get people asking me, you know, I found the cardinals. I'm pretty interesting. 426 00:58:28.230 --> 00:58:36.870 William Cheng: What should I do after the semester is over that. Well, I said, there are two things that you can do know the first thing is that you should re implement everything from the Brown University. 427 00:58:37.620 --> 00:58:45.360 William Cheng: Okay. The Brown University, they give you live drivers, a well why don't you leave that file and implement your driver. So look at the we need documentation and find out what you have to do. 428 00:58:45.690 --> 00:58:52.740 William Cheng: It this way, you also learned about drivers device drivers and then you also have to re implement systems analysis that so the lead lip. 429 00:58:53.070 --> 00:59:00.600 William Cheng: System PA system that a over here again implement your stuff. Now the other thing you can play with the winnings, they can actually turn this things to one and play with it. 430 00:59:00.780 --> 00:59:08.640 William Cheng: And look for all the places inside of winning source tree. Find out where they are using mounting and that you know again there will be saved me not yet implemented melty. 431 00:59:08.910 --> 00:59:16.110 William Cheng: So those will be the place that you have to implement and you will see that it's actually very simple. Right, because there are only a few places you have to, you have to implement 432 00:59:16.680 --> 00:59:26.700 William Cheng: For mountain to work. OK. So in that case, once you turn that on, you're using polymorphous them so therefore you don't polymorphous already where you finish Colonel three, so therefore they should be, they should be pretty straightforward. 433 00:59:27.780 --> 00:59:32.970 William Cheng: OK. So again, it should be very clear that melting the file system is not the same as using alias. Yeah. 434 00:59:33.630 --> 00:59:39.780 William Cheng: Alright, so we finish this part of chapter six and next time I guess we're going to the last part of chapter six. 435 00:59:40.230 --> 00:59:45.870 William Cheng: We're going to look at a case where you have multiple deaths. What if you have all actually went to look at a case where where where the dis died. 436 00:59:46.710 --> 00:59:54.390 William Cheng: Okay. So, so far, we will talk about you know crash resiliency when your file system crash or when you lose power. Well, in that case will be able to recover from 437 00:59:54.780 --> 01:00:01.170 William Cheng: One of your decide right here. This time, how do you actually recover from it. Okay. So that will be the next topic. Right. Okay. See you on Wednesday.