GATE Overflow Test Series | Databases | Test 1 | Question: 3

Question

Which of the following statements is/are correct? (Mark all the appropriate options)

• A. In a $B^+$ Tree, the structure of leaf nodes differs from the structure of internal nodes
• B. In a $B^+$ Tree, some search field values from the leaf nodes are repeated in the internal nodes to guide the search
• C. In a $B^{+}$ Tree, all non-root nodes are at least half full
• D. In a $B^{+}$ Tree, every key value exist at the leaf level

Answer 1

These are the properties of a $B^{+}$ tree. In a $B^{+}$Tree, data pointers are stored only at the leaf nodes; hence, the structure of leaf nodes differs from the structure of internal nodes. Since, all data pointers are at the leaf level every key value must exist at the leaf level.

So, the correct answer is $A;B;C;D.$

PS: For option C, in a $B^+$ tree of order $p,$ an internal node can have maximum $p$ children but minimum it must have $\lceil p/2 \rceil$ children.

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

Comments

@gatecse

In B+ tree all non-root nodes have keys atleast ceil(p/2)-1.How is it atleast half full.It would be if it was ceil(p/2).

every key value exist at leaf level menas, key vale doesn’t exist on non-leaf ??

---

Exactly the doubt I have about this.

---

For internal nodes in a B+ tree the node capacity refers to the number of “links” and hence the number of children it is having – not the “keys”.

---

in option D, is key-value referring to record pointer?