CMU Database Group · 1:22:14 · https://www.youtube.com/watch?v=scUtG_6M_lU
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat lcks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol glad you guys are here uh funny turnout uh cuz this is this is be the best data structure ever learned in computer science right forget red black trees right forget display trees nobody uses that B+ trees is what we want to use so this this is going to be the best um before we get into that uh again I everyone be hopefully have started or finished project one that's going to be due uh this Sunday coming up we had the
0:52 uh recitation on last Thursday we also did a additional recording of how to profile uh the performance of your your of your uh of your buffer Pool Guys So Pro profile your buffer buffer pool so that you want to get higher in the leaderboard right teach you how to do a flame graph and if you've never seen how to use perf before we have a tutorial on how to use that and you can do this on either the command line or C line or I think uh Visual Studio can also support it as well homework 3 will released on the 25th and then the midterm although you know three weeks away do at least put it on your radar
1:27 that's going to be in this room in class uh on October 9th the Wednesday and that'll cover everything up to uh I think lecture 10 including lecture 10 so whatever the the whatever the Monday lecture is before the the midterm that will be in the midterm okay we'll have more information about that uh next week and then if you have any special accommodations you need need us to handle please email me sooner rather than later okay any questions about project one okay Beyond this again we have some op talks uh the first one is actually today it's going to be on Zoom at 4:30 p.m.
2:04 after class and that'll be a uh project committer for data Fusion uh somebody actually works at influx uh but influx DB will be talked later in the semester but they they're based entirely on data Fusion so Andrew L is going to talk about what data Fusion is why it matters and how uh how you could build a more complex system on top of something like data Fusion so that you have to learn all the things doing the semester but then like you could build a more complex system on top of
2:30 and then the following next week we'll have the guy that actually invented data Fusion uh he's now apple he got bought out by Apple from ad of Nidia and then he has a project called Data Fusion Comet it's basically it's a accelerator for spark because Sparks in Java Sparks old and Sparks slow data Fusion comet is a way to use data Fusion to make sparkis faster and then also in the the week after that or the or on Tuesday next week we have somebody uh from Oracle tanker who uh is going to talk about how they use how they support Json in Oracle
3:00 Tanga is a good dude uh he's pretty high up at Oracle um couple ticks below Larry Alon he's a good dude it should be a good talk and that that'll be uh in 6501 but I think he's calling it over zoom and it'll be Pizza of that one okay
3:13 again these are optional if you want to go beyond the course these are the things I encourage you to check out because a couple of you asked me how do I learn more databases other than me cramming as much as I can in the slides
3:21 uh these are opportunities to go beyond the things we've talked about all right so I know I said at post on Patza that we were sort of rushed at the end to go over extendable hashing and linear hashing but we can talk about I can answer any questions you may have at the at the end of today's lecture just as a reminder that last class was about hash tables which are these data structures are mostly used the in the inside of our database system to keep track of various things we need to keep track of while we're running queries and running transactions uh we can use them
3:50 as a as an index but the most the indexes that when call create index B plus that we're talking about today in most systems hash are nice because they have the the average time complexity of 01 meaning you know you you do a look up on a key you hash to some location and that's going to be uh roughly where you need to be to find the key you're looking for or that you identify that you don't need it like I said most of these hash tables that we talked about last class will be primarily used for
4:17 internal things inside a data system not something you would normally expose to the outside world now there are some data systems that are built entirely off of uh hash table where the only you the only thing you get is essentially a hash table roughly red redis is is basically
4:31 that all right so now today's class we want to go beyond this and say okay we talked a little bit about how hash was be use to indexes and these are meant to be data structures that are going to allow us to find logical data like tupal or records in our in our databases more quickly so we want start come in the background of what that is and also understand filters which we'll see we'll see next class and then we'll talk about how we again the the next two lectures are how we're going to build optimized versions of these different data structures we could use so an index as
4:59 sort of be obvious to everyone here is going to be a data structure that's going to be based on some subset of of a table's attributes like some subset of a columns or all of them if you wanted to
5:09 um but it doesn't have to be where they're going to be organized and sorted in such a way uh that's going to allow us to do quick lookups to find single tupal now it's not always the case sometimes you have indexes like in postgress you can get blocks of tupal
5:24 right uh but for our purposes today we assume like for a given key we can find a a small set of the table an example of an index will be a b tree B plus tree a filter is a data structure that can answer what are called set membership queries meaning it can tell you whether a key exists in a set but it can't tell you where it is right a B plus tree or index I'll tell you for a given key here's where to go find it in in in my my table a filter says forgiven key yeah I usually it's it's uh problemistic so say yes I I probably do have that key you're looking for or no I
6:01 don't and the good the best example the most widely used one is be a bloom filter which we'll cover in last class um this is something you again a filter you wouldn't declare on your table although some data systems allow you to declare Bloom filter you can declare Bloom filters on tables that can be used for query optimization but in general this is something like like a hash sheap going to be used on the inside whereas a b plus3 is going be something that we have to declare like for for an index that we have that the a human has to tell the D we want this we want this
6:27 index there's a whole another thing we'll talk about next week were how do we actually keep these things synchronized uh and keep them thread safe or concurrent for concurrent access meaning like if I update a table and I add a key I want to make sure it it appears in in my index so if I do a look up on that index I don't get a false negative again that will cover throughout the semester but being back of your mind you got to realize that like if anything's in the table I want also reflected in my filter or my index to avoid again false
6:55 negatives all right so today's class we're going to most again just we're going to focus entirely on B plus Tre we can teach an entire course on B+ trees uh but try to cover much as I can the basics within a single day and then we'll call basically we'll start with the basics of it different design choices we have to consider when we build our p+ tree in in our database system and then various optimizations we can employ to make these things run
7:15 faster and as a spoiler project two will be a b plus3 this year right so it'll be based on the things that we talked about today and it's and so and B+ is the most widely used data structure in database systems um I was actually reading a Blog article this morning uh from cadb they started with a red black tree I don't know why then they realized that was a mistake and of course they switched to a B+ tree
7:37 right all right so the confusing thing about B+ trees is that there's a they're in a family of data structures called be trees but there is also a specific data structure called a b tree and then sometimes people say in you know for a database system they'll say yeah we're using B trees but it's really a B+ tree like in postgress say yeah we have B trees but as we'll talk about today it's going to it's really B plus tree and there is a distinction between a uh not to be overly pedantic there's a distinction what a b tree is versus a B plus tree is but most people Implement B+ trees but most people don't Implement B plus trees as it's originally defined
8:15 back in the 70s they use bits and pieces of various optimizations that people have developed over the years uh that will briefly cover so the original be Tre paper goes back to 1970 uh and it's from uh Bayer and mcra uh mccrae's actually seum
8:34 he got his PhD here in 1969 before any of us was born or maybe even earlier uh and then he went off in to to Boeing and built the um you know built the bee with with Bayer uh but this is not the paper nor normally people read uh there's a there's a survey paper from 1979 out of IBM uh called the UB ubiquitous be tree and this basically describes Again by By 1979 this data structure was so widely known and employed in database systems like that's why it was it was called ubiquitous because it was essentially everywhere and even though this is you know nearly 50 years later the b+3 is still going to be the best data structure most of the times of course we're going to tweak it for Modern Hardware modern situations but the core data structure is essentially the
9:17 same so there is no original B+ stre paper right in uh there's a a tech report from IBM in like 1973 uh I think where they talk about um uh different variants of the B tree and in it they include the B plus tree which I'll again I'll find for you guys in a second um and then they also never Define what the what the B stand for let me take a
9:41 guess he says balanced huh balanced binary no because binary means you can have only two keys right we're more generalized what's that he author's initial Bayer that's another good choice the other uh rumor is that stands for Boe because they vented that Boe right well so there's a there's a very important followup paper that came out 1981 on the be link tree and this is actually written by someone here who did his PG at CMU and is actually still at CMU so Phil Leman Works in in the Dean's office on the fifth floor in Gates right
10:21 and so we'll see what the belink Tre treat what the belink tree paper does later on they're basically going add these sibling pointers and this is what I was saying before that like everyone says they're going to implement a b tree or B+ tree but it's not the classic one that been known they almost everyone's going to use the sibling pointers from the belink tree because it makes concurrent access more easier right and if you if you go actually look in the postgress code uh you know if you go look at the all the PDFs you can click the links so this will take you to a source code file and sure enough at the top of the file in the header it says
10:51 this is a correct implementation correct is always good uh of lemman and Ya's High concurrency B Tree Management algorithm from the the B link tree page right and so so I asked actually Phil sent me an email last week uh because I was I mentioned him oh yeah we're teaching you know teaching B plus trees again uh and then he says he's 90% sure that back in the day the the the beay mccre guy the B stre authors told him it was named named after Boeing right it says the Boeing tree right the only think why is Boeing building a database system again back in the day there wasn't off the offthe shelf software like we have now so if you're a plane manufacturer and you're trying to keep track of all your parts you need a database system one of IBM's first database system they built IMS they built that to keep track of all the parts to build the Rockets go to the Moon right and you can you can buy IMS
11:41 today all right anyway so uh so but B tree the original PB tree is is from the 70s again the the B+ tree sort of came later on right so what is the B+ Tre so it's going to be a self-balancing ordered nway uh tree uh that's going to support efficient searching sequential access ins sech deletions all in log n
12:09 time right and the the the M here factor is consider the fan out so the number of of branches or or pointers coming out of the nodes corresponds to the fan out and somebody said oh b stands for binary so binary would be m equals 2 right um
12:29 and that's only you know well yeah so it's m equals two but like the fan out for a real data system think of like hundreds of keys within a single node right think of like you know we talk about 8 kilobyte pages in Po in postgress how many How many pairs of 64 bit integers can can you put in there quite a
12:48 bit right so the fan out is going to be quite large and that's going to make the height on average for most uh most indexes B plus trees three maybe four five is pretty extreme so it's going to be pretty efficient for us to go find the data that we need so the B plus tree as it's classically defined has these properties it's be considered perfectly balanced meaning every leaf node is going to be the same distance to the root right to get to the bottom layer that's always going to be the same same number of hops going back up right mean traversing down is always going to be the same cost log log n and then every node other than the root will be at least half full so the number of keys you have to have per node
13:29 has to be greater than uh M2 minus1 and then M minus1 right so I always need at least to have half half the nodes full and then when they get full we we have to deal with that when they get less than half full we have to deal with that we'll see in a second and so this data structure is be nice for us because is we're be able to optimize ourselves or optimize the the access patterns to handle reading large blocks of data and writing large blocks of data which we said we wanted to do at the very beginning because sequential access is cheaper than Random Access so
13:59 we'll be able to design our data structure and take take advantage of that now the text textbooks Define the you know the textbook defin these properties I'm telling you these properties and we'll see you know throughout the the lecture real word implementations aren't always going to follow this they're going to lack some of them in fact if I go back to the the postgress code here right if you can read the the the file path it's Source backend access NB tree read me N means non non so it's non-balance tree because they're going to break some of the some of these requirements and that's okay because it's going to be it's going to get allow them get better
14:33 performance but let's understand the the the sort of again the text definition and we'll see how to how to break it later all right so here's a really simple example of a B+ tree um right in this case here it's it's there's two keys per per node and so we have to first Define what the node types are so at the very top we have the root node that's the entry point for everybody coming into this data structure into the tree then you have the the the parts in the middle the inner nodes sometimes called the non-leaf loads right and then at the very bottom we have the leaf we have the leaf nodes so you can see think of the bottom as being uh the leaf noes is the all the keys we could possibly have that are going to be in in sorted order either from lowest to highest or highest to lowest you can Define this when when you when if you want to create an
15:18 index so the contents of the the root node and in in inner nodes uh it's essentially alternating key value pairs where the key is going to be uh or it's going to start off with with a pointer to a node below it followed by a key that represents the the separation of of the value or the key
15:37 space and then in the leaf nodes we're going to have key value pairs where this is the actual the actual data that we're trying to represent like for a given key here's the value the value could be a pointer to a record ID could be something else we're tracking in our system
15:51 right so the way to think about the keys in the in the and the above the inter nodes and the root nodes they separator bar or guide post that tells you as you're traversing the the tree if you're looking for a predict pick key whether you want to go left or right so in this case here at the top we have key 20 so that means all keys that are less than 20 will be to the your your left of it
16:15 and then all keys that are greater than equal to 20 will be on the right of it so if I'm looking now for a key I could look at this at the very root look at the the you know that 20 and decide whether I want to go left or right and that tells me how to go down and I just do the same operation when when I go down
16:30 below right one additional thing we're going to have now is sibling pointers so I think the original B+ Tre implementation or the definition had siing pointers at the bottom is just a way for us to get to left and right along along the leaf nodes but the tree paper added is siing pointers for the inner nodes as
16:50 well and we'll see this later you know when we do scans along the the bottom we obviously can Traverse along the uh the these these sibling pointers The Sibling pointers for the inner nodes are going to help us later on when we want to do concurrent access uh for split to merge because now we can jump across more easily without having to go back always back up to the root
17:13 yes this question is m is if m is greater than two are there sibling pointers uh between every possible pair no it be the sibling pointer would be for the node like for this node his sibling is over there right so again think of like large pages
17:29 it's you know it's a it's you know it's not a record idea where you have to have the the key the the page number and the slot number it's just a page number so 64 bits or 32 bit 32 bit integer not big yes um but for the for the bottom row if there's three children per node is it just the left child pointing to the middle and the middle pointing to the right or do they all three point to each other his question is if if if I'm the leaf note here are the The Sibling pointers what sorry is if there's three children in that same node because you said there can be more than two children
17:59 yes all three of them point at each other or is it just the uh it be going in in lexor graphical order yes you like this guy this is six this is 10 if there was a if there was say eight eight would between in here and this guy would only point to that right because again what what are we doing here what is what is what's the leaf node or Leaf nodes what do they just look
18:21 like it's a link list that's all it is right and so what the B plus Tre is just the scaffolding above this allows us to get to where we want in the link list without having to do squential scan yes so I no that
18:39 arees this question is there's no values for the in noes the the values would be the the node pointers right so I should make this more clear this the the scheme I'm showing at the top right for the root node it's the same for The Sibling nodes sorry for the for the inner nodes right there's pointers down to no children nodes below it
19:04 yes it's the question why why am i showing three node pointers here they would be null in this example I'm just trying to show that like the layout would be node pointer key node pointer key and then in this case you only have one key the rest is all
19:17 null and you keep track in the metadata say how many entries you actually have right or a null bit map so we'll see this again next class when we talk about Skip list skip list is be basically the same thing where they have a link list and they build crap on top of it right again once you understand like it really is just a link list but like guide post allow you to jump into that more quickly then it changes your thinking about about it it's you know it becomes less exotic in my
19:45 opinion all right so we sort of already covered this the nodes are to be comprised of an array of key value pairs again depending on whether I'm a leaf node inner node or a root node the values would either be pointers to other no if I'm a root node or inter node or a a value that corresponds to the thing that I'm trying to uh to map in my in my tree most of the time the arrays will be sorted in key order they don't have to be but most implementations do do that
20:14 um and then uh for null values or null Keys you have to decide where to do that and in in most system you can either declare them either the beginning or the end right because you can't compare nulls with each other you can't compare with null with keys so you got to put them somewhere you just put them at the beginning or the
20:32 end so one thing I also to point out too is that going back here notice how the the the children nodes don't store pointers to their parent nodes right and we'll we'll cover this next class when we talk about how to make this thread safe but the idea is that because now we can only Traverse the the tree in one data structure sorry in one direction from the from the top to the bottom you can go left and right lateral moves that complicates things we'll talk about next class but in general like we're only going from the top to the bottom now we can't have Deadlocks because it's not like we have someone from the bottom trying to come up right everyone's coming in always One
21:09 Direction Again The Sibling nodes will will cause uh sibling pointers will cause problems for us some systems only have the link list in one direction for the sing pointers so the same thing you don't have deadlock so you can't have people come in different directions you always go One Direction postr go has has doubly link list but you don't have to and it's a trade-off between again do you want to spend more time jumping into the tree to find the things you're looking for or can you just rely on the on those pointers but now you got to maintain those pointers and that CA other other
21:38 contention so there's no free lunch all right so go further detail what the nodes actually look like so as I said it's there's a there's a a pointer for the the previous page the sibling and the next sibling and these are just page IDs 64 bits or 32 bit inss and then I just look use my page directory we talked about before to go find the the page that that I want if I'm traversing along and then we have these key value pairs that are just alternating one after
22:06 another all right and the values are just going to be pointers or something uh so the actual structure will look something like this you actually have some metadata in the header that keeps track of like what level you are in the tree so you know how to interpret what the contents are of the page uh how many free slots you have the previous next pointer other additional metadata like n bit maps and so forth and then you have the the key value pair sorted at the end
22:29 and that's just think of like a struct or pair of key value over never again and in bus hub it's set up this way an alternative and actually a better approach is actually to do this where you store the keys continuously one after another and then have anal the value array stored that continuously separately one after another because then it's like almost like the column store we talked about before because now I can rip through and do binary search or whatever I need to on the sort of keys more efficiently and not have to jump over pointers I that don't or values that I I don't care
23:04 about can you guys close the door sorry yeah sorry thanks all right so what what are the values so as I said if it's going to be pointing to tubes it's going to be the record IDs again and most systems are are going are going to do this all right and the record ID get just the page number and the offset or whatever additional metadata we need to jump to things that we need this one's most
23:26 common but we talked about before about index organized storage where the leaf noes are actually where you could store the tupal themselves right postgress sorry sqlite and and myl famously do this for Oracle and SQL Server you you can uh optionally declare a table you want to be organized in this way but for myl and at least in NB and SQL light always like when you create a table it's going to be stored like this right we discussed this before in in lecture 4 so for the primary key index the leaf nodes are just going to be the the tub themselves if if it's the secondary index like a secondary key index then the leaf note will typically contain the the primary key of the TU you're pointing to so you do look up on the secondary index get to the leaf node now you have the primary key then you do a second look up in the primary key index to find the thing you're looking
24:15 for right because you can't use the record ID sorry you can't use a page number on offset because the leaf nodes will start moving around as we'll see when we when we rebalance the tree and therefore you don't know exactly where it could the physical could be so if you store the primary key as the value then you're guaranteed to be able to find it using the the primary key
24:36 Index this complicates other things well with mvcc again we'll cover this later on the semester but again most of the time it's going to be the record ID if we're using it as an index all right so I made a big deal that there's the B tree and the B plus tree what's the actual difference so in a b tree similar to like a red black tree and other trees you may be familiar with the values are actually could be in the inner nodes
25:01 themselves meaning as I Traverse down I I'm I'm not just trying to always get the Leaf nodes I could find an inner node and actually the value I'm looking for the key value pair could be in that inner node right so this would be more space efficient because each key can only appear once and then if it gets deleted then it it won't appear anywhere in the tree at all in the B+ tree the values that we actually care about are only found in the leaf nodes in the inner noes or just guide posts to get us down to to the
25:31 bottom that means we may end up deleting a key and it'll get removed from the leaf node but it could still exist in the inner node because why pay the cost of going cleaning it up it's just helping us get to the bottom we can leave it
25:45 there why why so why do we care about this distinction what's the key thing between a b tree and B plus tree if the leaf nodes only have always have the values yes you wouldn't have to restructure the whole tree when you're deleting things he say you wouldn't have to restructure the whole tree when you're deleting things you still have to do that with the B plus
26:03 Tre so so you so I just me refas what you're saying you're right that if I do a traversal in B+ tree I get past all the inter noes now I'm at the bottom I never have to go back up say for a scan and that means I just rip across the bottom sequentially along the leaf nodes to find all the data I'm looking for in a red black tree or or a B tree you got to kind of B bump bounce up and down the the noes to find all the things you're looking for so this this is going to maximize the squential access for us yes you might put all those
26:37 inory St is you might put all the L the non-leaf nodes in memory um yeah so yes so but you you still have so save it is thing you're trying to say is like the you could keep the inner no inner nodes in memory and not just fast lookups but then only fetch the things from disc or leave you know evict things that are to Leaf noes that are maybe not likely to be used you would get that anyway if it was a b tree like if you're only accessing one side of the tree then the buffer pool alth the replacement policy will will will rip you know replace those things as need it yes why we want
27:10 to is why we want to do that we don't want to do that that's what the B tree does that's old we don't want to do that I mean they're both old yeah we don't want to do that we want everything all the values we care about are on the Lea noes so as he said when I do want a d up a squential scan or a range scan I just Traverse to the bottom then I can scan along the leaf nodes
27:30 sequentially ideally and just find all things I'm looking for and never have to go back up the tree it statement is would that benefit Point query uh to your point yes so in a b tree since the values may be in the inner nodes yes I may be lucky in the first thing the root has the thing I'm looking for and I'm done right it'll complicate when we do updates right because the red black Tre you have to do rotations that makes all that harder
27:58 uh but the the win we get for sequential access is is is it's going to be a huge game changer for us why we want to do this yes so say said I said that oh when we get to Leaf nodes we be able to rip through through things sequentially but what if it just so happens that the pages
28:33 themselves uh aren't contiguous and and then becomes random well because I know that when I'm creating the data structure uh and I'm allocating pages I would know it's a leaf page and therefore I should maybe allocate it uh to be larger than inner node we can change that right or then also to I could preallocate pages to say here's a bunch of Lea pages that are be continuous to each other and I make sure that they are logically contiguous and both physically
28:58 is yes then how would you number Bas question is how would you how would you tune the number of keys you want to have in a node that'll come later the answer is dep again it's a cop out I'm GNA say many times that it depends but one of the key factures actually going to be the hardware if it's in memory 512 bytes is probably enough if it's a really slow disc one megabyte you can change that depending on what the hardware is
29:28 all right so let's get let's get through the actually how to maintain this thing do inserts and deletes but I think everyone understands the basics of how to do lookups all right so an insert the idea is that we want to figure out we Traverse our uh our data structure the B plus Tre as if we're doing a lookup right that's the same same uh algorithm
29:48 and then we find the leaf no where we where our where our key needs to be so then if the the leaf not we're going to insert into if it has enough space then we just insert it inserted order and and we're done but if it doesn't happen in enough space then we have to split it and we'll create two create a new node and take half the keys in the node that we're splitting into put them on the new new node New Leaf node and leave the other half there and then we have to update our parent which may recursively update the rest of the
30:17 tree uh depending on what the layout looks like so that we can redistribute everything right so this a simple example here so again we have these these these guide posts here uh and this again this is saying that everything less than four is on this side greater than greater greater than equal four and less than 12 is over here and then uh greater than equal 12 over there use a more tight notation there so if I want to insert six right six should go here
30:43 right because five six is between five and nine but the problem is this node is full so we're going to have to split it so we'll we'll slide over that existing node create a new node here and then take half the keys that are in the one that we're splitting keep half here and put half half over there right so I'll put n and 10 on this side and then keep five here and then now I can to start
31:07 six all right am I done what what am I'm missing right the inter node now needs to be updated to reflect that we now have UND new split it right so I got to put a value here so all I have to do is just take the the the smallest value here which is nine promote it up there and then this this changes the uh you changes all the the the guide posts what what key range is covered by uh you know
31:39 what subtes so now if I want to insert eight right again it start with the root I use my guide post to figure out where need to go right eight is less than nine so it's going to go here right and I just insert eight and that's fine that's easy
31:58 let's look look at a larger tree right with with more nodes per or more keys per node so I want to insert 17 right 17 is going to go here that's fine no issue now I want to insert 16 16 between 15 and and 17 so it's going to go here but now again our node is full where where the new key should be so I have to split
32:21 it so we'll do the same thing we did before we're could to create a new new Leaf node slide over the other guy split half of the half of the keys uh to go stay here half the keys go over there like
32:35 that right now I need to then uh make sure I update the parent node so now it points to the new node I created but the problem here is that the the parent Noe is full so I have this new parent uh the you know guide post up above in in a root the root node but I can't fit it into my my current root node so again now I just recursively do the same thing I did before at the leaf nodes I'm going to split the the root node put half the keys on one side half the keys on the other
33:10 side all right so I I but now I need to go decide because because it's the only node at this at this level because it's the root node I got to make another level above it so I'm going to pick the Middle Point here take 13 that's going to become the the split point for the level above me I take
33:30 my U create a new note here split the going back here sorry take 13 goes up now I can put 16 but now I need to update 13 to to point to to uh to the I need to split this one further right so I take split it out to two two inner nodes half goes here half goes there and then now my root node points to the the the two the two intern noes are created for the second
34:01 level right and the boundaries are this so again recursively keep going my do my splits until I meet my root if my root is full then I got to split the root and make a new level above that and then update everything down
34:18 below so because I don't have any parent pointers for these Leaf notes here when I'm going back here when I did this split here right I don't have to touch touch any this side of the tree their parent change because they're not pointing to it that's no big deal right now this new the new you know inner node here just has has the pointers down
34:42 below yes question how do you know where to split what do you mean what do you mean by where it's in the middle yeah that's it there's no magic to it okay so delete is basically going to be the reverse of this so same thing I want to Traverse the data structure to I find my leaf node that where I has the entry that I I want to leete if it's not there then and you know then it's negative I I don't do anything if it is there then
35:17 when I remove it if I become less than half full then I I have to merge it or do something to make sure that it's balanced right so the the the the the trick we're going to do is we're going to rely on The Sibling pointers to steal a key from our neighbor if we can so that we become balanced but if taking their you know their key causes them to become unbalanced then I have to
35:44 merge right because if they're if they're exactly half full and I'm exactly half full and I remove a key and if it makes me less than half full and if I take a key from them they become less less than half full then I know I can I can combine the two
35:58 and I do the same thing I did the insert I recursively do merges up up the tree until everything is balanced so yes so why we want the to be why do you want the node to be at least half full uh because you want you want you want to make sure that looking up any key is ASM totically the same no matter what key it
36:21 is all right and because it's it's sorted the data structure will always end up being essentially the same uh no matter how in the no matter what the order we insert them assuming we follow the same protocol deci side with the split key and so forth this will be different than a try Tri dat data structure is going to change depending on the order which we insert keys but we we'll ignore that for now so again this guarantees that any lookup for any key is always going to be log
36:48 in all right so uh we're going delete six again Traverse the root down to list Lea note here we go ahead and delete it now our uh this Leaf note here becomes less than half full right so rather than merging we just go look left and right if whatever have a hipping pointers and find whether we have a neighbor uh that we can steal a key from
37:11 in this case here the the key next to it or sry the the node next to it has three keys so we can go ahead and and steal Nine without doing anything right we're not done now because now since nine was the the guide post here right we have to go look and peek and see whether that did we steal something or actually we would know because that would always be above so now we got to update the guide post to reflect the fact that if any value is is uh equal nine should be over here so all we got to do is just pop up the the the lowest value on this note here which is 12 and then just overwrite it into uh its parent like
37:51 that that's easy let's see a more complicated example say so now we're going to delete 15 here right do a traversal end up in in the leaf node delete 15 now this node is less than half full so we can try to borrow from from a sibling that's fine so we'll go ahead and copy 17 over here right and then now we just have to update the guide post up above and say
38:14 uh that 19 is the the split not 17 that's fine that's easy now if I want to delete 19 I delete you know do the reversal find the leaf node delete 19 now I'm less than half full but now I can't steal a a value from any of my neighbors because they would also become less than half full as
38:37 well so I I have to merge and again the the the different system will do different things of like do do you merge from the left do you merge from the right do you steal from the left steal from the right the high level protocols is the same right different systems do different things but in this case here let's let's merge with our our neighbor on the on the I guess our right right so that we all have to do is kill the guide post up above and then combine these now into a dilute Neath node but now the parent node in the middle is now less than half
39:14 full and we need to then merge it with uh it its neighbor or it's sibling over there so to do this we're going to pull down the root node 13 and then and split it across and combine everything together into a into a new root
39:37 node right so when you do a delete you may end up collapsing reducing the height by at most by one yes so to confirm for borrowing are we only borrowing from like immediately adjacent siblings or like if there's something in the far left that has like three could we borrow all the way from over there so this question is like back here uh when I was had a borrow is it only immediate siblings or could I do
39:59 major surgery rebalancing things way over there you could nobody I don't think anybody does that could be expensive like like you kind of want to be in and out of the tree as quickly as possible and so spending time to go look at oh what could I steal from other than my neighbors immediate neighbors uh it just it just makes makes it longer and slower and you're holding latches while you're in the data structure we're not covering now but just it'll slow everyone down behind
40:26 you yes just making sure I think on one of the previous slides towards the beginning you said like max number of keys isus one but m is like the number uh Max Keys is n minus one uh so yeah so in this case here you would
40:46 have I mean what there's there's four pointers that's the degree and then you have three keys so the number of keys is n minus one the number of pointers coming out is M okay so m is the number
40:58 yes yeah or the degree of coming out yes so I I'll double check the slides if that wasn't clear all right other question about deletes yes uh so go back here why didn't I update from from 19 to 20 uh yeah that might be a
41:21 typo actually no no no all right so good point so question is going back here I 19 right and then I decided to merge and then I I removed that gu there but I didn't update the inter node that's what I've saying before the key
41:38 the key can if we delete a key it definitely cannot exist in the leaf node but it may exist in the root node so in this example here 19 well yeah that's discriminating enough like it's still correct any value less than 19 is on this side any value greater than equal 19 is on that side it's fine leave it alone right you could clean it up but there there's no reason to right still correct and eventually it'll you know if if we if we uh keep splitting the nodes
42:06 maybe gets removed eventually but who cares it's still correct in a b tree you wouldn't have that b plus tree you can yes thir at this stage we still so the question is if I insert 12 so I would come down here n is great 12 is greater than equal to n so it would go here so would
42:45 [Music] F okay so there already is a 12 here and it it points to something else yes we have stolen it from that to put it back to the uh so his question is if say I had another node in between here that had enough of uh enough space that could steal a key I think the rule is because you don't share a parent you don't steal because if you do that then you got to take latches on this and it makes it more
43:21 complicated yes do we do a instead of question in deleting 19 why why would we do a pull down instead of merging The Sibling uh you actually you could merge if you wanted to uh but then it gets weird because now you have like root has one there's at the top of the route there's one node and then the next level there's one node right so you you would
43:50 merge say it's still theoretically correct uh no because actually it would be more than log in because it' be an extra jump to go go find anything you need it's it's one right which I said before constants matter so we don't want to do that
44:19 yes conect no so I'm not showing the simp poins here did I say that the sibling pointers only exist if you um if you share a parent no you have sing pointers all the way across even you don't share parent his example was if I want can I steal from a sibling where we don't share parent I we still have sibling pointers but you would know who your parent
44:48 is know question is uh yeah I said before you you would not maintain your um yeah so question is how do you how do you know that you don't have the same parent uh that's a good question um actually I I don't know what they do then I'm pretty sure you definitely maintain SL points all the way across
45:18 um yeah I don't know how they check that um I mean the most obvious thing would be you you have to maintain the stack of the as you go down so you know that if for your parent to get down there you were the the leftmost child there isn't anybody on the other side so you you don't you don't go look that's the easy thing easiest thing to
45:39 do okay one last question yes yes had I think so I think the example you're saying same he brought up where what if I had a a single node above 13 so then then uh that single node would only point to 13 and and then the other side or I'm not sure saying like you like you can't do that like it has to be balanced
46:24 right so well this tree has shr in height but yeah so we so right here was a was we were looking at AE and would it be possible us to end the question is is it possible to have have one side of the tree sub tree have a shorter height than the other sub tree no it has to be balanced see that case wouldn't
46:55 happen all right last question yes so the you P down you always only you say is your question is do I always check whether I have one sibling and therefore I I can pull down uh how would you like you
47:24 always so so so next class as you start doing the deletes you actually keep track of latches on nodes where you know that you may have to do a merge so you know how far up you may have to merge like as you get to the bottom because you don't as you're tring down you don't know whether the delete the the the leaf note you're going to land on could absorb the delete without having to change everything right so you hold all the latches on everything and then now when you do delete you know how far up you meant you would have to then
47:56 apply the merge okay there's a lot we need to cover um but again it sounds like you guys have the basics of this which is good um again we can go over this over recation for project one or project two if necessary okay
48:13 um trying think what's the most important thing to cover um yeah let's get through this quickly uh all right so in all my examples shown before so far we've talked about like single key attributes like a single single digit uh you know sing Single value but in actuality you can have multiple Keys uh for an index this is called a composite index so my example here I could have a table called XXX and I could make an index on attributes a b and c right and I can declare additional metadata about or what the structure of the data structure look like so I can specify what the sword order is for a given column and that can change by default it's always ascending and then I also specify how where where do I want to put my nulls do I put them always at first I put them at the end I think by default they're always at the end Le in
49:03 post and then now one of the things we can do in a B+ tree if we have a composite index is we can we can do lookups on partial keys if we have a composite index remember I said we couldn't do this in a hash index
49:18 hash index you have to have all the keys because you take all the bytes and you you have to Hash it to figure out where you land in the hash table so if you only have you know one of the two keys the the hash means nothing but in B+ tree we can actually do lookups on uh portions of of of the key so obviously if I have a index on a b and c I do where a equal 1 Bal 2 and CS 3 but I I can do a prefix look up where a equal 1 and b equals two without having C and then in some systems I think only Oracle
49:47 and and SQL Server you can do crazy stuff like just the inner parts of of the key without actually having the prefix I you do b equals 2 and C equals whatever right so visually looks like this so again say I have two two in my Composite Index I have two keys one and two or sorry two two values so I want to look up a key where the pair one two again I just break out the indidual components
50:12 of of the attribute because I know the type of the of the keys because I'm starting that in my catalog because we're we're we're a relational system so then I just do my lookups as if I was looking up on a single key decide where I want to go down on my tree to find the find the data that I want
50:28 if I want to do a prefix look up it's essentially like having a wild card at the end of of the key again think of the keys are just just a bite array but I know where the offsets are I know how to jump to the indidual types so if I only have the the A and the first key and not this not the second again I just treat that as doing the look up on the first part land down in my leaf node now I scan along thanks to Sibling pointers to find the keys uh you know find the rest of the keys that match the predicate that I want
50:57 the last one is a bit more complicated and again only Oracle and SQL Ser do this right so now if I only have part of the key again now I basically have parallel searches going down all possible branches in the tree right now you have multiple threads you got to coordinate that of who's looking at what and so forth and then you find all the matches and then you have a way to consolidate the results later on Oracle calls these skip scans I'm pretty sure they have a patent because it's Oracle
51:21 right and and that's why most systems don't Implement there's a lot more Machinery you need to handle this now you need to handle duplicate keys right I said before you can have a primary key index where the key has to be unique but then you could also have secondary key indexes where it may not be unique right like people have would have multip zip you know multip people are live in the same zip code and if I want to index on zip code I have to be able to handle
51:45 that so there's two ways we can implement this the most common one is that we actually implicitly store as part of the key of the index the record ID and going back to what I just showed about the composite index if now I want to do look up on someone's zip code I just do the prefix look up just with that zip code it's going to find all the entries that with the same zip code even though I don't have the second part I don't have the I don't have the the the record ID and then now the data system
52:14 that's the B+ Street implementation just treats all the keys as unique because they are alternative is to do overflow Leaf nodes and this is where I recognize that I have duplicate keys and I just allow Leaf pages to keep almost like a like the chain hasht I show before to keep having more pages appended to the end of it right which sucks because if I have a skew distribution I may end up with a really long chain and I'm back to doing sequential
52:39 scans so again so for appending the record ID again the key even though I'm showing the key is like 1367 the key really is like this hidden thing where they're keeping track of the record ID all right postest does this but I don't think they even exposed to you you can't get through SQL that it's storing the record ID only if you look look at the page the actual bites you can see that
52:59 so when when I when my SQL query wants to insert six what it's really doing is first inserting the the tupal into a page now I have a record ID with a page number and a slot number and then concatenating that to the key I do my insert and I land uh exactly where I want and now in this case here because there's already a six or some other record ID I just do the split algorithm that we just talked about right to add you know add add new Leaf
53:24 notes so again logically looks like it's the same key but physically they're actually the record ID is in there for over overflow Leaf nodes the idea is that you would recognize uh that I already have the key that I'm trying to insert in my leaf page so then I just extend it out to add another Le page and have a pointer uh down below so forth
53:49 yes his question is do do we just say that the value is also the record ID as well yes so if you're smart you could just recognize oh the record ID that I already have in the key is the value as well and don't don't store it twice I don't know what post
54:03 does yesn't don't the Overflow break absolutely yes so's he statement is he correct doesn't having these overflow nodes break what we just said before about having sequential scan along the leaf nodes absolutely yes I mean some ways that you scal scan this way then you have to know to pop back up but yeah and as I said if you if you insert the same key over and over again now you have this really long overflow chain and that sucks it's it's more management yes how do we
54:38 search this question is how do you search a key when you have uh when you have duplicates if it's the if it's the going back here if it's the record if you pack in the record ID then it's just look prefix search so I have the six I know I need to find the six but I don't know what the record ID that's appended to it so I'll get all of the sixes and get the record ID is out of that if it's the Overflow chain you land to to the leaf node and you say all right well I know the key I'm looking for has to be in this Leaf node so let me follow all
55:06 you know all the the Overflow pointers down below and when I'm done then I know that six can't exist in any other Pages it's the same thing as the chain hash table right so in the chain hash table you hatch it you get a bucket pointer you land that that that that bucket chain and you scan all those pages until you find what you want same thing but instead of having a hash the hash look up at the top it's a it's a B plus
55:32 Tre yes so for overflow lead node in case like an extreme scenario where we have like one really bad key Collision that has like a long overflow lead node doesn't that break the like consistent time I and she's correct doesn't this break the log end guarantee yes I you know what I should have put the thing here don't do this do do the record ID one okay I just want to show you that you could do it there's another you know one way you could do this but don't but
55:59 don't all right clustered index concept and dat systems um and as you said like if we're using a heap file storage the heaps are unsorted right but now I'm maintaining this Heap data structure that's unsorted but I also have this index that's unsorted right and I can do index and organized storage where everything's nicely sorted in my Lea pages but in some database systems you can actually say I I want my heat file to actually be sorted based on some
56:26 index and when you in post you can call the cluster command give it an index on a table and it'll literally rewrite the table to be sorted based on that index it won't maintain it uh forever right if you start inserting new things it'll come out of order but sort of like a one shot one time
56:43 operation right and again the reason why this matters because again we want to maximize the amount of sequential access we have when we're accessing our table so if we have a cluster cluster B plus3 again whether it's one time sorting like in postgress or in index organized Pages if now I want to scan along the leaf nodes when to you know find all the the table pages when I access the pages I know that I'm only going to retrieve them once right because there's no value that could be
57:11 in you know key that that points in here that that could potentially also exist in here as I scan along I have to visit each Leaf page once right if it's unsorted though the index is now going to be sorted on some some sort order and then now my heat file or whatever the the pages are they're completely unsorted
57:32 entirely right so now if I scan along here and my pointers may be going all over the the pages so what happens now now if I'm just blindly scanning through whatever I see that comes out of my index and then go go grabbing the page I'm going to have Random Access so we have a really extreme case where we only have one frame in our buffer pool so just using this example here so this little box here represents every single time I got I have to go read a page that isn't going to be the buffer pool and so rarely do I have two pages that are or two two keys that are pointing to the same page continuous to each other so I'm basically thrashing I'm going in and out of the the the buffer pool going at pages and over and over
58:13 again so really simple optimization uh is to not actually fetch any tupal while we're scanning the index just go get the list of tbls we want then sort them BAS on the page ID now when I scan through and and get all get all the tupal I'm only retrieving each page
58:33 once right postest calls this I think a bit map Heap scan right it'll do a scan on the index get all the pages sort them and then combine them together all right in some cases also too you can actually do this you can get all the page the page IDs from multiple indexes then do intersections on them depending what the wear Clause is and then now you you again now you just have a a s list of the pages you need to
58:58 retrieve all right I want to finish up in the last 20 minutes talking about some optimizations we could do uh and how we actually want to build this thing uh so some of these ideas and techniques going to come from uh this book that came out about 10 years ago called uh modern b b tree techniques so again the the B plus tree paper is 1970 B link is 1981 but they're still writing books about how to make these things work because it's the most important data structure in the world not just in databases right think how crazy it is there's a data structure for databases
59:29 people write a book about right there's no book on red black trees as far as I know there's no book on slri no offense to Danny Slater right it's so important there's a follow-up that just came out last month right more modern B+ Tre techniques right so again this it really is that
59:46 important all right so the first question is what he brought up like how do we decide decide what the size of our nodes going to be and as I said like it's going to be based on what the hardware is so the slower your your data sorry slow the the the device the larger you want your page page size to be for your nodes because when I got to go fetch it I want to maximize sequential access so if it's a really slow disc one megabyte if not larger but it's really fast 52 bytes is actually the right size
1:00:14 so the Enterprise systems like db2 as we talked about when we talk about buffer pools you actually can declare for a given index what buffer pool manager you want to use for you stantially different buffer pool managers and you can specify what size the pages should be so you can say for this index that's on this Perle manager with this page size again depending on uh depending on what you want and if if you know that you're mostly doing point point queries going look up single Keys maybe you want a different size versus doing long long
1:00:44 scans the next question is what should be the merge threshold is as I said in the beginning there's the there's the textbook definition that says I merge when uh I'm less than half full but it may be the case that you're like deleting and inserting really fast over and over again so all you're going to end up be doing is just splitting and merging over and over again like insert a key delete a key andert a key and to avoid that you can relax that constraint
1:01:09 to let something go less than half full so that you don't you know you're not re you're not you're not collapsing that node if some inserts show up then you can fill fill it in if it goes completely empty then yeah merge it
1:01:23 right this is why post again they call it a nonbalanced B plus3 in the code because it's not exactly balanced as the way we talked about before another trick you can also do is you can have different sizes for the leaf nodes than than the inner nodes
1:01:39 right the typically want maybe the inner noes will be a bit larger than Leaf nodes all right because they they're going to see most of the traffic next thing we got to handle is variable length keys so there's a bunch of different ways to do this one way is instead of storing the the the the long keys inside the pages of the the noes themselves you just have a pointer to the tupo like a record ID to to the pointer and then since we already know how to store those in sloted Pages we just use all
1:02:09 that so in in memory databases there was a data structure data structure called tea trees I think T stands for the name of the dude that invented it but if you look at the paper all the the notes look like T's themselves right so that that that was a nice little clever thing that they did do we think this a good idea bad
1:02:31 idea he said he said depends uh I mean yeah he's yes uh like if you're if you're uh if your keys are like one gigabyte sure that's yeah definitely but most keys are not one gigabyte what do I have to do to do a look up I got to go look in a node before I can do any comparison the key there's there's no keys in the nodes I got to get a record ID to go follow the point you know follow that pointer to get that that Tuple then I can pair the key so as I'm traversing down even though if I'm doing binary search the minimum of search we need to do within the inner nodes of of a B+ tree I got to go f fetch a bunch bunch of tubol and that sucks so most systems don't do this even the inmemory systems like oracletimes 10 which originally was using T trees from the 1990s they got all of this and everyone's using B+ trees
1:03:22 now you can have variable length nodes right you can allow a node to the size of node is always to be fixed within uh you know within a given level uh this is only in academic systems it's it's pretty rare because it's a lot more M memory managers to do this right the the right approach would be something like like again db2 you say the buffer pole has this page size and everything inside is the same you can do padding that we talked about uh if I know the max length of the key type then I put a bunch of zeros empty space after after the key so it always nicely aligns
1:03:56 the more common approach is just within the page of the node themselves just like we had that slotted array uh slotted Pages you just have you have a portion of the space where you you store the the um the Vari length keys and in some cases you could have overflow right post allows overflow within a given node
1:04:16 to accommodate this because you want the the number of Keys has to be fixed next question is okay when we land in a node how do we do do that search to decide whether we want to go left or right so the easy thing to do uh is just linear
1:04:33 search right assuming assuming that it's not sorted I start from beginning to end just scan along till I find the key that I want and I'm done you know it's it's simple to do it's easy a better way to do this though if I could take advantage of Modern Hardware is rely on simd does everyone know what simd is who is who here is not who here is taking 48
1:04:56 very few okay does everyone not know not know what simd is single instruction multiple multiple data so in sort of classical programming you think of cyy or like single instruction single data like 1 plus one equals two that's cyy right you take one put in the register take one put another register in single instruction and it gives you two with simd you can rely on the hardware to allow you to take a vector of values and then there's specialized vectorized instructions that do same operation
1:05:26 on all all the values within that Vector so it would use like intrinsics like uh like this for for for x86 arm has the own version of this right and there's libraries that can do this all for you but say I'm looking for eight so I'll put in my Vector register eight four times because these are uh four lanes in here right assuming 30 bit integers and then now within a single instruction I can do a comparison with a vector of four values that I'm looking for and it gives me another output Vector s output register that says 01 whether I have a match so instead of doing that yes I'm doing linear scan looking at individual values but within a single instruction I look at I look at four values or you go ABX 512 I could look at you know significantly
1:06:09 more and then if I don't my match I just scan along and do the same thing again until I find the thing that I want and there's bit shifting operations to pull out the one and identify where it was
1:06:20 right so that'll speed things up that's nice obviously again if it is sorted then we just do binary search right you just jump to the Middle Point look at the key figure out when you go left and right and you just again jump around till you find the thing you're looking for all right that's
1:06:37 straightforward a the fastest way to do this which is only exists in academic papers I don't think anybody actually implements this through interpolation so if you know that the keys don't have any uh missing values in them they're always monotonically increasing then you can just do a simple formula to say for I know that the key has to exist or not exist therefore I know how to just do the math to jump to the offset that has exactly that I
1:07:03 want again I said no systems actually do this it's going to be binary search or the linear search with a simd is be the better way to go all right let me run through quickly uh last set of operations or optimizations you can do so prefix impression is is when you recognize that because the value domain within the index are going to be uh the values that con each other are likely to be very similar same reason why we put things in as a column store that now instead of having disperse values from different attributes within within a table it's all the values for a single attribute are contiguous so if I recognize that I seen the same thing over and over again the same prefix then rather than storing
1:07:41 that that redundant information I just store the prefix separately and then everything else that comes after that is is the suffix so now when I'm doing lookups I know how to look at the prefix as as needed and then only look at the the remaining suffixes if I don't have a match it's sort of like the Delta compression that that we talked about before like the fr the frame of reference
1:08:03 compression for duplication the idea is that if I can recognize that I'm seeing the same key over and over again instead of having to store that key redundantly uh I can just have a the key once followed by maybe the a small number that says here's how many values that that going to occur for it and then followed by those
1:08:23 values right added this two years ago for their B plus trees and it it reduces the size quite significantly right you can actually do same things for for the values as well not just the keys like if I have a bunch of tupos that are all on the same page instead of starting the page same page over and over again I just store it once say all these guys are in the same page with different slot numbers why would there be dupc why would there be duplicate Keys ZIP
1:08:48 code right zip code example we add ID so so St he's correct like did I say you have the record ID to make sure it's Unique so the key is the same the record IDs are different right so isord part of but I'm saying like in the internals of the system we could say I know I'm appending the record ID and therefore if I see the same key the same prefix of the key store that once and then now I just have the record IDs and that's the values so up above in the inter no so I think post up above the inter nodes the
1:09:23 I think you don't do the duplication but for the knows you could do this I do sorry yes a form of the Overflow because it doesn't exay she said is this is this a better form of the Overflow node CU those an extra extra layers yes but like you still may have to have the if you're doing the Overflow method you may still have to have the Overflow
1:09:52 chain right again always thinking like extremely examples I have a billion people there's a you half a billion people in one ZIP code so is this also a bad idea no this so question is this a bad idea this is no this is a good idea because you you could do this for the record ID thing that I talked about before right pitting the record ID because now I can extract out say this is actually the the key here is the true discriminator the thing I care about like the like the zip code and that that's getting repeated but then the the I'm putting the record ID as part of part of that composite key I pull that out that's ESS the value now I'm starting zip code once for all possible values within that the ZIP code this is a win you definitely want
1:10:34 this all right I can do suffix tration for the inner nodes again if I recognize that the most of the time I only need or the keys and the inter noes are pretty unique at least for certain of characters say for a string then I don't need the rest of the string to figure out when whether I need to go left or right so say I have long strings like here right it's the full alphabet
1:10:55 but I only really need the the first letter to figure out whether I need to go left or right I'm showing three letters so I just store that setad of the full thing and then now that's enough for me to figure out when I go right now of course this this may break if someone inserts something that that violates this so that's why I'm I'm storing ABC instead of just a I'm giving myself a little bit little wiggle room in case you know in case something comes along that could have to go left or right or go in between but again I can get away with this because the B+ tree doesn't store the actual key values the true key values in the intern noes so I can store whatever I want in there long as I long as I'm going left or right correctly I don't have to have exactly the key that I have before
1:11:39 yes so this question is he's correct like over time wouldn't the minimum prefix be different and we have to change that I I just update it right again we'll talk about latching next class but like I'm holding the if I need to update an inter node I have to have implicitly latching the the the children nodes because no one can get to the children unless they come through me so therefore I can do I can do whatever change I
1:12:02 want all right this last one is super important pointer swizzling where this is actually going to break sort of the the nice abstraction layers we had in our datab system while page IDs and record IDs and actually store raw memory pointers so if you think about what happens when you do a look up on a B plus Stream So I start with the the root I find key3 and I got to figure out what I'm going to go left and right so I I so
1:12:28 when I'm at the root node I again do that comparison I need to go down this side here but again I have a what is it really page ID so I got to go now to the PO and say Hey I want page two bring that into memory and give me the raw memory pointer in my dress space where I go access it and then now say I get down to the bottom the Lea note here now I'm doing scan along if I got to follow the sing pointer same thing I need to know
1:12:55 what the what the real memory address is for a given logical page ID I go to my buffer pool and ask again so I'm doing this over and over again I'm asking for you know this mapping from page IDs to physical memory addresses over and over again and that's going to cause a bottleneck in my buffer pool so if you recognize that some pages are hot and you're always going back and asking the buffer pool where it actually
1:13:19 is you do what's called pointer swizzling where you actually store the raw memory pointer in the page uh so that when you do that traversal you don't have to go to PO manager so obviously you would want to do this for the root right because everyone you can't go into that stru unless you go through the roote so store that memory pointer somewhere and then you could do this maybe for again for the hot Pages like the the the inner
1:13:42 nodes we need to be careful about this because we're actually storing that that that memory address in the page itself because it's in memory we got to keep it pinned and obviously we need to keep track of that when I flush it write it out the dis that I don't write out the memory address because when I bring that back in that memory address could be completely garbage so a b more bookkeeping we have to do here but we're avoiding having to do that extra lookup
1:14:06 to uh to have to go the buffle manager and obviously I need to know that I I Swizzle little pointer and may there may be different pages pointing to my memory address so I don't want to evict that memory address uh without telling everyone else that it's being evicted so you typically you arrange this in sort of hyal manner that you don't you can't evict anything uh at a uh you can't evict anything unless its parent has been evicted as well like there's there's it's a bit more complicated but this is a huge win we can do this for
1:14:37 other data structures or other parts of the data system as well all right the last one to talk about is do bulk inserts so in some cases you may actually know all the keys ahead of time right so if I call if I if I load my table typically people tell you unless it's a unique constraint where you make sure you don't have any you know Integrity violations you actually want to remove all the the indexes in your table first then bulkload all the data then call create
1:15:04 indexes right because if you incrementally update indexes that's be much slower than calling create index and because you can you actually do that in parallel so if you know all the keys ahead of time what you want to do is presort them and then now just fill out your Leaf nodes with your beautiful sibling
1:15:20 pointers uh and then now instead of building the index from top down you build it from bottom up you build basically the house on top of the foundation here and in some cases too if you recognize that oh this is uh rarely ever going to be updated I don't have to keep it half full or you keep some extra space I just completely fill it up entirely have these Pages completely packed then now my data structure is the most compact that it can
1:15:45 be right so you'll see this when we um uh you you'll see this in some cases when we run queries in some datab systems they actually build the index a build build b+3 for you to run your query and then immediately throw it away in that case they'll sort the data then build the index then use it for that query and then throw it away because it's faster to build the index and use it to run the query versus doing the squential
1:16:12 scan all right actually Li there's one more optimization I want to show you it's related to the log structure so we talk about report so as I just said maintaining the b+3 is expensive if you're doing sort of incrementally because you have the to do these splits and merges right and the worst case scenario could be for you know for one insert I got to basically have to rebalance the whole thing right so what if there was a way that we could absorb
1:16:37 the updates to our B+ tree uh and then only apply them in a batch when we know uh we absolutely have to so this is called a right optimized B+ tree uh the Wikipedia article calls them fractal trees uh there was a guy out of Stony Brook that that invented this sometimes also called B Epsilon trees and it's going to look a lot like the the log structure Mery that we talked about before where you have this buffer you're doing a bunch of Rights and absorb it and then only spill down below when you have to or we saw the same technique before when we talk about my SQL compression scheme because they had this mod log in front of every page where you do bunch of inserts without having to decompress everything so this this concept of log structured is super important we use it for all through uh in our datab system so in a b Upsilon tree or fractal tree we're going to have a mod log for every note so now when we do an insert we just write it into the mod log if we have space without doing that full traversal down to the leaf
1:17:37 nodes right because now that's fast right like we said before the log structure merry was super fast it just append append append to the log in the M table and never have to write out the dis so now if I want to do uh a delete same thing delete 10 I put in my mod block here at the top and I don't actually go to the bottom and actually delete
1:17:58 it right because the idea is that now if anybody wants to do a lookup they're going to start from the top of the rout the Top Root node and they got to look in the mod log to see whether the thing they're looking for has been insert or deleted accordingly and then if it's not in there then they do the Left Right traversal that we we normally do in a B+ stream right so actually going back here
1:18:20 they're looking for 10 so I would find the delete record in mod log for 10 at the the very top even though it's still hanging out on the bottom it's actually in my physical data structure but logically it's been deleted because I have the log entry for it so I can go ahead and stop right there and I'm
1:18:34 done and the reason why it's called a fractal tree because now when we run out of space in our mod log then we sort of apply we're pushing things down accordingly so in this case here if I want to insert 40 I don't have any more space in my mod log so I got to take my entries that are in the mod log of above and push those down so I can put the insert into 40 here and then now you're doing the split left and right you're actually looking at the thing that you modified and deciding should that mod log entry get pushed down to the left or pushed down to the right so in this case here 7 and 10 are less than 20 so it should go down here but then it gets absorbed by the mod log guy below now if this guy was full then this thing get then gets applied recursively down below
1:19:12 but again the idea is that the you know you can do fast updates but and it has all the same complications of the log structure stuff that we saw before so I said before the guy that invented at a Stoney Brook they had a system called called tokut Tech I this Tob was based entirely of out of uh the the fractal trees that got acquired by brona and then I think was called extra DB for my sequel for a while but that eventually died um the SS stsb was a thing out of China I think that's dead too but the probably the most famous one that's using Bon trees now is Splinter DB at a VMware um and in relation to AI we had speak last class they're using they don't heavily advertise it and then there's a new system out of China called chomo that claims they're also using Epson trees so it's way more competent
1:19:57 going a B+ Tre because you have to maintain these mod logs and apply them so forth um but again for right heavy workloads this would be be much faster than a regular P FL tree yes app question when you when would you actually apply the log so when you get to the leaf notes so if this thing had to spill down I would come down here I would insert seven and then delete 10 and say in this case here I'm now less than half full I would then go through the normal b+3 protocol of
1:20:27 rebalance all right so the veneral B plus tree despite being 50 years old is is widely used and it was always the right choice for any database system and then you sprinkle in the stuff from the be link tree that we talked about and the other optimizations and that makes it a uh you know makes them be able to handle anything and this should be if you're building new system from scratch this should be the the first choice I don't care what you read on Hacker News about Skip lists they're terrible right
1:20:54 try are interesting but you can put again you put tries inside of your B+ trees we next class B+ Tre is almost always going to be the right choice for for any database system if you want to do you know this kind of Point quity access so next class we're see how much we can get through uh but I'm going to cover a bunch of different other data structures throughout there skip list we can we mention we'll say why it's a bad idea we'll talk about Bloom filters tries skip uh skip list inverted index and we'll finish up quickly at the end talking about Vector indexes okay all right guys see
1:21:20 you remember the 4:30 today is the uh data Fusion talk M I need something refreshing when I get finished manifesting to cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme in my pants intoxicated lyrics are quicker with a simple Mo licker since I'm mer City Slicker play Waves a pick up RS I create rotate at a r too quick to duplicate feel a breeze at a skate
1:21:46 mik at Fahrenheit when I hold it real tight then I'm in flight then we ignite BL starts to boil I heat up the party let my girl R me my mic down with oil Rec still turn with thir de burn for one man I heat up your brain give it a sun so just cool let the temperature rise to cool it all with s eyes