Register

b+ tree order

2,629 views
1 votes
1 votes
Assume block size 4096 bytes,size of key is 4 bytes,size of pointer is 8 bytes.How many keys are possible per blocks for b+ tree organisation?

(a) 155

(b) 154

(c) 341

(d) 340
User Avatar

3 Answers

3 votes
3 votes

search field is V = 4 bytes long, the block size is B = 4096 bytes, and a block pointer is P = 8 bytes. As internal node of the B+ tree can have up to p tree pointers and p-1 search field values, these must fit into a single block. Hence, we have,
 
 
(p * 8) + (( p – 1 ) * 4 <= 4096
 
or (12 * p) <= 5000
 
p = 416.66 , So max keys are possible is 415 ( we cant consider the fraction )

But is this problem they done it this way 

 As internal node of the B+ tree can have up to p+1 tree pointers and p search field values, these must fit into a single block. Hence, we have,

 
(p+1) * 8 + p * 4 <= 4096
 
or (12 * p) <= 4088 

p = 340.66 , So max keys are possible is 340 ( we cant consider the fraction ) 

User Avatar
2 votes
2 votes

# of key =lower bound of ( block size/ (key + pointer))=lower bount of ( 4096/(4+8)= lower bound of (341.33)= 341

User Avatar
0 votes
0 votes
Ans: (d)

Order P = max. keys possible

So, the formula to use: P*K + (P+1)*Bp <= BS

Here, BS is block size, K is key, Bp is block pointer and P is order.

therefore, 4P + (P+1)8 <= 4096 gives 4P + 8P + 8 <= 4096 gives 12P <= 4088 gives P = 340.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
gauravkumawat asked Jun 13, 2023
943 views
Explain the properties of B-Tree Also Construct B+ tree with order P=4 10,5,30,40,20,17,90,45,93,60,20,50,29
please solve in paper formet Explain the properties of B-Tree Also Construct B+ tree with order P=410,5,30,40,20,17,90,45,93,60,20,50,29
User Avatar
0 votes
0 votes
1 answer
2
Crackcer asked Jan 10, 2022
253 views
Order of B and B+ tree(ACE academy test series)
1. Suppose there is a B-tree, such that internal node with order 86 and leaf node with order 103. 2. A B+ tree with internal order is 171 and leaf node with order 103. In both scenarios what is the order of the tree?
1. Suppose there is a B-tree, such that internal node with order 86 and leaf node with order 103.2. A B+ tree with internal order is 171 and leaf node with order 103.In b...
User Avatar
0 votes
0 votes
1 answer
3
Salazar asked Jan 29, 2018
3,967 views
Maximum height of a B+ tree of order m with n key values is (With Derivation)
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) N I tried deriving but had some trouble, could someone assist with the derivation or derivation process ?
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) NI tried deriving but had some trouble, could someone assi...
User Avatar
6 votes
6 votes
1 answer
4
firki lama asked Jan 14, 2017
5,956 views
order of leaf node in b+ tree??
which formula should we use for calculating LEAF node in B+ tree? I. n*(K+r)+b<=block size where n=no of keys k=key size,r=record pointer,b=block pointer II. (n-1)(K+r)+b<=block size
which formula should we use for calculating LEAF node in B+ tree?I. n*(K+r)+b<=block sizewhere n=no of keysk=key size,r=record pointer,b=block pointerII. (n-1)(K+r)+b<=bl...
User Avatar
Link Copied!