Búsqueda

La búsqueda en un B+ es similar a la busqueda de un BTree⁵, la única diferencia con éste último es que el nodo que contiene el apuntador al registro, en el B+, debe ser un nodo hoja.

Suponiendo que deseamos encontrar la llave k, entonces el algoritmo inicia la búsqueda en el nodo raíz y compara todos los elementos llaves, en orden ascendente, con k hasta que encontremos una llave mayor o terminemos de comparar todas las llaves sin encontrar la llave mayor. Para esta tarea implantamos una funcón llamada node_search, la cual tiene 2 entradas: el nodo y k, y regresa el índice donde podría estar la llave, en realidad este número es el índice de la máxima llave menor o igual a k. Por ejemplo, si el nodo tuviese las llaves (5, 10, 12, 17, 20) y ${\bf k}= 15$, entonces node_search nos indicaría que el tercer elemento (12) es la máxima llave menor o igual a 15, lo que establece que si el nodo es una rama es que posiblemente 15 se encuentre en el tercer subárbol hijo de nodo. En C esta función queda implantada como:

/* Regresa el menor entero j    */ 
/* tal que k <= key(p,j)        */
/* [ABRIL-97]                   */
/* AMILCAR MENESES VIVEROS      */
int nodesearch(node *p, Bkey k)
{
   int i; 

   for (i=0; i < (p->nKeys); i++) 
     if ( cmpkey(k,p,i) <= 0 )
         return i; 

   return i; 
}

Esta función incluye, a su vez, a la función cmpkey(), que compara a la llave k, con el i-ésimo elemento del nodo p, si k es menor regresa -1, 0 si es igual y 1 si es mayor.

Retomando la filosofía de node_seach escribimos una función que se encarga de buscar, en el B+, la hoja y posición donde posiblemente se encuentre k, esto és, la posición correspondiente con la máxima llave menor o igual que k. Esto tiene sus ventajas para otras operaciones que se realizan en el árbol. Así, la función search_leaf tiene como valores de entrada el nodo donde se inicia la búsqueda, la llave k, y un apuntador a la posición en el nodo; y regresa el apuntador al nodo hoja donde debe estar k. Esta función opera de la siguiente forma: busca el índice i correspondiente a k en el nodo, una vez obtenido este valor, se pregunta si el nodo es una hoja, si lo és, entonces se coloca a i como valor de la posición y se regresa el apuntador de este nodo; en caso de ser una rama, entonces se regresa el valor de la misma función, pero ahora se inyecta el i-ésimo árbol-hijo como valor de entrada:

 
/* Busca la hoja y posicion donde se debe estar la llave k, */
/* regresa NULL si el arbol esta vacio                      */ 
/* [ABRIL-97]                                               */
/* AMILCAR MENESES VIVEROS                                  */ 
node *search_leaf(node *p, Bkey k, int *position)
{
   int i; 

   if (p==NULL) {
      *position = -1; 
      return NULL; 
   }
   i = nodesearch(p, k); 
   if (isleaf(p)==BTRUE) {
      *position = i; 
      return p; 
   }
   return (search_leaf(p->an[i], k, position)); 
}

De esta forma cuando deseamos buscar un elemento en el árbol llamamos a la función search_leaf y comparamos que el valor del índice sea menor que el orden del árbol --esto se debe a que el arreglo de llaves tiene un elemento menos que el orden del árbol-- y comparamos a k con la i-ésima llave de la hoja encontrada.

void search(node *root, Bkey k)
{
   node *ns; 
   Bregister *r; 
   int i; 
   
   if ((ns=search_leaf(root,k,&i))==NULL) {
        printf("\n El elemento"); printf(FFkey,k); printf("no se encontro");
   }
   else if ( i < (ORDER-1) && k == (ns->ak[i]) ) { 
        r = ns->ap[i]; 
        printf("\n Llave  : "); printf(FFkey, PKeyNode(r));
        printf("\n Nombre : %s", r->nombre); 
        printf("\n Edad   : %d", r->edad); 
   }
   else printf("\n El elemento FKey no se encontro", k); 

   printf("\n Presione cualquier tecla para continuar ...");
   getchar(); 
}