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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Knute Snortum
• Paul Clapham
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• Jeanne Boyarsky
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Ron McLeod
• Piet Souris
• Frits Walraven
Bartenders:
• Ganesh Patekar
• Tim Holloway
• salvin francis

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

Greenhorn
Posts: 6
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:

best regards

Marshal
Posts: 64493
225
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: 64493
225
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
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
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

Stephan McAllister
Greenhorn
Posts: 6
Nobody has an idea how this job could be done?

Marshal
Posts: 24464
55

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.

Sheriff
Posts: 6741
466

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
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

 Evacuate the building! Here, take this tiny ad with you: ScroogeXHTML - small and flexible RTF to HTML converter library https://coderanch.com/t/710903/ScroogeXHTML-RTF-HTML-XHTML-converter