Inserción

Ya se ha mencionado que el B+ es un árbol balanceado, cuando se le agregan elementos se debe mantener este balance, esto es, cuando un nodo se llena se divide en 2 partes, las llaves se distribuyen en mitades y el elemento medio se inserta como una llave más en el nodo padre. Si esto nodo no existe, entonces se crea un nuevo nodo, se inserta el elemento y se actualiza la dirección del nodo raíz. En caso de que el nodo si exista y esté lleno, se le aplica el mismo método de división.

El primer paso en la inserción de un registro es encontrar la hoja y posición donde debe quedar el nuevo registro --este proceso se realiza con la fución ya dicutida search_leaf-- y verificamos el número de elementos en el nodo. Si el número de elementos es menor que el orden del árbol, entonces insertamos el registro con la función node_register que explicaremos más adelante. En caso contrario, si el número de elementos es igual al orden del nodo, entonces dividimos el nodo e insertamos el nuevo registro en el nodo que le corresponda (en la división), conectamos las nuevas hojas, y actualizamos la raíz del árbol. La función queda de la siguiente forma:

 
/* Inserta en el arbol un nuevo registro */
/* [ABRIL-97]                            */ 
/* AMILCAR MENESES VIVEROS               */ 
node *insert_register(node *root, Bkey k, Bregister *r)
{
   int i, f; 
   Bkey mkey; 
   node *ph1, *ph2, *rf; 

   rf = root; 
   if ((ph1=search_leaf(root,k,&i))==NULL) { 
      printf("\n Error!, no existe arbol\n"); exit(1); 
   }

   if (ph1->nKeys < (ORDER-1)) insnoderegister(ph1,i,r,k); 
   else {
      ph2 = divide(ph1, k, i, &f, &mkey);
      i = nodesearch(ph2, k); 
      insnoderegister(ph2, i, r, k); 
      conect(ph1, ph2); 
      rf = search_root(ph1); 
   }

   return rf; 
}

Se aprecia que la función insert_register tiene 3 parámetros de entrada: el nodo raíz root, la llave k y el apuntador al registro correspondiente r. Además regresa el apuntador a la raíz del árbol, esto es porque al conservar el balance del árbol, la raíz puede puede cambiar si se altera la profundidad del B+. La función insert_register se auxilia de 5 rutinas: insnoderegister, divide, nodesearch, concect y search_root que explicamos a continuación, exepto nodesearch que ya se ha discutido previamente.