• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How to create the inner nodes of a B+tree?

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi guys,

like the title says it already I have to write a methode which generates all inner nodes of a b+tree. I dont know what the code has to look like, not even a real approach.
In the List children there are all leaves of the tree in ascending order. My task is now to create all inner nodes out of the sorted leaves List.

My approach:



If you guys need more information, please let me know.

best regards
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Don't know myself, but please explain to us how a B+tree is made up, and what the nodes represent, and how they are connected to other nodes. That may give you some inspiration about what to do; some people call that rubber duck programming.

I am duplicating this discussion in another “general” forum.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I suggest you don't return null in line 17. It is probably better to return a 0‑element List instead.
 
Stephan McAllister
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok thanks guys for your answers, because it is really important for me to get the task done. I am a little bit under time pressure
The buildLeafLevel Method works nearly like expected, I dont know what to do with the children attribute in the BPNode contructor? This should be implemented in this method as well.
The buildInnerLevel method should create the inner nodes of this b+tree. A b+tree looks like that:



Here are the two important classes the third one is only to scan input.





I hope thats enough information.

best regards
 
Stephan McAllister
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why is my image not shown?

Requirements for a inner node of a b+tree
Each inner node has at least ceil.(m/2) maximum m children.
m stands for a pointer in this tree. Lets say m = 5 then this means there are 5 pointers and 4 keys.
On this image you can see the last level are leaves and the levels above are inner nodes.
B-Tree-Example.jpg
[Thumbnail for B-Tree-Example.jpg]
B+tree
 
Stephan McAllister
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nobody has an idea how this job could be done?
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan McAllister wrote:Why is my image not shown?



The forum software expects a URL which returns an image. The URL you used, although it looks like it should return an image, actually returns an HTML page which contains your image and some other things. And so the forum software doesn't understand it.
 
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan McAllister wrote:Nobody has an idea how this job could be done?


Since you are in Java in General forum, you are expected to be a bit more proficient in describing your issue. You just mentioned you have no idea how to do it. Well, my advise is - spend more time on it, read class slides, analyse snippets shown in a class, and when you get some idea and run into problems accomplishing that, then come back and let’s discuss it.

There are lots of code, and looking to some comments these seem to be instructor’s written classes, at least some of them, so it isnt really even clear if you had started on some parts.

You can learn only on spending lots of time on problem until you get pretty good idea how it needs to be done, granted, you may stuck on little things, but these supposed to be little.
 
Stephan McAllister
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for your replies @Clapham and @Vilda. Yeah, but it's no problem downloaded the image and attached it to the post.

Vilda I spent now 3 day on a specific problem and can't get it solved so it would be nice, if somebody could push me in the right direction.
My specific problem is that I dont know how to create this method:



Because I dont know how to sort it the right way. I have to iterate over all leaves(children) and all keys in that leaves, then I have to take every first key and save it to currentLevel. After that, if there are to many keys in > m-1 keys in the first node I have to split the inner node and create 2 new nodes. One goes above and the other one stays at the same level. Like in the picture above.
That's my specific problem I hope you can help me guys.

best regards
 
reply
    Bookmark Topic Watch Topic
  • New Topic