Re: Inorder Traversal of B-Tree

On Jan 28, 7:37 pm, annamalai <annamalai.gurus...@xxxxxxxxx> wrote:
On Jan 28, 9:12 pm, user923005 <dcor...@xxxxxxxxx> wrote:

On Jan 28, 5:20 pm, annamalai <annamalai.gurus...@xxxxxxxxx> wrote:

Hi All,

Can anybody tell me whether an in-order traversal of a B-Tree will
result in the keys being listed in ascending order?  I am trying to
find out the correct way to do an inorder traversal of a B-Tree.  Any
help much appreciated.

What do you suppose that "inorder" means in terms of traversal?

When you are in doubt, simple things can get confusing.  Most of the
discussion about tree traversal talks in terms of node (rather than
the keys).  Even the Wikipedia article on Tree_traversal, talks in
terms of node.  I guess that is because they are talking about binary
search trees.  I am looking for multiway tree traversal, specifically
B-Tree traversal.

Let me then rephrase my question slightly.  While traversing a B-Tree,
what does it mean to visit a node?  Do I visit only one key, or do I
visit all the keys?

In a Bayer tree, the keys are clumped by similarity.

This may prove helpful:
1.  Go to :http://www.google.com/
2.  Type the words "Inorder traversal" into the search box
3.  Click the button that says "Search"

I always do that before I post.  For example, you try to search the
internet and find out if there is any article that talks about multi
way tree traversal (or B-Tree traversal).  If you find it, then please
give it to me.  I would be thankful.  If you cannot find it, then you
will know why I didn't find it either!

Sorry, I have a tendency to mistake B-tree for btree. The second is
trivial, the first is not.

Here is a very simple tutorial:
http://www.semaphorecorp.com/btp/algo.html

There is a very nice C++ oriented tutorial on Bayer trees here that
shows inorder traversal:
http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

Here is a nice Perl tutorial on Bayer trees:
http://perl.plover.com/BTree/
.

Quantcast