How to create an index file using B+ tree

Asked

Viewed 934 times

6

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

A 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 to save this index done in B+ tree in a file, and how to later recover the index to memory from this same file? If possible an implementation of this case or an example, to complement the explanation.

c filing-cabinet pointer índices tree

  • Could you give more information about the members of this structure, that is, what structures/types the pointers are pointing to? There are other structures involved?

2 answers

1

B+ trees are designed to work on disk.

The typical use of B+ trees includes the possibility of a huge number of keys (e.g. millions), typically having all the nodes in a file and only being loaded into memory the necessary pages.

In general each page usually has a fixed size (to make it easier to calculate the disk location where the page is) and the pointers tend to be "page numbers" referring to the disk file.

Thus befitting:

  • review the "Node" type so that it contains the full page contiguously, and with size fixed (example array of pairs (key, page numbers)).
  • convert pointers to page numbers

save/load page would be something like

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

1

I believe that any formatted file can do it by taking sheet in sheet and then implementing its own algorithm to create each separate object (you don’t intend 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" (Keys). With a DOM parser, you don’t even need to save the number of keys, the program calculates by the number of tags in the subtag. If you don’t like DOM/XML, you can also use JSON.

Browser other questions tagged c filing-cabinet pointer índices tree

You are not signed in. Login or sign up in order to post.