emufs/indice_bplus.c

   1 /** Arbol B+ */
   2 #include "tipo1.h"
   3 #include "tipo3.h"
   4 #include "indices.h"
   5 #include "indice_bplus.h"
   6
   7 /**#*#*#*#*#**#*#*#*#*#* Private prototypes*#*#*#*#*#**#*#*#*#*#**#*#*#*/
   8 int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node);
   9 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node);
  10 NODO_B_PLUS *b_plus_crearnodo(INDICE *idx);
  11 int b_plus_destruir_nodo(NODO_B_PLUS *nodo);
  12 int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode);
  13 int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query);
  14 int b_plus_insertar(INDICE *idx, INDEX_DAT *query);
  15 int b_plus_get_num_nodo(INDICE *idx);
  16 /**#*#*#*#*#**#*#*#*#*#*FIN PROTOTYPES*#*#*#*#*#**#*#*#*#*#**#*#*#*#*#*/
  17
  18 /** Crea un nuevo nodo y lo inicializa */
  19 NODO_B_PLUS *b_plus_crearnodo(INDICE *idx) {
  20
  21         NODO_B_PLUS *nodo = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS));
  22         if (nodo == NULL) return NULL;
  23         nodo->nivel = 0;
  24         nodo->cant_claves = 0;
  25
  26     /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */
  27         nodo->claves = (CLAVE*)malloc(idx->size_claves);
  28         nodo->hijos = (int*)malloc(idx->size_hijos);
  29         memset(nodo->claves,-1,idx->size_claves);
  30         memset(nodo->hijos,-1,idx->size_hijos);
  31
  32     return nodo;
  33 }
  34
  35 /** Crea el archivo indice B+ */
  36 int emufs_b_plus_crear(INDICE *idx) {
  37
  38         FILE *fp;
  39         NODO_B_PLUS *raiz;
  40         int error = 0;
  41
  42         /* Creamos el archivo que contendra el indice */
  43         fp = fopen(idx->filename, "w");
  44         PERR("Creando indice con nodo raiz");
  45         if (fp == NULL) {
  46                 PERR("Error al crear el archivo");
  47                 return -1;
  48         }
  49         fclose(fp);
  50
  51         /* Creamos el nodo raiz y lo guardamos el en indice */
  52         raiz = b_plus_crearnodo(idx);
  53         error = b_plus_grabar_nodo(idx,raiz,0);
  54
  55         /* Liberamos areas de memoria reservadas */
  56         free(raiz->claves);
  57         free(raiz->hijos);
  58         free(raiz);
  59
  60         return error;
  61 }
  62
  63
  64 /** Busca el nro de bloque donde se debe guardar un reg con clave X.
  65  *  Posibilidades: return 0 - Encontro un bloque potencial
  66  *                 return -1 - No hay clave, inserto clave de nuevo bloques
  67  *                 return 1 - Hubo falla de lectura de un nodo, Abortar
  68  */
  69 int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) {
  70
  71         int i,exitcode = 0;
  72         NODO_B_PLUS *nodo;
  73         nodo = b_plus_leer_nodo(idx,num_node);
  74         if (nodo == NULL) return 1;
  75         i = nodo->cant_claves - 1;
  76
  77         /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
  78         if (nodo->nivel == 0) {
  79         /* Vemos en que bloque deberia ir */
  80                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
  81                 if (i < 0) {
  82                         /* La clave es menor que todas, debo insertarla */
  83                         b_plus_destruir_nodo(nodo);
  84                         /*emufs_b_plus_insertar(idx,query);     */
  85                         return -1;
  86                 }
  87                 else {
  88                         /* Encontre un bloque potencial */
  89                         query->num_bloque = nodo->hijos[i];
  90                         b_plus_destruir_nodo(nodo);
  91                         return 0;
  92                 }
  93         }
  94         else {
  95                 /* Buscamos por donde descender al siguiente nivel */
  96                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
  97         i++;
  98         num_node = nodo->hijos[i];
  99                 b_plus_destruir_nodo(nodo);
 100                 exitcode = emufs_b_plus_get_bloque(idx,query,num_node);
 101                 return exitcode;
 102         }
 103 }
 104
 105 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node) {
 106
 107         /*int i = 0;*/
 108         FILE *fp;
 109         NODO_B_PLUS *memnode = b_plus_crearnodo(idx);
 110         char *disknode = (char*)malloc(idx->tam_bloque);
 111
 112         if (num_node < 0) {
 113                 PERR("Se intento leer nodo negativo!!\n");
 114                 exit(1);
 115         }
 116         if (disknode == NULL) return NULL;
 117         if (memnode == NULL) return NULL;
 118
 119     /* Open up file */
 120         fp = fopen(idx->filename, "r+");
 121         if (fp == NULL) {
 122                 free(disknode);
 123                 b_plus_destruir_nodo(memnode);
 124                 return NULL;
 125         }
 126
 127         /* Intentamos leer un nodo, sino podemos error! */
 128         fseek(fp, num_node*idx->tam_bloque, SEEK_SET);
 129         if (fread(disknode, idx->tam_bloque, 1, fp) != 1) {
 130                 free(disknode);
 131                 fclose(fp);
 132                 return NULL;
 133         }
 134         fclose(fp);
 135
 136         /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */
 137         memcpy(memnode,disknode,SIZE_B_PLUS_HEADER);
 138         memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves);
 139         memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER+idx->size_claves,idx->size_hijos);
 140         free(disknode);
 141
 142         /*printf("Dumping Node_%i\n",num_node);
 143         printf("Nivel: %i  Cant Claves: %i\n",memnode->nivel,memnode->cant_claves);
 144         printf("Claves:");
 145         for (i = 0; i < idx->size_claves/sizeof(CLAVE); ++i) printf(" %i",memnode->claves[i].i_clave);
 146         printf("\nHijos:");
 147         for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]);
 148         printf("\nEnd Dump\n"); */
 149
 150         return memnode;
 151
 152 }
 153
 154 int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node)
 155 {
 156         FILE *fp;
 157
 158         fp = fopen(idx->filename, "r+");
 159         if (fp == NULL) return -1;
 160
 161         fseek(fp,num_node*(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos),SEEK_SET);
 162         fwrite(nodo,SIZE_B_PLUS_HEADER,1,fp);
 163         fwrite(nodo->claves,idx->size_claves,1,fp);
 164         fwrite(nodo->hijos,idx->size_hijos,1,fp);
 165         fclose(fp);
 166
 167         return 0;
 168 }
 169
 170 int b_plus_destruir_nodo(NODO_B_PLUS *nodo)
 171 {
 172         free(nodo->claves);
 173         free(nodo->hijos);
 174         free(nodo);
 175         return 0;
 176 }
 177
 178 int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode)
 179 {
 180         /* locals */
 181         int minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
 182         int numbrother,j = 0;
 183         int es_interno = 1;
 184
 185         NODO_B_PLUS *brother = b_plus_crearnodo(idx);
 186         brother->nivel = fullnode->nivel; /* Idem nivel que el que se parte */
 187
 188         /* Si estoy en una hoja, la parte derecha del partido tendra minclaves+1 */
 189         /* pues el ancla se debe repetir ademas de subir */
 190         if (brother->nivel == 0) {
 191                 brother->cant_claves = minclaves+1;
 192                 es_interno = 0;
 193         }
 194         else brother->cant_claves = minclaves;
 195
 196         /* Copio las claves al brother derecho */
 197         for (j = 0; j < brother->cant_claves; ++j)
 198                 brother->claves[j] = fullnode->claves[j+minclaves+es_interno];
 199
 200         /* Copio los hijos ya sea para hoja o no hoja. */
 201         for (j = 0; j < brother->cant_claves+1; ++j)
 202                 brother->hijos[j] = fullnode->hijos[j+minclaves+es_interno];
 203
 204         /* Ahora me ocupo del nodo que se partio */
 205         fullnode->cant_claves = minclaves;
 206         /* Obtengo numero de nodo para brother y encadeno si es hoja */
 207         numbrother = b_plus_get_num_nodo(idx);
 208         if (fullnode->nivel == 0) fullnode->hijos[minclaves] = numbrother;
 209
 210         /* Ahora fixeamos el padre, apuntando al nuevo hijo */
 211         for (j = parent->cant_claves; j > ithchild; --j)
 212                 parent->hijos[j+1] = parent->hijos[j];
 213         parent->hijos[ithchild+1] = numbrother;
 214
 215         /* Idem pero subo la median key */
 216         for (j = parent->cant_claves-1; j >= ithchild; --j)
 217                 parent->claves[j+1] = parent->claves[j];
 218         parent->claves[ithchild] = fullnode->claves[minclaves];
 219         parent->cant_claves++;
 220
 221         /* Grabo los nodos en disco */
 222         b_plus_grabar_nodo(idx,fullnode,parent->hijos[ithchild]);
 223         b_plus_grabar_nodo(idx,brother,numbrother);
 224         b_plus_grabar_nodo(idx,parent,numparent);
 225
 226         b_plus_destruir_nodo(brother);
 227
 228         return 0;
 229 }
 230
 231
 232 int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query)
 233 {
 234     int i, num_nodo_hijo;
 235     NODO_B_PLUS *hijo;
 236
 237     i = nodo->cant_claves-1;
 238     if ( nodo->nivel == 0 ){
 239                 /* Muevo siempre el encadenamiento */
 240                 nodo->hijos[i+2] = nodo->hijos[i+1];
 241                 /* Ahora muevo las claves y sus punteros a bloques del dat */
 242         while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])){
 243             nodo->claves[i+1] = nodo->claves[i];
 244                         nodo->hijos[i+1] = nodo->hijos[i];
 245             i--;
 246         }
 247         nodo->claves[i+1] = query->clave;
 248                 nodo->hijos[i+1] = query->num_bloque;
 249         nodo->cant_claves++;
 250         b_plus_grabar_nodo(idx, nodo, num_nodo);
 251     } else {
 252         while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i]))
 253             i--;
 254         i++;
 255         num_nodo_hijo = nodo->hijos[i];
 256         hijo = b_plus_leer_nodo(idx, num_nodo_hijo);
 257         if ( hijo->cant_claves == idx->size_claves/sizeof(CLAVE) ) {
 258             b_plus_split_child(idx, num_nodo, nodo, i, hijo);
 259                         /* OjO Utilizo el menor pero con el proposito de clave > nodo->clave) */
 260             if (emufs_indice_es_menor(idx,nodo->claves[i],query->clave))
 261                 i++;
 262         }
 263                 if (hijo) b_plus_destruir_nodo(hijo);
 264                 hijo = b_plus_leer_nodo(idx, nodo->hijos[i]);
 265         b_plus_insert_nonfull(idx, hijo, nodo->hijos[i], query);
 266                 if (hijo) b_plus_destruir_nodo(hijo);
 267     }
 268
 269         return 0;
 270 }
 271
 272 int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query)
 273 {
 274     NODO_B_PLUS *raiz;
 275
 276     raiz = b_plus_leer_nodo(idx, 0);
 277     if ( raiz->cant_claves == idx->size_claves/sizeof(CLAVE) ) {
 278         NODO_B_PLUS *new_root = b_plus_crearnodo(idx);
 279         new_root->nivel = raiz->nivel + 1;
 280         new_root->hijos[0] = b_plus_get_num_nodo(idx);
 281         b_plus_grabar_nodo(idx, raiz, new_root->hijos[0]);
 282         b_plus_grabar_nodo(idx, new_root, 0);
 283             b_plus_split_child(idx, 0, new_root, 0, raiz);
 284         b_plus_insert_nonfull(idx, new_root, 0, query);
 285                 b_plus_destruir_nodo(new_root);
 286     } else
 287         {
 288                 b_plus_insert_nonfull(idx, raiz, 0, query);
 289         }
 290
 291         b_plus_destruir_nodo(raiz);
 292
 293     return 0;
 294 }
 295
 296 /** Busca una clave dentro del arbol e indica si existe o no
 297  *  Posibilidades: return 1 - Encontro la clave
 298  *                 return 0 - No encontro la clave
 299  *                 return -1 - Hubo falla de lectura de un nodo, Abortar
 300  */
 301 int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node)
 302 {
 303         int i,exitcode = 0;
 304         NODO_B_PLUS *nodo;
 305         nodo = b_plus_leer_nodo(idx,num_node);
 306         if (nodo == NULL) return -1;
 307         i = nodo->cant_claves - 1;
 308
 309         /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
 310         if (nodo->nivel == 0) {
 311         /* Vemos si esta la clave */
 312                 while ( i >= 0 && !emufs_indice_es_igual(idx,query->clave,nodo->claves[i])) i--;
 313                 if (i < 0)
 314                 {
 315                         b_plus_destruir_nodo(nodo);
 316                         return 0; /* No encontre la clave */
 317                 } else  {
 318                         /* Encontre la clave, guardo el nodo donde esta! */
 319                         query->num_bloque = num_node;
 320                         b_plus_destruir_nodo(nodo);
 321                         return 1;
 322                 }
 323         }
 324         else {
 325                 /* Buscamos por donde descender al siguiente nivel */
 326                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
 327         i++;
 328         num_node = nodo->hijos[i];
 329                 b_plus_destruir_nodo(nodo);
 330                 exitcode = b_plus_existe_clave(idx,query,num_node);
 331                 return exitcode;
 332         }
 333 }
 334
 335 int b_plus_cant_claves_nodo(INDICE *idx, int num_node)
 336 {
 337         NODO_B_PLUS *nodo =     b_plus_leer_nodo(idx,num_node);
 338         if (nodo == NULL) return -1;
 339         return nodo->cant_claves;
 340 }
 341
 342 /* Search_Type: 0 - Predecesor, 1 - Sucesor
 343    Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */
 344 int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type)
 345 {
 346         int i = 0, exitcode = 0;
 347         NODO_B_PLUS *child = NULL;
 348         NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);
 349         if (nodo == NULL) return -1;
 350         i = nodo->cant_claves - 1;
 351         if (nodo->nivel == 0) {
 352                 while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 353                 switch (search_type) {
 354                         /* Busco predecesor en la hoja */
 355                         case 0: if (i <= 0) exitcode = 0;
 356                                         else {
 357                                                 if (emufs_indice_es_igual(idx,nodo->claves[i],key))     {
 358                                                         prepostkey->clave = nodo->claves[i-1];
 359                                                         prepostkey->num_bloque = nodo->hijos[i-1];
 360                                                 } else {
 361                                                         prepostkey->clave = nodo->claves[i];
 362                                                         prepostkey->num_bloque = nodo->hijos[i];
 363                                                 }
 364                                                 exitcode = 1;
 365                                         }
 366                                         break;
 367                         /* Busco sucesor en la hoja */
 368                         case 1: if (i == nodo->cant_claves-1) {
 369                                                 /* Busco el primero del siguiente nodo del SQSET */
 370                                                 num_node = nodo->hijos[nodo->cant_claves];
 371                                                 if (num_node != -1) {
 372                                                         b_plus_destruir_nodo(nodo);
 373                                                         nodo = b_plus_leer_nodo(idx,num_node);
 374                                                         prepostkey->clave = nodo->claves[0];
 375                                                         prepostkey->num_bloque = nodo->hijos[0];
 376                                                         exitcode = 1;
 377                                                 }
 378                                                 else exitcode = -1; /* No hay mas */
 379                                         }
 380                                         else {
 381                                                 prepostkey->clave = nodo->claves[i+1];
 382                                                 prepostkey->num_bloque = nodo->hijos[i+1];
 383                                                 exitcode = 1;
 384                                         }
 385                                         break;
 386                 }
 387         } else {
 388                 /* Veo por que rama debo seguir buscando el pre o post */
 389                 while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 390                 if (search_type == 0) {
 391                         if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 392                         else {
 393                                 /* Busco primero por la rama derecha, sino por la izquierda */
 394                                 exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 395                                 if (exitcode == 0)
 396                                         exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i],prepostkey,search_type);
 397                         }
 398                         /* Handleo busqueda de clave menor o igual que todas */
 399                         if (exitcode == 0) exitcode = -1;
 400                 } else  {
 401                         /* Busco un sucesor como get bloque */
 402                         exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 403                 }
 404         }
 405
 406         /* Libero y devuelvo exitcode */
 407         b_plus_destruir_nodo(nodo);
 408         return(exitcode);
 409 }
 410
 411 int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int num_node)
 412 {
 413         NODO_B_PLUS *nodo;
 414         int i;
 415         INDEX_DAT auxquery;
 416         auxquery.clave = key;
 417
 418         /* Comienzo buscando la clave y obteniendo el nodo en donde esta */
 419         if (b_plus_existe_clave(idx,&auxquery,num_node) == 1) {
 420
 421                 /* Levanto el nodo y busco donde esta la clave */
 422                 /*printf("El reemplazar encontro la clave %i y en el nodo %i\n",auxquery.clave.i_clave,(int)auxquery.num_bloque);*/
 423                 nodo = b_plus_leer_nodo(idx,auxquery.num_bloque);
 424                 if (nodo == NULL) return -1;
 425                 i = nodo->cant_claves - 1;
 426
 427                 /* Busco la clave y reemplazo */
 428                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 429                 if (i < 0) return -1; /* Error, no esta la clave */
 430
 431                 /* Cheque por las dudas si es hoja o interno, aunque deberia ser hoja */
 432                 if (nodo->nivel > 0) {
 433                         nodo->claves[i] = query.clave;
 434                 } else {
 435                         nodo->claves[i] = query.clave;
 436                         nodo->hijos[i] = query.num_bloque;
 437                 }
 438                 b_plus_grabar_nodo(idx,nodo,auxquery.num_bloque);
 439                 b_plus_destruir_nodo(nodo);
 440                 return 0;
 441         }
 442         else return -1;
 443 }
 444
 445 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 446 {
 447         INDEX_DAT prepostkey;
 448         int i = 0,j = 0,minclaves = 0, nivel_mayor1 = 0,cant_claves_child = 0;
 449         int cant_claves_rsibling = 0, cant_claves_lsibling = 0, es_hoja = 0;
 450         int leftoffset = 0;
 451         NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);
 452         NODO_B_PLUS *node_y,*node_z,*mergenode,*siblingnode;
 453         if (nodo == NULL) { PERR("No leyo nodo bien"); return -1; }
 454         i = nodo->cant_claves - 1;
 455         minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
 456
 457         /* Si es hoja, borro directamente la clave. No se producira underflow
 458        pues lo asegura la recursividad del delete */
 459         if (nodo->nivel == 0) {
 460                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 461                 if (i < 0) return -1;
 462                 /* Encontre la clave en la pos i, la borro */
 463                 for (j = i; j < nodo->cant_claves-1; ++j) {
 464                         nodo->claves[j] = nodo->claves[j+1];
 465                         nodo->hijos[j] = nodo->hijos[j+1];
 466                 }
 467                 nodo->hijos[j] = nodo->hijos[j+1];
 468         nodo->cant_claves--;
 469
 470                 /* Grabo el nodo actualizado en disco */
 471                 b_plus_grabar_nodo(idx,nodo,num_node);
 472                 b_plus_destruir_nodo(nodo);
 473                 return 0;
 474         } else {
 475                 /* Me debo fijar si esta la clave en este nodo interno, sino busco */
 476                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 477                 if (i < 0) {
 478                         PERR("Entre caso 3 del eliminar");
 479                         /* No esta en este nodo interno, caso 3. Determino en que rama debe estar */
 480                         i = nodo->cant_claves - 1;
 481                         while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 482                 i++;
 483                 cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
 484                         if (cant_claves_child > minclaves) emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 485                         else {
 486                                 /* Vemos si estamos en caso 3a o 3b, mirando cant_claves de sus siblings */
 487                                 if (i < nodo->cant_claves) cant_claves_rsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
 488                                 if (i > 0) cant_claves_lsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i-1]);
 489                                 /*printf ("El sibling derecho si existe tiene %i claves\n", cant_claves_rsibling);
 490                                 printf ("El sibling izquierdo si existe tiene %i claves\n", cant_claves_lsibling);      */
 491                                 if (cant_claves_rsibling > minclaves) {
 492                                         /* El sibling derecho me dara una key mediante rotacion. Caso 3a */
 493                                         PERR("Entre caso 3a right sibling del eliminar");
 494                                         node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 495                                         node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 496                                         if (node_z->nivel == 0) es_hoja = 1;
 497                                         /* Le bajo la del padre a NodeY y muevo el apropiado child de NodoZ a NodoY */
 498                                         node_y->claves[cant_claves_child] = nodo->claves[i];
 499                                         node_y->hijos[cant_claves_child+1] = node_y->hijos[cant_claves_child];
 500                                         node_y->hijos[cant_claves_child+1-es_hoja] = node_z->hijos[0];
 501                                         node_y->cant_claves++;
 502                                         /* Le subo al padre desde el NodoZ, teniendo en cuenta si es hoja o no */
 503                                         nodo->claves[i] = node_z->claves[es_hoja];
 504                                         /* Hago shifting en el sibling para quitar la que subio */
 505                                         for (j = 0; j < node_z->cant_claves-1; ++j) {
 506                                                 node_z->claves[j] = node_z->claves[j+1];
 507                                                 node_z->hijos[j] = node_z->hijos[j+1];
 508                                         }
 509                                         node_z->hijos[j] = node_z->hijos[j+1];
 510                                 node_z->cant_claves--;
 511                                         /* Grabo los cambios */
 512                                         b_plus_grabar_nodo(idx,node_z,nodo->hijos[i+1]);
 513                                         b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]);
 514                                         b_plus_grabar_nodo(idx,nodo,num_node);
 515                                         b_plus_destruir_nodo(node_y);
 516                                         b_plus_destruir_nodo(node_z);
 517                                         /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */
 518                                         emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 519                                 }
 520                                 else if (cant_claves_lsibling > minclaves) {
 521                                                 /* el sibling izquierdo me dara una key mediante rotacion Caso 3a */
 522                                                 PERR("Entre caso 3a left sibling del eliminar");
 523                                                 node_z = b_plus_leer_nodo(idx,nodo->hijos[i]);
 524                                                 node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]);
 525                                                 if (node_z->nivel == 0) es_hoja = 1;
 526                                             /* Hago lugar en NodoZ para la clave que bajara desde el padre */
 527                                                 /* Muevo el ultimo y restantes claves/punteros */
 528                                                 j = node_z->cant_claves - 1;
 529                                                 node_z->hijos[j+2] = node_z->hijos[j+1];
 530                                         while (j >= 0){
 531                                         node_z->claves[j+1] = node_z->claves[j];
 532                                                         node_z->hijos[j+1] = node_z->hijos[j];
 533                                         j--;
 534                                         }
 535                                                 /* Hago la rotacion final segun sea hoja o no */
 536                                                 if (es_hoja) {
 537                                                         nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
 538                                                         node_z->claves[0] = node_y->claves[cant_claves_lsibling-1];
 539                                                         node_z->hijos[0] = node_y->hijos[cant_claves_lsibling-1];
 540                                                         node_y->hijos[cant_claves_lsibling-1] = node_y->hijos[cant_claves_lsibling]; /* cadena */
 541                                                         node_y->cant_claves--;
 542                                                         node_z->cant_claves++;
 543                                                 } else {
 544                                                         node_z->claves[0] = nodo->claves[i-1];
 545                                                         node_z->hijos[0] = node_y->hijos[cant_claves_lsibling];
 546                                                         nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
 547                                                         node_y->cant_claves--;
 548                                                         node_z->cant_claves++;
 549                                                 }
 550                                                 /* Grabo los cambios */
 551                                                 b_plus_grabar_nodo(idx,node_y,nodo->hijos[i-1]);
 552                                                 b_plus_grabar_nodo(idx,node_z,nodo->hijos[i]);
 553                                                 b_plus_grabar_nodo(idx,nodo,num_node);
 554                                                 b_plus_destruir_nodo(node_y);
 555                                                 b_plus_destruir_nodo(node_z);
 556                                                 /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */
 557                                                 emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 558                                         } else {
 559                                                 /* Caso 3b, debo bajar una clave y unificar con sibling disponible */
 560                                                 PERR("Entre caso 3b del eliminar");
 561                                                 if (cant_claves_lsibling == minclaves) {
 562                                                         PERR("Hago merge con sibling izquierdo");
 563                                                         leftoffset = 1;
 564                                                         siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i]);     /* Este es el root de la rama! */
 565                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-1]); /* Aca va todo */
 566                                                 } else {
 567                                                         PERR("Hago merge con sibling derecho");
 568                                                         leftoffset = 0;
 569                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i]);
 570                                                         siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 571                                                 }
 572
 573                                                 /* Bajo una clave del Padre Nodo a MergeNode y muevo todo lo SiblingNode a MergeNode */
 574                                                 /* Si es nivel mayor a 1, bajo clave, otherwise no bajo pues se repetiria */
 575                                                 nivel_mayor1 = 0;
 576                                                 if (nodo->nivel > 1) {
 577                                                         nivel_mayor1 = 1;
 578                                                         mergenode->claves[minclaves] = nodo->claves[i-leftoffset];
 579                                                 }
 580                                                 for (j = 0; j < minclaves; ++j) mergenode->claves[j+minclaves+nivel_mayor1] = siblingnode->claves[j];
 581                                                 for (j = 0; j < minclaves+1; ++j) mergenode->hijos[j+minclaves+nivel_mayor1] = siblingnode->hijos[j];
 582                                                 mergenode->cant_claves = minclaves*2+nivel_mayor1;
 583
 584                                                 /* Shifteo en el nodo padre NODO, para quitar la que bajo */
 585                                                 for (j = i-leftoffset; j < nodo->cant_claves-1; ++j) {
 586                                                         nodo->claves[j] = nodo->claves[j+1];
 587                                                         nodo->hijos[j+1] = nodo->hijos[j+2];
 588                                                 }
 589                                                 nodo->cant_claves--;
 590                                                 b_plus_grabar_nodo(idx,nodo,num_node);
 591                                                 b_plus_grabar_nodo(idx,mergenode,nodo->hijos[i-leftoffset]);
 592                                                 b_plus_destruir_nodo(mergenode);
 593                                                 b_plus_destruir_nodo(siblingnode);
 594                                                 /* Elimino recursivamente Key de la rama apropiada segun el Merge que se hizo */
 595                                                 emufs_b_plus_eliminar(idx,key,nodo->hijos[i-leftoffset]);
 596                                                 /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */
 597                                                 if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) {
 598                                                         /* Debo establecer como nueva raiz, el NodoY */
 599                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-leftoffset]);
 600                                                         b_plus_grabar_nodo(idx,mergenode,0);
 601                                                         truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 602                                                 }
 603                                                 /* End 3b */
 604                                                 }
 605                                         }
 606                 } else {
 607                         /* Esta en el nodo interno, caso 2 */
 608                         cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
 609                         if (cant_claves_child > minclaves) {
 610                                 PERR("Entre caso 2a del eliminar");
 611                                 /* Caso 2a, comienzo buscando la clave previa inmediata */
 612                                 b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0);
 613                                 /* La elimino recursivamente */
 614                                 emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i]); /* CHEAT */
 615                                 /* Remplazo mi clave key por la encontrada prekey */
 616                                 nodo->claves[i] = prepostkey.clave;
 617                                 b_plus_grabar_nodo(idx,nodo,num_node);
 618                                 /* Remplazo la otra instancia de key en una hoja seguro por prekey */
 619                                 emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]);
 620                         } else {
 621                                 cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
 622                                 if (cant_claves_child > minclaves) {
 623                                         PERR("Entre caso 2b del eliminar");
 624                                         /* Caso 2b, comienzo buscando la clave sucesor inmediata */
 625                                         b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1);
 626                                         /* La elimino recursivamente */
 627                                         emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i+1]); /* CHEAT */
 628                                         /* Remplazo mi clave key por la encontrada postkey */
 629                                         nodo->claves[i] = prepostkey.clave;
 630                                         b_plus_grabar_nodo(idx,nodo,num_node);
 631                                         /* Remplazo la otra instancia de key en una hoja seguro por postkey */
 632                                         emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]);
 633                                 } else {
 634                                         PERR("Entre caso 2c del eliminar");
 635                                         /* Caso 2c debo hacer un merge de la clave con hijo izq y der */
 636                                         node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 637                                         node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 638                                         /* Bajo la clave Key a NodoY y muevo todo lo de NodoZ a NodoY */
 639                                         /* Si es nivel mayor a 1, bajo clave pues no esta en NodoZ, otherwise no bajo */
 640                                         if (nodo->nivel > 1) {
 641                                                 nivel_mayor1 = 1;
 642                                                 node_y->claves[minclaves] = key;
 643                                         }
 644                                         for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+nivel_mayor1] = node_z->claves[j];
 645                                         for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+nivel_mayor1] = node_z->hijos[j];
 646                                         node_y->cant_claves = minclaves*2+nivel_mayor1;
 647                                         /* Shifteo en el nodo padre NODO, para quitar la que bajo */
 648                                         for (j = i; j < nodo->cant_claves-1; ++j) {
 649                                                 nodo->claves[j] = nodo->claves[j+1];
 650                                                 nodo->hijos[j+1] = nodo->hijos[j+2];
 651                                         }
 652                                         nodo->cant_claves--;
 653                                         b_plus_grabar_nodo(idx,nodo,num_node);
 654                                         b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]);
 655                                         b_plus_destruir_nodo(node_y);
 656                                         b_plus_destruir_nodo(node_z);
 657                                         /* Elimino recursivamente Key de NodeY, entrando por ese subtree */
 658                                         emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 659                                         /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */
 660                                         if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) {
 661                                                 /* Debo establecer como nueva raiz, el NodoY */
 662                                                 node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 663                                                 b_plus_grabar_nodo(idx,node_y,0);
 664                                                 truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 665                                                 b_plus_destruir_nodo(node_y);
 666                                         }
 667                                 }
 668                         }
 669                 }
 670                 /* Termine caso 2 o 3, libero el nodo */
 671                 b_plus_destruir_nodo(nodo);
 672                 return 0;
 673         }
 674
 675         return -1;
 676 }
 677
 678 int b_plus_get_num_nodo(INDICE *idx)
 679 {
 680         FILE *fp;
 681         int num;
 682
 683         fp = fopen(idx->filename, "ab");
 684         if (fp == NULL) return -1;
 685
 686     num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 687     fclose(fp);
 688     return num;
 689 }
 690
 691 CLAVE emufs_b_plus_obtener_menor_clave(INDICE *idx) {
 692
 693         CLAVE key;
 694         NODO_B_PLUS *node;
 695         int num_child = 0;
 696         node = b_plus_leer_nodo(idx,0);
 697         if (node == NULL) {
 698                 key.i_clave = -1;
 699                 return key;
 700         }
 701
 702         while (node->nivel > 0) {
 703                 /* Deciendo por la rama de mas hacia la izquierda */
 704                 if (node->cant_claves > 0) {
 705                         num_child = node->hijos[0];
 706                         b_plus_destruir_nodo(node);
 707                         node = b_plus_leer_nodo(idx,num_child);
 708                 }
 709                 else {
 710                         b_plus_destruir_nodo(node);
 711                         return key;
 712                 }
 713         }
 714
 715         /* Ahora estoy en la primer hoja del arbol, devuelvo la primer clave */
 716         key = node->claves[0];
 717         b_plus_destruir_nodo(node);
 718
 719         return key;
 720 }
 721
 722 CLAVE emufs_b_plus_obtener_mayor_clave(INDICE *idx) {
 723
 724         CLAVE key;
 725         NODO_B_PLUS *node;
 726         B_PLUS_KEYBUCKET *bucket = NULL;
 727         int num_child = 0, cant_claves = 0;
 728         node = b_plus_leer_nodo(idx,0);
 729         if (node == NULL) {
 730                 key.i_clave = -1;
 731                 b_plus_destruir_nodo(node);
 732                 return key;
 733         }
 734
 735         cant_claves = node->cant_claves;
 736         while (node->nivel > 0) {
 737                 /* Deciendo por la rama de mas hacia la derecha */
 738                 if (node->cant_claves > 0) {
 739                         num_child = node->hijos[cant_claves];
 740                         b_plus_destruir_nodo(node);
 741                         node = b_plus_leer_nodo(idx,num_child);
 742                         cant_claves = node->cant_claves;
 743                 }
 744                 else {
 745                         b_plus_destruir_nodo(node);
 746                         return key;
 747                 }
 748         }
 749
 750         /* Ahora estoy en la ultima hoja del arbol, devuelvo la ultima clave */
 751         bucket = idx->padre->obtener_claves_raw(idx->padre,node->hijos[cant_claves-1]);
 752         key = bucket->claves[bucket->cant_keys-1];
 753         free(bucket->claves);
 754         free (bucket);
 755         b_plus_destruir_nodo(node);
 756
 757         return key;
 758 }
 759
 760 CLAVE emufs_b_plus_obtener_sig_clave(INDICE *idx, CLAVE key) {
 761
 762         INDEX_DAT query;
 763         int i = 0;
 764         query.clave = key;
 765
 766         /* Si aun no tengo un array, obtengo uno */
 767         if (idx->keybucket == NULL) {
 768                 /* Busco el ancla para esta key */
 769                 emufs_b_plus_get_bloque(idx,&query,0);
 770                 idx->keybucket = idx->padre->obtener_claves_raw(idx->padre,query.num_bloque);
 771                 /* Dejo el el iterador listo para la leer el siguiente, pues puede estar por el medio */
 772                 i = idx->keybucket->cant_keys - 1;
 773                 while (i >= 0 && emufs_indice_es_menor(idx,key,idx->keybucket->claves[i])) --i;
 774                 i++;
 775                 idx->keybucket->current_key = i;
 776                 /*printf ("\nLevante bloque nro: %i y obtuve un bucket con %i keys\n",query.num_bloque,idx->keybucket->cant_keys);
 777                 printf ("La primera clave del bucket que devuelvo es: %i\n",idx->keybucket->claves[0].i_clave);                                         */
 778         }
 779
 780         /* Si me pide el siguiente de una clave que no esta en este bucket, pido un nuevo! */
 781         if (idx->keybucket != NULL) {
 782                 i = idx->keybucket->cant_keys - 1;
 783                 while (i >= 0 && !emufs_indice_es_igual(idx,key,idx->keybucket->claves[i])) --i;
 784                 if (i < 0) {
 785                         /* Debo obtener un nuevo bucket pues este debe ser de otro query viejo */
 786                         free(idx->keybucket->claves);
 787                         free(idx->keybucket);
 788                         emufs_b_plus_get_bloque(idx,&query,0);
 789                         idx->keybucket = idx->padre->obtener_claves_raw(idx->padre,query.num_bloque);
 790                         /* Dejo el el iterador listo para la leer el siguiente, pues puede estar por el medio */
 791                         i = idx->keybucket->cant_keys - 1;
 792                         while (i >= 0 && emufs_indice_es_menor(idx,key,idx->keybucket->claves[i])) --i;
 793                         i++;
 794                         idx->keybucket->current_key = i;
 795                         /*printf ("La primera clave del bucket que devuelvo es: %i\n",idx->keybucket->claves[0].i_clave);*/
 796                 }
 797         }
 798
 799         /* Veo si ya devolvi la ultima */
 800         if (idx->keybucket != NULL)
 801                 if (idx->keybucket->current_key == idx->keybucket->cant_keys) {
 802                         /* Debo obtener un nuevo bucket de claves */
 803                         if (b_plus_buscar_prepost(idx,idx->keybucket->claves[0],0,&query,1) != -1) {
 804                                 free(idx->keybucket->claves);
 805                                 free(idx->keybucket);
 806                                 idx->keybucket = idx->padre->obtener_claves_raw(idx->padre,query.num_bloque);
 807                                 /*printf ("\nLevante bloque nro: %i y obtuve un bucket con %i keys\n",query.num_bloque,idx->keybucket->cant_keys);
 808                                 printf ("La primera clave del bucket que devuelvo es: %i\n",idx->keybucket->claves[0].i_clave);*/
 809                         }
 810                         else {
 811                                 /* No hay mas o hubo error, cortamos */
 812                                 key.i_clave = -1;
 813                                 return key;
 814                         }
 815                 }
 816
 817         /* Devuelvo el siguiente elemento del array solo si es mayor. Si es menor, lo skipeo */
 818         if (idx->keybucket->current_key < idx->keybucket->cant_keys) {
 819                 i = idx->keybucket->current_key;
 820                 idx->keybucket->current_key++;
 821                 return (idx->keybucket->claves[i]);
 822         }
 823         else return key;
 824 }