edited by
1,851 views
1 votes
1 votes

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.

  • B tree index has more levels than B+ tree index for large number of keys.
  • B+ tree index has more levels than B tree index for large number of keys.
  • Both B tree B+ tree best for sequential access of records.
  • B+ tree index nodes more than B tree for large number of keys

I think a is correct but the given ans is b

edited by

3 Answers

3 votes
3 votes

Option B,D are correct. 

I'll write BT and B+T in place of B-Tree and B+ Tree respectively.

Given that $Order$ of B-Tree (BT) and B+-Tree(B+T) node is Same. Since Order is same, in each node we can have same "maximum number" of keys in both BT and B+T index. So, It is quite intuitive that B+T index will have more levels than BT index when number of keys to be inserted is large enough because in B+T we have repetition of keys since we have All the keys that are stored in internal levels, are also stored in leaf levels. Whereas in BT, we have ALL the keys(records) distributed over all the levels and no repetition of keys. 

So, It is quite intuitive that If the Order is same for BT and B+T Node then For large number of Keys(Records), we need More nodes and hence more levels in B+T than in BT.

That was intuitive argument But we can also support this argument using some example.


Say, I want to insert $3120$ Keys(Records) in BT and B+T. And say The Order of both BT and B+T is 5.


For B-Tree :

Order is 5, So, root node can have $[1,4] keys$ and $[2,5]$ Tree/Node/Block pointers. And All the remaining internal nodes can have $[2,4] Keys$ and hence, $[3,5] $ Tree pointers. And leaf nodes can have $[2,4] keys$ and All the tree pointers of leaf nodes are set to NULL. So, 

Now, For B-T we need At Least 5 levels i.e. in 5 levels we can store 3120 Keys. 

In Order to store 3120 Keys in minimum number of levels possible, we need to fill each node as full as possible. So, each node at each level should be filled with 4 keys. 

First level : 1 Node ,  4 Keys, 5 tree pointers

2nd level : 5 Nodes, $5 \times 4$ keys, $5 \times 5$ tree pointers

3rd level : 25 Nodes, $25 \times 4$ keys, $25 \times 5$ tree pointers

4th level : 125 Nodes, $125 \times 4$ keys, $125 \times 5$ tree pointers

5th level : 625 Nodes, $625 \times 4$ keys. 

So, Total Keys in all levels are 3120. So, we can say that If we want to store 3120 Keys in BT with order 5 such that we get minimum number of levels then we will need 5 levels and total 780 Nodes. 


For B+ - Tree :

Let me define the Order of B+ tree as following : ( http://user.ceng.metu.edu.tr/~karagoz/ceng302/302-B+tree-ind-hash.pdf )

B+ Tree is constructed by parameter/Order $P$ ( Maximum Number of Pointers in each Node ) 

• Each Node (except root) has $\left \lceil P/2 \right \rceil$ to P pointers.

• Each Node (except root) has $\left \lceil P/2 \right \rceil$ -1 to P-1 search-key values.

So, Using the above definition of Order,

Order is 5, So, root node can have $[1,4] keys$ and $[2,5]$ Tree/Node/Block pointers. And All the remaining internal nodes can have $[2,4] Keys$ and hence, $[3,5] $ Tree pointers. And leaf nodes can have $[2,4] keys$. So, 

In Order to store 3120 Keys in minimum number of levels possible, we need to fill each node as full as possible. So, each node at each level should be filled with 4 keys.

Since B+ Trees have ALL the keys(records) at the leaf level, we can construct B+ Tree in Bottom-Up fashion. 

Last Level (Leaf level) : 3120 Keys, So $\left \lceil 3120/4 = 780 \right \rceil$*  Nodes are required at leaf level such that all are fully filled so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

$*$ : divided by 4 because we are distributing Keys in the nodes as maximum as possible. 

Now that we have 780 nodes at leaf level, it means that we need 780 tree pointers at second last level. So,

2nd last level : 780 Pointers, So $\left \lceil 780/5 = 156 \right \rceil$*  Nodes are required at this level such that all are as fully filled as possible so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

$*$ : divided by 5 because we are distributing Pointers in the nodes as maximum as possible. 

Now that we have 156 nodes at 2nd last level, it means that we need 156 tree pointers at 3rd last level. So,

3rd last level : 156 Pointers, So $\left \lceil 156/5 = 32 \right \rceil$  Nodes are required at this level such that all are as fully filled as possible so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

Now that we have 32 nodes at 3rd last level, it means that we need 32 tree pointers at 4th last level. So,

4th last level : 32 Pointers, So $\left \lceil 32/5 = 7 \right \rceil$  Nodes are required at this level such that all are as fully filled as possible so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

Now that we have 7 nodes at 4th last level, it means that we need 7 tree pointers at 5th last level. So,

5th last level : 7 Pointers, So $\left \lceil 7/5 = 2 \right \rceil$  Nodes are required at this level such that all are as fully filled as possible so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

Now that we have 2 nodes at 5th last level, it means that we need 2 tree pointers at 6th last level. So,

6th last level : 2 Pointers, So $\left \lceil 2/5 = 1 \right \rceil$  Node is required at this level such that all are as fully filled as possible so that we can have least number of levels and nodes possible to store 3120 keys in the B+Tree of order 5. 

So, 6th last level is the Root level. So,

So, Total Keys that we inserted are 3120. So, we can say that If we want to store 3120 Keys in B+T with order 5 such that we get minimum number of levels then we will need 6 levels and total 978 Nodes. 


So, We can see that If order of BT and B+T is same and number of keys are large  then B+T will have more levels than BT and also more number of Index nodes in B+T than in BT.

So, Option B,D are correct. 

 

edited by
0 votes
0 votes

acc. to me

ans:B

for a and b option)

indexing nodes is more in B+ because  it holds key value both in internal and leaf while B tree only has one entry for one key, rest for record pointer it is constant in both cases. so 

 for c)http://www.differencebetween.info/difference-between-b-tree-and-b-plus-tree

         so,false

correct me if i m wrong

0 votes
0 votes

Option b is right

  • B+ tree have redundant key( search key is repeated) . But in B tree there is no redundant (search key is not repeated)key . So number of levels in b+ tree is more.
  • In B+ tree  we can access sequential as well as random.
  • but in B tree only random access is possible.

Related questions

1 votes
1 votes
0 answers
4
raviyogi asked Jan 4, 2018
295 views
how many block at database level (storing records) are required?