2 votes 2 votes In a database file structure, the search key field is 9 bytes long, the block size is 1024 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a leaf node in a B+ tree implementing this file structure is Databases databases indexing made-easy-test-series + – sumit chakraborty asked Jan 26, 2018 • edited Mar 4, 2019 by ajaysoni1924 sumit chakraborty 1.2k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Ashwin Kulkarni commented Jan 26, 2018 reply Follow Share It should be 63. p(9+7) + 6 <= 1024 P = 63. 2 votes 2 votes sumit chakraborty commented Jan 26, 2018 reply Follow Share Thanks. I also got 63 but the answer given was 64 with the explanation as (p-1)(9+7) + 6 <= 1024 and so i just wanted to clarify. 1 votes 1 votes Ashwin Kulkarni commented Jan 26, 2018 reply Follow Share Haha! Many times they mixed up B and B+ tree concepts for these crucial answers ! and unnecessarily it confuses us! :( 0 votes 0 votes saxena0612 commented Jan 26, 2018 reply Follow Share @Ashwin Kulkarni : you are taking $P$ pointers to data records and $1$ more for next block but that constitutes to $P+1$ pointers which is contradicting the order of a block. Source : Navathe : $6^{th}$ edition Page no 653 0 votes 0 votes Ashwin Kulkarni commented Jan 26, 2018 reply Follow Share @saxena, I did the same way as diagram shows. P <key,record> pairs and 1 block pointer for the next block. And order of leaf will be number of <key,record> pairs in it! 1 votes 1 votes saxena0612 commented Jan 26, 2018 reply Follow Share Yup ! you are correct I erroneously counting the block pointer in order which is not the case. Thanks! 1 votes 1 votes ushamya commented May 18, 2019 reply Follow Share Block Size = 1024 bytes Record pointer = 7 bytes Block pointer = 6 bytes Search keys = 9 bytes Then, = $(p-1) * (Record pointer + Key size) + Block Pointer \leq Block Size$ = (p-1) * (7+9) + 6 ≤ 1024 = (p-1) * (16) ≤ 1024 -6 =16p - 16 ≤ 1018 = 16p ≤ 1034 p ≤ 1034/16 = 64.625 = 64 So, the answer should be 64 right?How it is 63? 0 votes 0 votes Satbir commented May 18, 2019 reply Follow Share you are taking wrong formula. For a B+ tree the order of a node is the maximum number of keys that it can contain. for B+ tree if p is the order then in leaf node there are p <key,record pointer> and 1 block pointer. (p)∗(Recordpointer+Keysize)+BlockPointerSize ≤ BlockSize 1 votes 1 votes ushamya commented May 19, 2019 reply Follow Share Okay. Thank you! 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes solution Rishabh24Mishra answered Jan 26, 2018 • selected Jan 26, 2018 by sumit chakraborty Rishabh24Mishra comment Share Follow See 1 comment See all 1 1 comment reply rajatmyname commented Mar 8, 2019 reply Follow Share Can you please give general formula for both B-tree and B+tree and for leaf as well as non-leaf nodes? 0 votes 0 votes Please log in or register to add a comment.