Hello friends welcome to Gate Smashers In this video I'll explain B-tree introduction part so if we talk about B tree We call this Dynamic multilevel index On multilevel indexing I've already explained a question link of that you'll get in description box Generally in multilevel index what we do In secondary memory has all our data lets say we've number of records We've entered that all in secondary records all data in that memory corresponding to that we'll make an index Types of indexes all I've explained Primary index, clustered and secondary index what is sparse and dense that all you'll get in link at description box introduction part of indexes you'll get there So when we make dense in that For every entry there will be entry in index also and in index we only keep 2 things, key value and pointer Key value meas on which basis I've to search if we take a simple example In you college or university your professor wants to take online detail of you I'm not talking about offline or from register If any online entry has to find in your college or university so what he will use Which key value he'll use either your roll number or registration number because I know it is unique and search on the basis of it will be easy and one is the key value and second is pointer, so that book size won't be much bigger As in starting of book At starting of book you'll get key value means topic name and its corresponding pointer, pointer means page number then you can move to thg that page and see the whole description of that page which is kept in secondary memory so means in a way you've to visualize that this type of architecture we've Sometimes we've alrger size of index We create a multilevel of that also We further make index of index and further make index of that so as levels keep in increasing so inserting in this and deleteing become difficult mean lets say I've inserted any element in secondary memory So I've to change everywhere corresponding to that same if we deleted so corresponding to that we've to delete value so this is bit difficult so to remove that thing or to make it better We use tree data strcuture and in that we specially use balanced tree means B- tree So B-tree is generally used for multilevel indexing means our data is kept as it will but we'll make index of it using tree data struture So now about tree you already know that in tree there is nodes and edges, like we make tree in such way that is called root node and these are all intermediate nodes and these are your leaf node Root, leaf and which comes in between that is intermediate you can say leaf also and that is your route element We enter value in root and connect with edges Cycle is not in this because in graph there is cycle but tree is acyclic Now see here we're using a little different strcuture from tree one is that it is balanced balance means all the elements will be on same level of leaf node and here I can make in such way, so is this a tree Yes it is also tree, but here it is not balanced because in this leaf node is here but there is no leaf node further to this, so this is unblanced because this leaf is on level one and second on is on level 2, so it is not balanced but here there will always balance and no whatever we talk in B-tree In this firstly wr'll talk about nomenclature, means what values we use in this First we use block pointer or you can say tree pointer What is its work ? Which is used in tree Like if we talk, here we've a node means there is a node of tree Which we show in round shape but you can make it like this also because in normal tree we add only one value, like in this node we entered 10 Here you can more values also in a node Multiple values in a single node that node further denotes its child so for this which pointer is used block pointer or tree pointer Like we've used here, further of this root is left children this is denoted by block pointer right children is denoted by block pointer or tree pointer Second hetre we talk about keys Keys meas like I've already told you that on which basis you've to search So that searching creteria is key Where we'll enter keys We'll enter keys in this nodes We can add multiple keys,Single key we add for sure but we can add more than 1 keys To corresponding to that key data pointer will be there or you can say record pointers what is the use of that Like if I make node like this and in this node lets say I've added element 10 so now corresonding to 10 there will be one record pointer what that record pointer is doing where that record pointer in secondary memory kept Here I'm only getting 10 ass a key means roll number 10 but corresponding to that roll number, name, father name, mother name, address gender, marks mobile number and all, where this whole information is kept that is in records of secondary memory so this record pointer actully point h So here first important point is Record pointer will be equal to total keys obviisuly According to every key there will be a record pointer which will point actually data in secondary memory Same lets say I added 20 So 20 corresponding record pointer which will point in such way but if we talk about block pointer So block pointer is depending on what, it is depending upon how many children there are in node Total children will be equal to block pointer simple architechure it have So see story starts with order this is given to you in such way that order of B tree is P order of B-tree is P So what is the order order is equal to maximum number of clhidren maximum number of children a node can have maximum number of children a node can have that is called your order So see lets say if order 4 is given to you lets say if order 4 is given to you So what you can find according to this if order is 4 So here you keep remember this table that Root That in root how many maximum , this is showing children That how many maximun children it can have In root maximum children can be p and minimum children will be P Intermediate node means whether it is inbetween node or leaf node its maximum children can be P and minimum can be P/2 ceiling value So remember that how many maximum and minumim children intermediate node can have and root node it is P and 2 and if you here value given is 4 Value is given that order of B tree is 4 Si if order of B tree is 4 so maximum number of children So how many maximun children it can have So maximum number of children will be P that is your root node, so maximum children can be 4 and minimum can be 2 if maximum can be 4, so you can make in such way see this This is children one this is children 2 this is 3 and this is children 4 Maximum 4 children we can make so obviosuly who is denotingevery chidlren Block pointer is representing so block pointer will be equal to total order so if order P is given to you So block pointer will also be equal to p if you're taking maximum value so obviously we'll take maximum because we wish to make maximum to maximum and put the data Next if we talk about the key If value is given to you and P is the order so how many P values it can have Total keys can be P-1 How many total keys can come it is P-1 and how many record pointer there will be so obviously as I've told already record pointer is equal to keys So record pointer will be P-1 and keys will be P-1 So what I've written in this question that how much is the order it is 4 So maximum 4 children there can C1, C2, C3, C4 and keys will be 1, 2, 3 and block pointer coresponding to that Record pointer 1,2,3 Always remember that we insert key in this in sorted order lets say data is given to 10, 20, 30 So you've to do like 10, 20, 30 is this sorted way only we insert the data because it follow binary search property and if we talk about here this is your record pointer that is pointing towards secondary memory and this is also record pointer and your block pointers we use in B tree So block pointer in tree point total number of children Record pointerpoints in secondary memory where actually data is presented and key value shows you Key value is showing you that on which base you've to search means what is the searching crerteria for your search that is called key so like this way insert data So on this question can come that what is the therotical value of three all these basic level question can be asked form you thank you