B+ tree Data structure

[eman 22]

How can I determine the order of B+ Tree ?

Or it should be according to the number of total elements in the tree.

[Narue]

I'm not sure you're using "order" the way it's usually used. The order of a B+ Tree refers to the maximum number of children an internal node could have. Can you be more specific as to what you're asking?

[eman 22]

yes I know that the order of B+ tree the maximum number of children an internal node could have.
but in the implementation of the tree how can I determine it?

Should I assumed that is a input to tree? Or what should I do?

[Narue]

You're the programmer, do what you want... Though if this is a library, it would certainly be a good idea to let the client code choose an order.

[eman 22]

is there a way to determine the order according to the maximum total number that will be insert?

[griswolf]

Are you asking for a way to determine what is the optimum order for a given B+ Tree? If you think about it, you will see that this "optimum" value depends on the cost to do these things:

• Searching
  • Follow a link to a child node
  • Find the appropriate key within a node
• Inserting
  • (see searching)
  • Insert a key into a node
  • Re-balance by splitting
• Deleting
  • (see searching)
  • Remove a key from a node
  • Re-balance by joining

Of course, these costs vary with platform, with underlying storage, with the size of the cache... And the importance of each also varies: How often do you do inserts or deletes compared with how often you do a lookup? This is a fun problem that can be approached in several ways.

In theory, you can just talk about Big Theta costs (though you will have to think hard about the meaning of 'N')

In a lab, you can use test data to measure the effect of changes

For a paper, you can do research to see what the industry does

For a thesis, all of the above. And more. And more...

Enjoy!

[eman 22]

yeah, I really will enjoy

[rubberman]

Donald Knuth's volume on Sorting and Searching has some superb explanations of this stuff. Donald Knuth, The Art of Computer Programming. I think S&S is volume 3, but since I am on vacation this weekend, I'm not at home to look at the book and tell you precisely.

[rubberman]

Ok. Back from vacation now. Yes, Sorting & Searching is volume 3... :-)