B+ Tree

Question

Which of the following statement true about B tree and B⁺ tree index? Assume order of B tree node same as order of B⁺ tree node.

A. B tree index has more levels than B⁺ tree index for large number of keys.

B. B⁺ tree index has more levels than B tree index for large number of keys.

C. Both B tree B⁺ tree best for sequential access of records.

D. B⁺ tree index nodes more than B⁺ tree for large number of keys.

Please Explain every Point.

Answer 1

Since Order of  B tree node same as order of B⁺ tree node. (Order must have been defined though) but Let's assume the conventional and most widely used definition of Order (Number of Node/Child Pointers) Then It means, In One Block (Node) we can put same number of Keys in both B-tree as well as B⁺ Tree. Now Because In B Tree, One key is put into One Node only which is not the case in  B+ Tree ( All the Keys are also  available at the bottom level ), B⁺ tree index has more levels than B tree index for large number of keys. So, From this We can even infer that B⁺ tree index nodes are more than B tree for large number of keys.

---

 B⁺ tree is best suited for sequential access of records Because All the keys are present at the bottom level with Each Node pointing to the next node in the bottom level.

---

P.S. : This is One Basis of Comparison. There are other situations in which you would get better results for B⁺ Tree Like When the Node/Block Size is same etc.

Comments

@Deepak

In B+ tree order of leaf node is p and order of internal node should be p+1

right?

https://gateoverflow.in/220853/made-easy-doubt-3

this question is not correct

See once

---

@deepak sir if we see the time complexity for search in $b^+$tree and b tree it is $log_pn$ where n is no. Of search keys and p is order now in $b^+$ tree as there can be large no  Ofkeys in comparison to b tree and hence order of $b^+ $tree would be more so tree should grow breadth wise more compare to depth wise so first option should be come  that b tree index has more level than  B⁺ tree index

Please correct me if i am wrong

---

Well explained @Deepakk Poonia (Dee) sir Thanks a lot .

---

Hii @Deepak Poonia Sir,

Is It even possible to have an order of nodes the same in the b tree and b+ tree while keeping the node(block size) size same??

---

```

B+ tree index has more levels than B tree index for large number of keys. So, From this We can even infer that B+ tree index nodes are more than B tree for large number of keys.

```

I think this line should be B tree index has more levels than B+ tree for large number of keys. As more number of entries can be inserted in a single level due to no record pointer for internal nodes. same for B+ tree index nodes are more than B tree for large number of keys.