How to create an index file using tree B +

Question

How to create an index file using tree B +

Navigation

#1 by (1 votes)
#2 by (1 votes)

6

I have a B + tree that acts as the index of a data file. This index should be saved to an index file.

The struct node or node of the B + tree is:

typedef struct node 
{
    void ** pointers;
    int * keys;
    struct node * parent;
    bool is_leaf;
    int num_keys;.
} node;

How can I save this index made in B + tree to a file, and how to later retrieve the index to memory from this same file? If possible an implementation of this case or an example, to complement the explanation.

c ponteiro arquivo

asked by anonymous 16.12.2014 / 17:32

2 answers

How to list and monitor the app's that are installed and / or in use? How to make my default program to open a file type?

score 1 · Answer 1

I believe that any formatted file can do it by taking sheet inside sheet and then implementing its own algorithm to create each separate object (you do not want to save the record, right?). Example: (!strcmp(objeto.tagName,"tree"))? instancia_hipotetica.is_leaf = false, instancia_hipotetica.is_leaf = true; . I recommend the DOM system ( eXpat - XML).

Edit - from what I've seen, you're using keys. With a DOM parser, you do not even have to save the number of keys, the program computes by the number of tags in the subtag. If you do not like DOM / XML, you can also use JSON.

score 1 · Answer 2

B + trees are designed to work on disk.

The typical use of B + Trees contemplates the possibility of huge amounts of keys (eg millions), typically having all nodes in a file and only loading the required pages into memory.

In general, each page is usually fixed in size (to make it easier to calculate where the page is located on the disk) and the pointers tend to be "page numbers" for the file on disk.

So it was convenient:

review the type "node" so that it contiguously contains the entire page, and size (example array of pairs (key, page numbers)).
convert pointers into page numbers

record / load page would be something like

offset = tamanho x numeroDePagina
fseek(ficheir,offset, 0)
fread ou fwrite (página, sizeof(node),1 ,ficheiro)