reset password
Author Message
raylongma1018
Posts: 81
Posted 19:40 Jul 08, 2015 |

i don't understand solution to problem4 

why do we split the 76,79,82,90? when inserting key 53?

isn't the max key is 5 so we get the minimun degree 2t-1 =5 so t= 3?

so if we follow the algorithm from book if the node is root and it is full then it will split but the node contain 76,79,82,90 is not the root node it won't split until it is full and it will split until there is node that will insert to that node. 

if we check the book from page 498 this case is really similar as insert B which will not split when the leaf node become full. 

I just need to know why the solution work differently from book? I am very confused

raylongma1018
Posts: 81
Posted 20:00 Jul 08, 2015 |

i try to do some research on algorithm of B-tree, surprising there are many different versions of B-tree algorithm, some of the B-tree algorithm work differently as from the book, one of B-tree algorithm will split the leaf node or internal it becomes full, it will split no matter any other nodes will insert into that leaf nodes, and that B-tree algorithm works exactly the same as the solution we have. But we are using textbook as reference , and the textbook does not work on this way. When I read the algorithm it will not split the node until there is a key inserted into a full leaf. I believe the solution is probably wrong, maybe the problem is collected from some other website using different B-tree algorithm. 

vsevak
Posts: 18
Posted 20:01 Jul 08, 2015 |

Even i have the same doubt. given minimum order is 3. so maximum allowed key is 5. and in given example there were 4 keys.

so without splitting parent node we can directly add key into child node and i did the same and got wrong.

Please explain.

raylongma1018
Posts: 81
Posted 20:06 Jul 08, 2015 |

also for problem 1 is not a fair question because most of topic are not covered yet and some of topics are from later chapters, 

raylongma1018
Posts: 81
Posted 20:08 Jul 08, 2015 |

i mean problem 1 for chapter 16 set 1

 

pchavda
Posts: 12
Posted 20:09 Jul 08, 2015 |

as t = 3 , t2-1 that is 5 so we can insert maximun 5 elements in a node.

As it was nonfull node as stated in book, i have directly inserted 53 key in the beginning of second child.

So i also want to know the proper solution of this problem to get a better understanding of the topic.

Thanks.  

nahmed5
Posts: 57
Posted 22:18 Jul 08, 2015 |
Hi! There are many versions of B-tree. So, the solution provided for this one is correct. However, if you guys have followed the book then it will be correct too. So, no mark will be deducted if you have followed the book. However, to avoid confusion in the future, we will only follow the book's method. So for midterm please do follow the book.
pchavda
Posts: 12
Posted 22:21 Jul 08, 2015 |

Thanks

vsevak
Posts: 18
Posted 22:21 Jul 08, 2015 |

Thanks Nishat :)

 

savanes5
Posts: 8
Posted 22:47 Jul 08, 2015 |

If t=3, the solution provided is incorrect.