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 Danish commented Feb 12, 2015 reply Follow Share @Arjun Sir ... typo ... its a b+tree of order 3 5 votes 5 votes Arjun commented Feb 12, 2015 reply Follow Share It is order 1 in the paper :O 1 votes 1 votes Danish commented Feb 12, 2015 reply Follow Share So marks to all ??? 1 votes 1 votes monanshi commented Dec 26, 2015 reply Follow Share Tree of order m has m-1 keys. Given order is 1 => 0 keys? :O 1 votes 1 votes amarVashishth commented Dec 26, 2015 reply Follow Share @monanshi you should read above comments too, they had the same issue. 1 votes 1 votes Tauhin Gangwar commented Dec 26, 2015 reply Follow Share root has atleast 2 block pointers atmost p pointers 1 votes 1 votes monanshi commented Dec 26, 2015 i edited by monanshi Dec 26, 2015 reply Follow Share @amarVashishth But no conclusion yet? 0 votes 0 votes amarVashishth commented Dec 26, 2015 reply Follow Share it is self understood that what should be correction to that, also order does not matter here. 5 votes 5 votes monanshi commented Dec 26, 2015 reply Follow Share Thanks. Check this also https://gateoverflow.in/1520/gate1999_21?show=32524#c32524 0 votes 0 votes Sayan Bose commented Nov 5, 2017 reply Follow Share Please update the question. It should be of order=3 or else the solution doesn't make sense 5 votes 5 votes 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 Show 9 previous comments 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.