The Gateway to Computer Science Excellence
0 votes
141 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 by Boss (29k points) | 141 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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,061 comments
104,695 users