File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

b-tree, where to start??

 
billo bailey
Ranch Hand
Posts: 50
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Nathaniel Stoddard
Ranch Hand
Posts: 1258
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Adam Seth Tyler
Greenhorn
Posts: 2
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1923
Linux Postgres Database Scala
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4118
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Max Habibi
town drunk
( and author)
Sheriff
Posts: 4118
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1923
Linux Postgres Database Scala
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4118
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stefan Wagner:
Thanks, Max,
but


You're welcome
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic