31 votes 31 votes In a B+ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2\;\text{B}$ , then the maximum order of the B+ Tree is ____ Databases gatecse-2017-set2 databases b-tree numerical-answers normal + – Madhav asked Feb 14, 2017 • edited Jun 19, 2021 by Lakshman Bhaiya Madhav 11.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply swap_it commented Feb 14, 2017 i moved by Puja Mishra Jan 19, 2018 reply Follow Share order-p p(block pointer size) + (p-1)keysize<=512 p=52 As record pointr size is not given the node is assumed to be internal one. 2 votes 2 votes Harshal Sapkal commented Feb 16, 2017 reply Follow Share 63.75 should be the answer 1 votes 1 votes Please log in or register to add a comment.
Best answer 57 votes 57 votes Let order of $B+$ tree is p then maximum number of child pointers $= p$ and maximum number of keys $= p-1$. To accommodate all child pointers and search key, total size of these together can not exceed $512\;\text{bytes}$. $2(p)+8(p-1) \leq 512$ $\implies p \leq52$ Therefore, maximum order must be 52. Sachin Mittal 1 answered Feb 14, 2017 • edited Jun 19, 2021 by Lakshman Bhaiya Sachin Mittal 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply `JEET commented Dec 16, 2019 reply Follow Share @Sachin Mittal 1 @Satbir Can you please tell me how the above formula is derived? I mean the logic of that. 1 votes 1 votes rhl commented May 17, 2023 reply Follow Share See the below diagram Let the order of B+ Tree be $p$, which means a node can have at max $p$ total pointers Using leaf node we see that we have $1$ Block Pointer to point to the next leaf node and $p-1$ <key,Data pointer> pairs. Using above information we can easily conclude that $2B + (p-1)(2B+8B) \leq 512$ Using Internal Node we see from the above diagram it has $p$ Block Pointers and $p-1$ keys. Therefore $2p+8(p-1) \leq 512$ Solving any of the equation we will get the same answer. But why? Usually, the Record pointer has more size than our Block Pointer due to offset. The scenario given here can’t happen in real life. But since the size of both pointers is same we will get same order for internal nodes and leaf nodes. Usually in B+ Tree leaf nodes and internal node has different order. 1 votes 1 votes Please log in or register to add a comment.
13 votes 13 votes hope it might help.... akash.dinkar12 answered Apr 4, 2017 akash.dinkar12 comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Let the Order of the tree to be p. Every b+ tree node contains p children and p-1 data items where record pointer are not present in the internal nodes. So p(Block pointer size)+(p-1)Key size<=Block size p(2)+(p-1)8<=512 p=52. swap_it answered Feb 14, 2017 swap_it comment Share Follow See all 4 Comments See all 4 4 Comments reply Prashant. commented Feb 14, 2017 reply Follow Share where given it is asking for leaf node or internal node. 5 votes 5 votes mcjoshi commented Feb 14, 2017 reply Follow Share For leaf node we need to know record pointer size also. So, data given above is sufficient enough if it is considered internal node. 11 votes 11 votes swap_it commented Feb 14, 2017 reply Follow Share The record pointer is not given so assumed it to be internal node. 1 votes 1 votes piyushrawat01 commented Jan 2, 2019 reply Follow Share Order of a B tree is maximum number of children in a internal node unless specified otherwise, moreover record pointer value not given. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes B+ Tree internal node structure Contain N-1 keys and N block pointers (Where N is order of B+ tree) N(Block Pointer Size) + N-1(Key size) <= Block size N(2) + N-1(8) <= 512 By solving this equation we will get N = 52 Suneel Padala answered Feb 8, 2019 Suneel Padala comment Share Follow See all 0 reply Please log in or register to add a comment.