• Advertisement
Sign in to follow this  

Similar B-Tree Algorithm

This topic is 4430 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Recently I was working up a concept for an algorithm sort of like a dynamic array. Thanks to a few people though, I discovered something very close to what I had in mind, called a B-Tree. I used this link: http://www.semaphorecorp.com/btp/algo.html With a B-Tree, each node in the tree holds the base of the index. And when you delete a key, it doesn't collapse the index. When you delete a key, you basically have a free slot. What I had in mind though: Instead of each node holding the base of the index, the node would simply hold the number of keys which are contained in that node. When you add a key, you add +1 to the count in each node. When you delete a key, you subtract -1 from the count in each node, etc. To search for a key, you add up the number of keys in each node, until the number of keys is greater than the index for the key you're searching for. What I want to know is if anyone is aware if the algorithm already exists? Considering the B-Tree algorithm already exists... If the algorithm doesn't already exist though, I plan to write a C++ library for it.

Share this post


Link to post
Share on other sites
Advertisement
KISS.

I think you're seriously off base if all you're working on is a dynamic array. I'm going to assume you know about std::vector and are creating an array that doesn't guarenttee continuity in memory (ie, it's made up of several blocks that are allocated as the array is resized, avoiding moving data around).

All you really need is to just have a (singly) linked list of new[]'d arrays, storing a number that is the starting index of that block with each linked list. You're trying to avoid the linear search time for those indexes using a tree structure, but if you end up having so many small blocks that this time matters then you should be rethinking your allocation strategy instead of trying to create a ridiculously complex dynamic array.

Share this post


Link to post
Share on other sites
You would use it like a dynamic array, but otherwise, the algorithm is very different.

Vector - Only efficient when removing keys at the end of the array
Deque - Only efficient when removing keys at the beginning or end of the array

By breaking up the data into several small pieces, it makes the data highly dynamic (comparable to a stack). And the whole 'tree' or braching concept greatly reduces the time needed for searching. If you simply use a 2d dynamic array, the X dimension will grow very large and will become very inefficient.

Share this post


Link to post
Share on other sites
It sounds a little like you've reinvented the concatenation tree.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement