super test, cargando 10000 registros con claves random y el arbol se arma, al parecer...

[z.facultad/75.06/emufs.git] / emufs / indice_bplus.c

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 06d3ee1f07416ee271ccebbd1dc4571fd2de4d9b..274fe798b99900c97af467d93c5b91117ac6cda6 100644 (file)
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -79,7 +79,7 @@ int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) {
                if (i < 0) {
                        /* La clave es menor que todas, debo insertarla */
                        b_plus_destruir_nodo(nodo);                     
-                       emufs_b_plus_insertar(idx,query);                       
+                       /*emufs_b_plus_insertar(idx,query);     */
                        return -1;
                }
                else {
@@ -435,9 +435,10 @@ int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query)
 
 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 {
-       INDEX_DAT prekey;
+       INDEX_DAT prepostkey;
        int i = 0,j = 0,minclaves = 0, cant_claves_child = 0;
-       NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);             
+       NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);
+       NODO_B_PLUS *hijoder,*hijoizq;
        if (nodo == NULL) return -1;
        i = nodo->cant_claves - 1;
        minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
@@ -469,21 +470,39 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
                        cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
                        if (cant_claves_child > minclaves) {
                                /* Caso 2a, comienzo buscando la clave previa inmediata */
-                               b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prekey,0);
+                               b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0);
                                /* La elimino recursivamente */
-                               emufs_b_plus_eliminar(idx,prekey.clave,0);
+                               emufs_b_plus_eliminar(idx,prepostkey.clave,0);
                                /* Remplazo mi clave key por la encontrada prekey */
-                               nodo->claves[i] = prekey.clave;
+                               nodo->claves[i] = prepostkey.clave;
                                /* Remplazo la otra instancia de key en una hoja seguro por prekey */
-                               /*emufs_b_plus_reemplazar_clave(idx,key,prekey.clave);*/
-                       } else {                                
+                               emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave);
+                       } else { 
                                cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
                                if (cant_claves_child > minclaves) {
-                                       /* Caso 2b */
-                                       
+                                       /* Caso 2b, comienzo buscando la clave previa inmediata */
+                                       b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1);
+                                       /* La elimino recursivamente */
+                                       emufs_b_plus_eliminar(idx,prepostkey.clave,0);
+                                       /* Remplazo mi clave key por la encontrada postkey */
+                                       nodo->claves[i] = prepostkey.clave;
+                                       /* Remplazo la otra instancia de key en una hoja seguro por postkey */
+                                       emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave);
                                } else {
-                                       /* Caso 2c */
-                               
+                                       /* Caso 2c debo hacer un merge de la clave con hijo izq y der */
+                                       node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
+                                       node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
+                                       /* Bajo la clave Key a NodoY y muevo todo lo de NodoZ a NodoY */
+                                       node_y->claves[minclaves] = nodo->claves[i];
+                                       for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+1] = node_z->claves[j];
+                                       for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+1] = node_z->hijos[j];
+                                       b_plus_destruir_nodo(z);                                                                                
+                                       /* Shifteo en el nodo padre NODO, para quitar la que bajo */
+                                       for (j = i; j < nodo->cant_claves-1; ++j) {
+                                               nodo->claves[j] = nodo->claves[j+1];
+                                               nodo->hijos[j+1] = nodo->hijos[j+2];
+                                       }
+                                       }
                                }
                        }                       
                }