MADE EASY TEST SERIES

Question

The following key values are inserted into a B⁺ tree in which order of the internal nodes is 4 and that of the leaf nodes is 3, in the sequence given below. The order of the internal nodes is the maximum number of tree pointers in each node and the order of the leaf nodes is the maximum number of data items that can be stored in it. The B⁺ tree is initially empty: 50,15,30,40,35,20,8,10,5

The maximum number of times nodes would get split up as a result of these insertions is___?

Comments

Answer is given as 8. But I am getting answer as 3. How to solve this question?

---

you are  right.

answer is 3 already either we use left biasing or right biasing.  can you tell the question number and test number and name in ME test series

---

SINGLE SUBJECT- DATABASE(2019) question number 31

---

the minimum number of keys that can be present in the leaf node is ceil((3+1)/2)-1=1 key.. am i right?

---

minimum number of <keys ,pointer> pair that are present in leaf node should be ceil (O(leaf)/2). i.e. 2

---

For a leaf node, its order is defined as the number of pointers in the leaf node which includes both record pointers as well as one block pointer. But here number of <key,pointer pairs> are given as 3. So order of a leaf node(as per definition) should be 4. Hence minimum number of pointers should be ceil(4/2)=2 and so minimum number of keys should be 2-1=1. Where am i going wrong? Would you please clarify this?

---

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

 

The order, or branching factor, b of a B+ tree measures the capacity of nodes (i.e., the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as  m, is constrained for internal nodes so that . The root is an exception: it is allowed to have as few as two children.^[1] For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children, but are constrained so that the number of keys must be at least  and at most . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary and at most  .

---

So that means if order n of a leaf node is defined as the number of pointers per node, then the minimum number of pointers should be ceil(n/2) and the minimum number of keys should be ceil(n/2)-1.

If order n of a leaf node is defined as the number of <key,pointer> pairs per node, then minimum number of <key,pointer> pairs that can be present in the leaf node= ceil(n/2) and minimum number of pointers(including record pointers and block pointers) that can be present in the leaf node is ceil(n/2)+1.

Am i right?

---

but in question it is explicitly defined order is in terms of maximum data values present i.e. max (k,ptr) pairs present .

so analyze the question in that way

---

Ya i got that point. But suppose that in the question it was given that order of leaf node is defined as maximum number of pointers per node. Then is this correct?

" if order n of a leaf node is defined as the number of pointers per node, then the minimum number of pointers should be ceil(n/2) and the minimum number of keys should be ceil(n/2)-1. "

---

Ya i got that point. But suppose that in the question it was given that order of leaf node is defined as maximum number of pointers per node. Then is this correct?
 

O(new)=O(leaf)-1

then you have to subtract 1 from the order. that will give you the number of record pointer which in turn will give you the <key, ptr> pairs.  

after above step min nu of <k,ptr> pairs will be ceil(O(new)/2)

---

wouldn't ceil(n/2)-1 give the same result as ceil((O(leaf)-1)/2) where n=O(leaf)???

---

take O(leaf) as any even number. then u wil see the difference

---

ok..got it..thanks :)

---

Hmm answer is 3

---

i am getting 4 and i think 4  should be correct.

 3 is not correct, according to me

---

Gate Fever

I am getting answer as 8. How are u getting 4?

---

8??

but in the previous comments u all are saying its 3

---

Ya..but I dont think its right..Maybe at that time I miscounted on the number of splits. I just calculated it now, Its coming as 8. How are you getting it as 4?

---

@Somoshree Datta 5

splits:-

1) while inserting 40

2)while inserting 8

3)while inserting 10

4)while inserting 5

 

---

Gate Fever

Maximum number of splits will occur when u follow left biasing with right median as here the keys are not coming in an ordered way, i.e. keys are not decreasing or increasing.

1st leaf node split: insertion of 40

2nd  leaf node split: insertion of  35

3rd leaf node split: insertion of  20

4th leaf node split and 5th internal node split : insertion of 8

6th  leaf node split: insertion of 10

7th split leaf node split and 8th internal node split: insertion of 5

So total number of splits=8