And today the topic of discussion is B plus three and this is going to be our first video on B plus three because we'll
understand few things on B plus three. That is how to insert element in B plus three
how to delete the element from B plus three. But now the most important part is what is B plus three
And if we have already studied B three, then what is B plus three now
And there is a lot of confusion. So let's remove those confusion and I'll make you expert in B plus three
Let's start with B plus three. So uh what the theory is saying that in order to implement dynamic multilevel indexing B three
and B plus three are generally used. So for no, for creating multilevel indexing
what is indexing? So what is indexing if I already, I've already told you if you have uh seen a book
you have all seen a book in a book. There are few pages for index
No suppose you are, you want to study bubble chart. So you go and index and you see bubble sort where you see page number
three and you open the page number three. Similarly. So this this three is called this
this this page and this entry is called what index? Fine. So for creating this index
we use B three but for creating multi level index, so let's let's see what is multi level index
So let's click on multi level index. So this is the multi level index and now let's understand what it is all about
Suppose my book is having 500 pages that is from 12345 and 500 pages
And in page number one, these are entries, these are supposed data of page number one
this is the data of page number two. This is the data of page number five
And suppose the last page is 500. This is data of page number 500
So first of all, so I suppose this is book. So the beginning of book has a page
some few pages which contains index fine index and index contain. So now if you see this is index index
of a book. So suppose this is one index first index. And suppose this is uh suppose I am saying I want to study link
list fine. So link list is in page number two. So where I'll go in page number two and I'll this is supposed link list
This is the date of link list. I'll study. Suppose next time I thought to study uh MERS shot
So in index number three. I'm having a mer shot and Meho after that page number is written and suppose page number is four
So I'll simply go to the page number four and I'll, I'll, I'll read my chart similarly
You have an index. So what is the use of index? Let's see if
suppose there is no index in your book. I'm, I'm giving you an example
I'm I'm saying, suppose there is no index in your book. Suppose there is no index in your book
And I told you to find out bubble sort. Will that be possible for you to find out bubble sort
No, it will become very tough. It is possible it is possible to find bubble sort but it will take a lot of time
it will take a lot of time because you never know out of 500 which pages having bubble shot
So you will keep on searching bubble sort every time but having index having index
So index uh suppose index in index, you have to search where the bubble sort is
So it will in index, you will have to search where the bubble sort is. Suppose here is bubble sort
So you have taken some time to search but after that, your search become very easy
So using index, your searching time become very smart, your searching time becomes very smart
But what if? But what if this index grows so high if this index grows so high
So what we actually do we create one more index of our index
we create one more index of our index that will help me finding index and that index will help me finding data
That index will help me finding data. So this representation is actually a multilevel indexing
So actually this is nothing, this is actually A B three. So if I have already
if you remember B three, if you remember B three, we have created some B three like this 259
I'm not just talking of B plus three, I'm talking of B three on it. So these are what
These are indexes, these are actually indexes to some data pointer and these are what child
Now again, child have some indexes and again, some data pointers similarly
So, so this is called multilevel index. And so the highest index
the highest index of index is called root node. These are called internal node and this is called leaf node
This is called leaf node where data is fine. OK? Where data is
But so this is, this is actually multilevel indexing. So uh let's go back and see in order to implement that multilevel indexing B three
and B plus three is used. So now things are clear are generally used fine
That's fine if things are used the drawback of B three used for indexing
However, is that it stored data point. Not if I see the structure before
When I told you when I have explained B three. I've just created this structure only where I've just inserted nodes
I've just inserted node. I haven't told you about what is actual structure of B three today
I'm going to tell you the actual structure of B tree. So if suppose this is the node
then this will keep the informa this place will keep the information of child
And this is key key is that which value you want to find
And this is data pointer. This is what data pointer. This is what data pointer where that data is
That is suppose you want to search link list, link list. Then this is actually the pointer that where that link list is in in
block, in block, which block that is in hard disk, which block
that link list is because here we do not have pages. Here we have a block no fine
So this contains the data pointer again, what will happen again? What will happen again
Uh Information of child will come? OK. OK. I'm so sorry. Again
the information of child will come child pointer again, key value, data pointer again
child information, again, key value, data pointer and child will come. So if I see the structure of B three B
three, I'm talking of B three, I'm not talking of B plus three. If I see the structure of a node of B three
every node has child pointer, key value data pointer, every node, every node has
So the drawback of B three used for indexing. However, is that its stored data pointer
What is data pointer a pointer to the disk file? That is what I told you block containing the key value file
OK? You're responding to a particular key value fine. OK. That is if I want to search link list
then where that link list is at which data point fine along with the key value to the node of the B three
That is, that is what I already told you that if, if I want to search link list that at which location this link list
is. So there you will find a link list that is key value and data according to that link is fine
OK. So this is fine. Then what is drawback this technique? This is the drawback
This technique greatly reduces number of entry. Why? Because for every note
I have to keep this data pointer for let me change the color. Oh my God
Let me change the color. If for every, for every entry, I have to keep this data pointer data pointer
data pointer that this technique greatly reduces the number of entries that can be packed into a node
Because node is having so much of data, it is having information of key also that is index pointer
Also data pointer also of A B three thereby contribute increase in number of levels
Since if the size of node will become high, then definitely these levels
these levels will become high because our node will not be able to contain much value if the node cannot contain much value
Definitely, in that case, I have to increase the size because it is inversely proportional
If a node can contain more number of elements, then definitely heart will no heart will be less since note is high pack
So level increases, this will increase the number of level in the B three
Hence increase in the first time of a record. So what is the drawback of B three is that every node contain information of data
pointer, information of data pointer because of that size of node increases and level increases and if the level is increasing
so our first time will increase. So in order to remove this drawback
a new concept came B plus three. So what B plus three told that instead of keeping what B plus three told that instead of
keeping data pointer at every node, try to keep data pointer only at only and only at leaf notte
Now listen to me very carefully what B plus told. Instead of keeping data pointer at every note
try to keep data pointer only at leaf node that is leaf notte will contain all the elements of a tree fine and upper node
will only contain information of child and key, upper node will only internal node will only contain information of child and key that is if
I say if I say B plus three, so this is the structure of B tree
This is the structure of B tree node. Now if I make the structure of B plus three node
if I make the structure of B plus three node, there will be two structures one for internal node
So if I show you internal node, internal node will have only child pointer
key, child pointer, key, child pointer key and child pointer. So this is what reducing the size of
my node. A node can contain now more values. But if I talk about child pointer
since I know what is child, what is leaf node? What is leaf node
What is I'm I'm talking about to keep data only at leaf node
I'm sorry if I use as child uh what B plus three told, try to keep data only at lea notte if I say leave
note, what is leaf notte? We do not have a child. So if there is no child, why to keep information of child pointer
why to keep information of child pointer? So I'll keep the information of key and data pointer
I'll keep the information of key and data pointer. I'll keep the information of key and data pointer
So this will be the, this will be the leaf node structure
So in B plus three, there are two kinds of structures. One is of internal nodes and one is of leaf node fine
So this is actually the difference between B three and B plus three. Since since now
the internal nodes can contain more values. Because of this, our level will decrease and certain level will decrease
our search time will decrease fine. OK. So this is the main
main profit of using the main profit of using what B plus three
So if I see show you the B three, if I show you the B three, I just told you every note contain what child
pointer, key value and data pointer. This, this, this is what data pointer
So every node, then you will see the structure of every node. It is same. It is the structure of every node or straight
This is the structure of B three. Now this is the drawback. So how I have removed in B plus three
So I will not now read all those things. I've already told you what uh what
what B plus three is all about. So in B plus plus three, in if I
this is called internal load, so what is in, I've already shown internal load only will keep the uh well child information
key value, child information, uh key value, child information, key value, child information
So these are the child fine. OK. So this is what, this is what this is what actually what key value
fine key value and child internal load and external load will only have two value
key value data pointer there will be no child pointer, key value
data pointer, key value, data pointer fine. And all those leave node will be connected with a link list
Now there will be a link kind of link with every node fine. So if I show you the structure of B plus three
if I show you the structure of B plus three, this is the structure of B plus three where this node
this internal node is only having internal node is having key value and what child pointer
So this is child pointer but leave node is having what key value
And data pointer, key value and data pointer. And this is connected with other leaf by link list fine so that you can traverse all
the leaf because all the data in B plus three, all the data is present at leaf node
All the data is present at leaf node. While in B three data is scattered in B three data is scattered
It is somewhere in internal node also in leaf node also. But in B plus three
all the data of a tree is you can find at leaf node also some data in internal lode fine
So why internal lode if I show you the structure, the, the right child of three is having three and four
So this is what B three is that in uh B plus three? In B three
we have discussed that if I this is five, this is nine
all those elements will come here will be less than +54 and suppose four and three and four here
less than greater than five, greater than five and less than nine. That is suppose +67 and eight here greater than nine
that is 10 and 11. But in B plus three, this, the left child of a key will always be less than
but right child will be greater than an equal to, will be greater than an equal to
Because of this right child is greater than and equal to. If you see the right child of five
the five left child of five is always less than, but right child of five is greater than and equal to equal two will also
be there. So what is the benefit of B three? Is that what is the benefit of B plus three
You can sequentially travel the leaf node and you will find all the data
you can sequentially travel all the node and you can find the data fine. But in B plus three
you have to travel all the node you have to travel. If I see the structure of B three
if I see the structure of B two, this is the structure. If I have to find five
I have to go up if I have to find six. But in B plus three, every element
you can search it at every element, you can search it at where leave
not fine. So this is what uh B plus three is all about. Now see the very important difference between B plus three and B
three. You can consider it as a property also. So what is B plus three such key can be repeated
You have seen that three was at leaf node also. Three was at internal node also
But if I say B three search key cannot be red. You can you have seen that all the
all the elements are different in leaf node and internal node fine. OK. Data is only saved on leaf node
This is what I told you in B plus three data is only saved at leaf node
Both leaf node and internal node can store data. But in B three B three data can be either in internal node also and and
mode also that both the nodes are responsible. Data is stored on the leaf node makes the search more accurate and faster
This is what the benefit of B plus three because all the data is at leaf node and all the leaf node are connected with
link list, not having a link fine. So what will happen? It will become easy for you to search
you can sequentially search searching is slow because data is stored on leaf node and internal lode because data is there in internal node also
it could be on leaf node also. So you have to search all the node deletion is not difficult and element is only removed from
leaf mode since all the data in B three, B plus three is present at leaf node
So it is very easy to delete element from no B plus three
But as I've already discussed B three deletion. If you have not seen my video
you can see that I took two videos. It took two videos for me to know to show you the deletion in B three
So you can imagine that 17 minute, a single video was of 17 minutes
It took me 34 minutes to explain you how to delete element from B three
So in deletion in B three is very tough process, time consuming link
leaf notes made such efficient and quick because all the leaf node are linked
So it make our searching very efficient and quick. You cannot link the leaf node here
There is no linking in the leaf node. So this is all about B plus three
So I I try, I say thank you so much for watching Java T Point
Please like subscribe and share the channel. Thank you. Thank you so much. Thank you