Thread: B-Tree index of delimited file

  1. #1
    &operator overload neolyn's Avatar
    Join Date
    Nov 2004
    Location
    Morgantown, WV
    Posts
    16

    Question B-Tree index of delimited file

    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.
    Last edited by neolyn; 11-23-2004 at 07:18 PM. Reason: Made this a question.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Sure I have some ideas. But how about you attempt writing this a little more yourself before I jump in.

  3. #3
    &operator overload neolyn's Avatar
    Join Date
    Nov 2004
    Location
    Morgantown, WV
    Posts
    16
    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.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Well you're not looking very hard
    http://faq.cprogramming.com/cgi-bin/...&id=1073086407

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    A thourough discussion of B-trees with sample code.


    http://cis.stvincent.edu/carlsond/sw...ree/btree.html

  6. #6
    &operator overload neolyn's Avatar
    Join Date
    Nov 2004
    Location
    Morgantown, WV
    Posts
    16
    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.

  7. #7
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    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.

    The references at the bottom are out of date. A good source would be a Data Structures book.

    jc
    Mr. C: Author and Instructor

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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:
    Code:
    struct Node {
           Node* nodes[4];   // an empty space is NULL
           int       keys[3];     
           Node* parent;      // points to the node above
           int       numKeys; 
    };
    (You might try to find a better datastructure)

    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.

  9. #9
    &operator overload neolyn's Avatar
    Join Date
    Nov 2004
    Location
    Morgantown, WV
    Posts
    16
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. opening empty file causes access violation
    By trevordunstan in forum C Programming
    Replies: 10
    Last Post: 10-21-2008, 11:19 PM
  2. Formatting a text file...
    By dagorsul in forum C Programming
    Replies: 12
    Last Post: 05-02-2008, 03:53 AM
  3. Problem reading a delimited file into a binary tree
    By neolyn in forum C++ Programming
    Replies: 10
    Last Post: 12-09-2004, 07:51 PM
  4. file index update error
    By daluu in forum C Programming
    Replies: 1
    Last Post: 04-28-2003, 02:47 AM
  5. System
    By drdroid in forum C++ Programming
    Replies: 3
    Last Post: 06-28-2002, 10:12 PM