Printable View
Anyone have any ideas on creating a B-Tree index of a delimited text file in memory? I'm trying to code this in C++ (no C functions - OO only).
Example:
void create(char datafile[], int delimiter);
Will create a B-Tree from the datafile passed to the function, and use the Xth delimited field of the file as the B-Tree's primary key, where X = dilimiter.
Any ideas?? Thanks.
Sure I have some ideas. But how about you attempt writing this a little more yourself before I jump in.
Well, I'm really sort of lost - I have never coded a B-Tree before, and I am having a lot of trouble finding any references.
I'm not really sure how to declare my nodes, the insert procedure, and also getting my program to traverse the file in the manner outlined above.
Well you're not looking very hard
http://faq.cprogramming.com/cgi-bin/...&id=1073086407
A thourough discussion of B-trees with sample code.
http://cis.stvincent.edu/carlsond/sw...ree/btree.html
Well, that's nice - but the http://faq.cprogramming.com/cgi-bin...6&id=1073086407 link doesn't even mention B-Trees. And the second link http://cis.stvincent.edu/carlsond/s...tree/btree.html is a site I've already been to - doesn't help much.
I disagree the site does a good job discussing B trees. Just because it does not provide full solutions does not mean it does not help much.Quote:
doesn't even mention B-Trees. And the second link http://cis.stvincent.edu/carlsond/s...tree/btree.html is a site I've already been to - doesn't help much.
The references at the bottom are out of date. A good source would be a Data Structures book.
jc :)
To implement B-Trees in memory is somewhat difficult. Simply inserting the keys into the tree, similar to a binary tree, isn't too hard. Just makes sure a node's children are ordered such as the pictures on the website. The hard part ist when the key is inserted to a node and some condition is met on the node you need to split the node, increasing the keys in the level above. Once spliting the node inserted, the level above might also meet the split condition, so your split routine has to recursively walk above the trees. In effect, from a child node you need to acess a parent node, and your datastructure would look something like this:
(You might try to find a better datastructure)Code:struct Node {
Node* nodes[4]; // an empty space is NULL
int keys[3];
Node* parent; // points to the node above
int numKeys;
};
The ordering between keys and the nodes are such that keys[0] < keys[1] <...< keys[numKeys-1], and, ignoring a few special cases, nodes[i] is placed between key[i - 1] and key[i].
How you split is that you take a group keys such as ( 2, 5, 6, 7, 8, 9, 10), and then pick the median. After picking the medien, you form two sides, those before the medien and those after. In this case the medien is 7, so your two sides are (2, 5, 6) and (8, 9, 10). The 7 must, then, be brought up to the layer above the node splitted, and then this node might be split. As you can see it's fairly complicated; you're definitely going want to try this on paper a few times.
Thank you - that's exactly what I was looking for.
My professor gave ONE example of this in class and never showed us any code. So, the day after, he assigns a project on it - over Thanksgiving break.
So, thank you.