How can I determine the order of B+ Tree ?
Or it should be according to the number of total elements in the tree.
eman 22 0 Junior Poster in Training
Narue 5,707 Bad Cop Team Colleague
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 0 Junior Poster in Training
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 5,707 Bad Cop Team Colleague
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 0 Junior Poster in Training
is there a way to determine the order according to the maximum total number that will be insert?
griswolf 304 Veteran Poster
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 0 Junior Poster in Training
yeah, I really will enjoy
rubberman 1,355 Nearly a Posting Virtuoso Featured Poster
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 1,355 Nearly a Posting Virtuoso Featured Poster
Ok. Back from vacation now. Yes, Sorting & Searching is volume 3... :-)
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.