search
Log In
0 votes
330 views

Consider a $B^+$ tree , in which order of internal nodes is 4 and order of leaf nodes is 3. The order of internal nodes is the maximum number of tree pointers in each internal node and the order of leaf node is the maximum number of data items that can be stored in each node.

Keys are inserted into following order

$50,15,30,40,35,20,8,10,5$

The maximum number of times nodes would split up is?

I did in below way and I got 3 splits, assuming B+ tree with left biasing.

But the answer is given to be 8. Have I made any mistake?

in Databases 330 views
0
not finding any error
0
order of node=  number of keys present

right?

B tree of order $\Theta$ means there are $\Theta$ to $2.\Theta$ keys present
0

See here

 if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children;

https://en.wikipedia.org/wiki/B%2B_tree 

0

@srestha 

order of node is not the number of keys present...order of node is a number of child pointers it has...

0

@srestha-Yeah it is indirectly stating that only that for  a internal node of a $B^+$ tree having order 'p', it contains $\lceil p/2 \rceil$ to $p$ tree pointers.

The order of internal node of a $B^{+}$ tree is always specified in terms of the number of tree pointers and the for the leaf node it is specified by the number of data records values it can hold.

Have I committed any mistake here in insertion?

0

@Akash 

plz check wiki

@Ayush Upadhyaya

you breaks leaf node, when maximum $4$ keys present in leaf

but leaf node should break when there are $5$ keys in leaf

because it can hold maximum $4$ node

right?

0

@srestha-Yes because the order of the leaf nodes is 3. Means it can hold maximum 3 (key,record) pairs before it overflows.

Don't get confused srestha.In simple terms, here both internal nodes and leaf nodes can hold a maximum of 3 keys only.

0
oh yes,

that means maximum key in leaf node=3

maximum key for internal node is 4

right?

really some confusion was there

(ur diagram max key of internal node is 3, but need to be 4)

right?
0

@srestha-No.Again you are getting confused. Read the question again, it mentioned what order for leaf and order for non-leaf stands for.

If maximum 'p' pointers you can accomodate in internal node then maximum p-1 keys you can accomodate in the same internal node.

0

@Ayush Upadhyaya

chk tis https://gateoverflow.in/1330/gate2009-44

and another point

See this definition

The order of internal nodes is the maximum number of tree pointers in each internal node and the order of leaf node is the maximum number of data items that can be stored in each node.

why such a definition is there for order. Means in internal node why donot we take keys as order? I mean why two different kind of definition for order in $B^{+}$ tree?? One taking pointer and another one key??

0

@srestha-Because all the keys are stored in leaf nodes in B+ tree.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
125 views
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?
asked Jan 9, 2019 in Databases bts1jimin 125 views
1 vote
2 answers
2
352 views
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?
asked Nov 23, 2018 in Databases aditi19 352 views
0 votes
1 answer
3
1.9k views asked Aug 24, 2018 in Databases Vishnathan 1.9k views
1 vote
1 answer
4
555 views
Which of the following statement true about B tree and B+ tree index? Assume order of B tree node same as order of B+ tree node. A. B tree index has more levels than B+ tree index for large number of keys. B. B+ tree index has more levels than B tree ... + tree best for sequential access of records. D. B+ tree index nodes more than B+ tree for large number of keys. Please Explain every Point.
asked May 12, 2018 in Databases Na462 555 views
...