The Gateway to Computer Science Excellence

0 votes

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?

0

order of node= number of keys present

right?

B tree of order $\Theta$ means there are $\Theta$ to $2.\Theta$ 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;

0

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

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?

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

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??

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,061 comments

104,695 users