Mover dentro de uma árvore em C- MapReduce - B plus Tree

[Tharso]

Faz um tempo já que me interessei pelo paradigma MapReduce que foi desenvolvido pelo Google. Comecei então a dar uma lida nos frameworks MapReduce para multi-core, e encontrei Metis, que está desenvolvido em C. Comecei a fazer algumas pequenas mudanças no código de acordo com o objetivo que eu queria.

Utilizando um programa de Contar Palavras, Metis paralelamente usando threads por cores, vai armazenando cada palavra em uma estrutura de dados do tipo tabela Hash, onde cada entrada da tabela hash possui uma árvore B+tree. A maioria das outras soluções que eu havia encontrado utilizam arrays nas entradas da tabela hash.

A B+Tree é uma variação da árvore B. Em uma árvore-B+, contrastando com uma árvore-B, todos os dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista enlaçada para efectuar consultas facilmente.

Uma das modificações que eu estava tentando fazer é em cada entrada da tabela hash, onde existe uma b+tree, pegar todas as chaves armazenadas ali e serializo elas, ou seja, meto em um array, para pode guardar em um arquivo, já que a idéia de guardar toda a estrutura não me interessa, só preciso dos dados.

Para isso eu preciso recorrer toda a árvore e ir trazendo as chaves e os valores nela armazenada. Eu posso recorrer ela de 2 maneiras, a primeira é como uma árvore normal, a segunda é utilizando a lista enlaçada entre as folhas, que me parece muito mais interessante.

O problema é que nesse momento eu não estou sabendo como saltar de um nó para o outro através do ponteiro da lista enlaçada, ou seja, eu só consigo imprimir os valores do nó mais a esquerda, e não consigo imprimir os outros.

A estrutura de dados que a aplicação utiliza é essa:

typedef struct {
    int map_rows;
    int map_cols;
    htable_entry_t **mbks;
} mapper_t;

typedef struct {
    btree_t v;
} htable_entry_t;

typedef struct {
    uint64_t nkeys;
    short nlevel;
    btnode_t *root;
} btree_t;

typedef struct {
    short nkeys;
    void *parent;
    keyvals_t arr[2 * order + 2];    //order é igual 3
    void *next;
} btnode_t;

typedef struct {
    void *key;
    void **vals;
    unsigned len;
    unsigned alloc_len;
    unsigned hash;
} keyvals_t;

A função que eu estava desenvolvendo para percorrer a árvore é essa

int
H_table_entry_Verify()
{
    block_key unique_key;
    int i,j;
    for(j=0;j<mapper.map_rows;j++)
    {
        for(i=0;i<mapper.map_cols;i++){
             htable_entry_t *bufferHKey = &mapper.mbks[j][i];
             btree_t *bptree = &mapper.mbks[j][i].v;
             btnode_t *node = bptree->root;
             printf("btreeroot %d btreenkeys %d btreenlevel %d Nodenkeys %d Nodenext %d NodeParent %d\n",bptree->root, bptree->nkeys, bptree->nlevel,           node->nkeys, node->next, &node->parent);

            for(int u = 0; u <= bptree->nlevel; u++){
                btnode_t *node = bptree->root;
                  for(int h = 0; h < node->nkeys; h++){
                       printf("%s -- ",node->arr[h].key);
                         if(h==node->nkeys -1)
                            printf("\n\n");
                }
            }
          }
        }
    return 1;
}

Com essa função eu consigo acessar a entrada hash desejada, descer pela árvore e imprimir as chaves que estão no nó mais a esquerda. Dai em diante eu não sei como avançar para os outros nós, onde estão as outras chaves.

Alguém sabe como eu posso fazer isso, como manipulo os ponteiros para saltar ao próximo nó? Teoricamente btnode_t.next é quem tem esse ponteiro.