44 votes 44 votes With reference to the B+ tree index of order $1$ shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query. "Get all records with a search key greater than or equal to $7$ and less than $15$ " is ______. Databases gatecse-2015-set2 databases b-tree normal numerical-answers + – go_editor asked Feb 12, 2015 • edited Jun 19, 2018 by Pooja Khatri go_editor 13.4k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments Chhotu commented Dec 22, 2017 i edited by Chhotu Dec 22, 2017 reply Follow Share Notice --> In this question next block pointers in leaf node are bi-directional. But I think in general next block pointers in leaf node are unidirectional. PS: @Anu007 ji, Please check http://2.bp.blogspot.com/--7OpPitZhoQ/Uy8TVPCxenI/AAAAAAAACPs/lUkMHUTlM2g/s1600/Structure+of+a+leaf+node+of+B++tree.jpg 3 votes 3 votes Anu007 commented Dec 22, 2017 reply Follow Share no it is bidirectional. see each node has |pleft| key |p| key|pright| so pleft of one node contain address of its left node while pright of left node contain address of its left node. 0 votes 0 votes jatin khachane 1 commented Oct 30, 2018 reply Follow Share @Chhotu By default it is unidirectional. 3 votes 3 votes Please log in or register to add a comment.
Best answer 68 votes 68 votes whichever way you go from the root to leaves, you'll always end up counting $5$ nodes. amarVashishth answered Dec 26, 2015 • edited Jun 15, 2021 by S k Rawani amarVashishth comment Share Follow See all 12 Comments See all 12 12 Comments reply Abhi_S commented May 12, 2017 reply Follow Share Wouldn't the next node (17,null) be checked to ascertain the value of the first search key (referring to the diagram with green highlight) ? Otherwise, how will the program know when to stop accessing nodes in the backing store to retrieve the values? Edit - I understand why it's the case - they've asked for range query with search key greater than or equal to 7 and less than 15. Thus after accessing the node containing 15, it won't check further as the range upper bound has been encountered. Thus only 5 blocks will be accessed. 7 votes 7 votes venkat_sirvisetti commented May 12, 2017 reply Follow Share The question clearly mentions "Records with search key greater than or equal to 7 and less than 15". So, when we are traversing it is safe to stop as soon as we reach search key 15. However, if he asked less than or equal to 15, then we must check the next node 12 votes 12 votes Vicky rix commented Nov 11, 2017 reply Follow Share To satisfy the query we should not only fetch the index blocks but after that we need to also fetch the data blocks .. since "minimum number of blocks that needs to be fetched" is asked ... we can think that all index records are having the record pointer as pointing to the same node .. in that case 5 index blocks + 1 data block = 6 blocks are needed ... this is what i feel .. i think in the question they should have mentioned "how many index blocks are to be fetched to execute this query" 0 votes 0 votes learner_geek commented Dec 3, 2017 reply Follow Share If asked less than or equal to 15 then also #5 nodes to be fetched??because as we reach 15 terminate to search?? 3 votes 3 votes Dileep kumar M 6 commented Dec 13, 2017 reply Follow Share Here in the secound case why internal node 5 is not accessed and in the leaf level what is significance of two direction arrow(is it is doubly linked list) 0 votes 0 votes talha hashim commented Sep 21, 2018 reply Follow Share @ Vicky rix sir this is B+ tree not B-tree .you are actually defining the property of B-tree 0 votes 0 votes !KARAN commented Apr 13, 2019 reply Follow Share I am thinking which path would be traversed in actual scenario. Why green path would be traversed? As we know that $B^+$ tree support range queries, so whatever nodes being accessing will be compared with the range given that is $(\geq7 \text{ and} \lt15)$. Due to this only pink path would be traversed not the green path. 0 votes 0 votes Logan commented Jan 2, 2020 reply Follow Share The question asks the number of nodes fetched, as in a B+ tree data lies only in the leaf why would internal nodes be fetched?. The question is not asking about accessed. According to this 3 nodes should be fetched. 0 votes 0 votes KartikGawande commented Dec 12, 2022 reply Follow Share Why is the question saying order is $1$ but showing $B+ tree$ of order $3$ for the non leaf nodes? 1 votes 1 votes phaniphani commented Nov 16, 2023 reply Follow Share Same doubt… Why is it saying order 1 but have 3 pointers 0 votes 0 votes phaniphani commented Dec 22, 2023 reply Follow Share Hey, I am not sure I understand what you are saying. Do you mean to say that 1 order here means there is one middle pointer per block. ie, do you mean that when telling the order of a B-tree we exclude the first and last? 0 votes 0 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Dec 22, 2023 reply Follow Share @phaniphani now i got it what u were trying to say yes ig this is mistake here 0 votes 0 votes Please log in or register to add a comment.
21 votes 21 votes The total number of nodes accessed including root will be 5. The order is, (9)-->(5)-->(5,7)-->(9,11)-->(13,15). Gate Keeda answered Feb 12, 2015 Gate Keeda comment Share Follow See 1 comment See all 1 1 comment reply Kaluti commented Sep 20, 2018 reply Follow Share I am also not getting why in the leaf nodes doubly linked nodes are used here. Leaf nodes in b plus tree store record pointer as well as block pointer is that they wanna to represent by doubly linked list 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes The question wants us to perform a range query from 7 to 14 (both inclusive) on a $B^+ \ tree$ This requires for us to first reach the leaf node that has 7, and then traverse in a forward direction until we reach 14. Or vice versa. This works because:- ALL the keys can be found in the leafs of a $B^+ \ tree$ — which are interconnected. Keys are arranged in sorted order. Hence, just finding one end of the range is enough. So, we need 3 accesses (counting root) to reach the leaf that has one end of the range. Then 2 more accesses to reach the other end. So, 5 Refer to the pictures in amarVashishth sir's answer for clarity. JashanArora answered Oct 2, 2019 • edited Jan 23, 2020 by JashanArora JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.