*
The moose likes Java in General and the fly likes b-tree, where to start?? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "b-tree, where to start??" Watch "b-tree, where to start??" New topic
Author

b-tree, where to start??

billo bailey
Ranch Hand

Joined: Dec 02, 2002
Posts: 50
Howdy,
I have to implement a b-tree and am somewhat stumped as to how to proceed. Heres the helper code we've been given, to get us on our merry way though its not much help if you ask me.

could anyone shed some light on where to go next. The tree will have node size of 4 max and 2 min.
thanks
bill


only users lose drugs
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

So it sounds like homework.
You know what a btree is?
What is the usage of a btree?
What method does a user need?
How will he want to call them?


http://home.arcor.de/hirnstrom/bewerbung
Nathaniel Stoddard
Ranch Hand

Joined: May 29, 2003
Posts: 1258
Billo,
Don't mind Stefan--I'll do your homework for you! Give me a couple minutes to pump out a nice B-tree for you. Does your teacher have any strict coding conventions I need to follow?
There used to be a nice algorithms website that told you all about these sorts of things, and a million other data structures, and who knows what else. Have you tried searching Google for "b-tree". The first link explained things pretty well for me--and I'm a bit slow. Geez, link #3 even gives you pseudocode.
[ April 23, 2004: Message edited by: Nathaniel Stoddard ]

Nathaniel Stodard<br />SCJP, SCJD, SCWCD, SCBCD, SCDJWS, ICAD, ICSD, ICED
Adam Seth Tyler
Greenhorn

Joined: May 05, 2004
Posts: 2
Hey Nataniel,
Is there any chance you can foward this information on?
I have a similar program to write and it is doing my head in!!
Magical1
[ May 05, 2004: Message edited by: Magical1 ]
[ May 05, 2004: Message edited by: Magical1 ]
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Magical1: First you have to stick to the naming - conventions, and then we will explain, how you can use yahoo, to find google.
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
Originally posted by Magical1:
Look Stefan,
If you want to come across as the German equivalent to a "muppet" that is certainly your perogitive!
After all there is no shame in admitting that you are incapable of creating such a program due to your lack of understanding in the data structures that govern such algorithims in Java.
As we say in English is better to keep quiet and be thought a fool, than open your mouth and remove all doubt!
Magical1


"Magical1"
You're quickly removing all doubt from my mind that you deserve the help that Javaranch can offer. PLease change your name, and start treating the members here with respect, or go find another site.
M


Java Regular Expressions
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
Hi billo,
Let's start with the first steps. Do you know what a B-tree is, and why it's used?

M
Adam Seth Tyler
Greenhorn

Joined: May 05, 2004
Posts: 2
Yes I understand the concept as a Data Structure,
and I am using it to manage entries into a database, at least that is the jist of my problem.
But I am finding the concept of a triple, pretty difficult to use, as it restricts the number of pointers available to me.
Let me explaina little more here are the type of specs required
Implement a Btree Index Creation application that will allow you insert integer keys into a B-Tree of m=5 (that is minimum number of keys in a node is 2 and maximum number of keys in a node is 4).
The application is a simple loop that takes integer key inputs from the user until no integer key is typed.
The loop would look something like this:
1. take integer key input from user;
2. search through the B-Tree using a search Btree method until appropriate node is found into which
key is to be inserted;
3. insert the key into the node using a insert Btree method which will create a BtreeTriple entry in
the node. Leave the TreeData part of the BTreeTriple entry blank, this will later be set up to retrieve from the invoice number in the database;
4. if necessary split the node and try to insert promoted key into parent node (back to step 3) and
repeat until no splits needed.
5. Display the current BTree on the screen;
6. go to step 1
In addition, when no more input (that is no integer key typed) the application should print out the Btree
to the screen.
----------------------------------------------------------------------------
this is what I understand of a b-tree triple
public class BTreeNode {
private BTreeNode first; // Reference to B-tree node with keys less than first key of the node.
private BTreeTriple [] entries; // array of B-TreeTriple entries.
}
class BTreeTriple {
private int key;
private TreeData info; // reference to data for this key
e.g. file address of record
private BTreeNode next; // reference to B-tree node for keys > this key and less than the next key in this node
}
----------------------------------------------------------------------------
As I suffer from having a poor short term memory things I learn I don't remember for a while and this is giving me a complete mental blank.
I am sorry I did not originally notice the naming scheme as listed when I signed up, I am sorry!
Adam Seth Tyler
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Thanks, Max,
but
- I'm used to defend myself
- the muppets are well known here, and 'kermit the frog' is a superstar. Sometimes I'm more like the draconic eagle, but we all love the muppets, so it was no problem to me.
- I don't like censorshipship but I finally accept your interest in keeping this a 'nice place'.
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
Originally posted by Stefan Wagner:
Thanks, Max,
but


You're welcome
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: b-tree, where to start??
 
Similar Threads
How to find Path with Max weight
Mapping Keys to nodes in JTree
Trees in Java
HashMap
help with itteration through a multi dimensional array?