B-Trees

[Danesh]

Hi all,

I need help if anybody has any exprience in implementation of B-Tress. Actually, there are many resources about implementing B-Tree algorithms (Search, Insertion and Deletion) but they are in recursive form. I need something in non-recursive form.
I will explain a little about B-Trees. B-Tress are used in indexing files which reside on disk and the goal is to minimize the number of disk accesses to retrieve a key from a B-Tree. B-Trees always are ballanced. It means that they have same height for each key to get reached. To satisfy ballanced condition if a node in a B-Tree is full it will be spilitted into two new nodes and new key (overflowed) will send to upper lever (parent of this node). In fact, recursive functions are used for insertion because you have to keep track of each visited node and to come back and insert overflowed node if necessary, but I need something non-recursive. For more information about B-Trees yu can search on net or follow this link: http://slady.net/java/bt/view.php?w=1000&h=750
It will show B-Trees actions in graphical form.

Regards,

Danesh

[gabor]

Hello!

I'd like to ask what progress have you got since the start of this topic?
Nowdays I am working on tree algos and implementing a B-Tree could be an interesting challange.
Though I'm implementing a general tree model, not a retrieve or search tree, something that I can easily use for storing XML data, but later I sure will need an auxillary tree or more for indexing the data stored by this general tree.

Greets, Gábor

[asmfan]

i see only one plus of non recursive algos - avoiding stack overflow during deep recursion, but you can cope with it in recursive algos by specifying additional stack size in linker options.
actually there is another plus - saving time by avoiding calls on every recursion level... its another story;)

[zooba]

i see only one plus of non recursive algos - avoiding stack overflow during deep recursion, but you can cope with it in recursive algos by specifying additional stack size in linker options.

Though if you think/know you're going to suffer deep recursion you can allocate memory manually for the stack - just change ESP to point at it :u

[asmfan]

Zooba,
it is a good point, but what about HLL? you cannot do it in Java for example. this hand-made trick of low-level programming only, but B-trees are all-level programmed as math abstraction.

[zooba]

I would expect that any decent HLL would manage the stack such that more space is allocated when required.

I don't think there are many decent HLLs out there  :snooty: :bdg :U