if I want to insert J, A, F, C, R, S, and L, into a b+ tree in that order, is this the way to do it?
insert
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
That's a reasonable way of doing it.
When you insert R you can split the nodes up so that F is in the right one, but that's just arbitrary. It would result in arity 2, 3, and 2 in 3 bottom nodes instead of 3 and 4 in 2 bottom nodes, but it's just as valid. Unless for some reason you're required to implement a B+ tree using a specific algorithm (like for a class), this doesn't really matter.
Why does F show up twice? In a real implementation, you'd include a data pointer with EVERY key value, not just on leaf node key values, so you would only see F in there one time.
When A and C are deleted, the ideal implementation would detect that the leaf node is less than half-full, and it will combine the data and merge it back into the root node.
BillBach: You could consider this to be a B+-tree implementation of a set instead of a map, so there are no values in the terminal nodes.
> will it be A and C on the bottom left J on the root and J,R, and S on the bottom right? Am I getting this correctly?
You have the bottom row correct. But notice that F is in the root in your example tree. This implies that a key in an internal node is equal to to the maximal key in its corresponding subtree. So the root node should contain C, not J.
No. Think about the lookup algorithm for a B+tree.
You look at the keys in the root node, and find the first one that is >= the key you are looking up. Then you descend into the corresponding subtree and recursively do the same thing until you reach a terminal node (where you search for an exact key match). If all of the keys in an internal node are less than the key you are searching for, then you descend into the rightmost subtree.
In the top node you need to have information that steers the search into the correct subtree. So you store the maximal key in the corresponding subtree for each internal node. The maximal key in the left subtree is C, so you keep C in the first key slot of the root node.
Business Accounts
Answer for Membership
by: epasquierPosted on 2009-10-01 at 04:13:26ID: 25467474
What do you call a B+ tree ? If I understand correctly your example, it is a two-way linked chain of 5 values array, used to quickly implement a sorted list of values.
It seems complicated though, why not use a two way linked chain of simple values ? Why is F in two arrays when you insert R ?