0

Hi all, I'm having difficulties with a past paper question on B+ Tree's that I need to fully understand for an exam 2 weeks from now. Any help would be appreciated!

I need to construct a B+ tree with branching factor M = 3. Each leaf can contain up to L data items, where L = M. Draw the B+ tree after insertion of 2, 9, 3, 8, 5, and 6 (in the given order).

Firstly can anyone tell me what M and L are abbreviations for? And can anyone direct me to any helpful tutorials or guides on how to do B+ Trees? I'd really like to know how to do these!
Thank you!

2
Contributors
4
Replies
6
Views
7 Years
Discussion Span
Last Post by C Newbie
0

M represents the number of potential links in a node (the number of direct children). A binary tree is M=2, for example. A B+ tree stores data in the leaf nodes and only keys in internal nodes, so L in this case represents the number of data items each leaf can hold.

Edited by Narue: n/a

0

M represents the number of potential links in a node (the number of direct children). A binary tree is M=2, for example. A B+ tree stores data in the leaf nodes and only keys in internal nodes, so L in this case represents the number of data items each leaf can hold.

So I would start off with:
|2|9|
v
|2|3|9|
v
?

How would 8 be brought into the tree then?
Thanks for the reply btw

0

>How would 8 be brought into the tree then?
B-trees use a split and merge technique for adding and removing nodes. It works the same way with a B+ tree, which your reference material should explain clearly.

0

>How would 8 be brought into the tree then?
B-trees use a split and merge technique for adding and removing nodes. It works the same way with a B+ tree, which your reference material should explain clearly.

I've been working on this for a while now and I got:
|3 6|
|2| |5| |8 9|

I think this is the right way of creating a separate tree and merging. Sorry this is probably useless...

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.