GATE Overflow | Mock GATE | Test 1 | Question: 27

Question

Which of the following statements is incorrect with respect to B-tree and B+ trees?

• A. Deletion operation is easier in B-tree but complex in case of B+ trees.
  
• B. In B+ trees, data records are stored only in the leaf nodes but in B trees data records are stored both in leaf and internal nodes.
  
• C. Search keys are repeated in case of B+ trees but not in case of B trees.
  
• D. Searching is faster in B+ trees compared to B trees

Comments

https://en.m.wikipedia.org/wiki/B-tree

In cormen also you can see the deletion process and analyse why it is complex.

Watch out for few nptel lectures on this topic if possible.

---

Data record is only key or Key+pointer to record/block

@shreyansh jain

Searching in B+ trees is faster because in B+ trees as we are storing record pointers in leaves only so in internal nodes fanout will be more hence height will be less hence searching time is less

---

the difference in height is a mere constant and doesn't affect time complexity much

Answer 1

A is an incorrect statement.

1. In a B tree search keys and data stored in internal or leaf nodes. But in B+-tree data store only leaf nodes.

2. Searching any data in a B+ tree is very easy because all data are found in leaf nodes. Searching a B tree requires a full traversal.

3. In a B tree, data may be found in leaf nodes or internal nodes. Deletion of internal nodes is very complicated. In a B+ tree, data is only found in leaf nodes. Deletion of leaf nodes is easy.

4. Insertion in B tree is more complicated than B+ tree.

5. B+ trees store redundant search key but B tree has no redundant value.

6. In a B+ tree, leaf nodes data are ordered as a sequential linked list but in B tree the leaf node cannot be stored using a linked list. Many database systems' implementations prefer the structural simplicity of a B+ tree.

Refer: https://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees