Solved

b-tree with duplicate keys

Posted on 2006-11-02
1
444 Views
Last Modified: 2008-03-17
If multiple identical keys are put into a b-tree, how would it be possible to retrieve all of them?  If for example, you have 5 keys per node, and you insert 15 keys into an empty tree, the root node would be split.  Then during a retrieval, the retrieval function would find all duplicate keys in the root node, and then continue searching in the right node, but the keys in the left node would be lost.

So, how is this problem usually handled?  Do you need to make some kind of separate nodes that store all duplicate keys?
0
Comment
Question by:chsalvia
1 Comment
 
LVL 45

Accepted Solution

by:
Kdo earned 250 total points
ID: 17858611

When a b-tree allows multiple keys, certain rules must be defined.

For instance, when searching for a key you have the option of allowing duplicates in only one of the branches or both.

Searches are much faster when you only have to search one direction.  Though there is added overhead in maintaining the tree.

- Assume that a page holds 10 keys and we add thse 10 keys to a page:   A B C D E F G H I J
- Now we add a duplicate key B.  The most straight-forward approach is to split the page at the duplicate.  Either before or after the target key.  Let's pick before.

These two pages now contain the keys: A and  B B C D E F G H I J

Now we want to add another B to the page.  It's full and the target key already occupies the first position.  We can force another split after the B and continue adding B keys to the page.   Or we can move right to overflow blocks.

We can create a left node and put the duplicate B keys in it.


Note that balancing a tree can be a bit more of a challenge when duplicate keys are allowed and this technique is used.  The trade off is that the search doesn't have to play "what if".  If there are duplicate keys the search will be able to quickly locate them.


Good Luck,
Kent
0

Featured Post

Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Coverting 24 hour time to 12 hour in C++ 15 168
C++ vs C compilers 13 157
First character of input string truncated with scanf 3 94
Finding a good hash function 4 120
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

919 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now