4 - Búsqueda en un árbol B

La búsqueda en un B-Tree aprovecha el arreglo ordenado de claves dentro de cada nodo y el alto factor de ramificación para reducir lecturas de disco. En cada nivel se revisan las claves del nodo y, si no hay coincidencia, se elige uno de sus hijos. El proceso es similar a un BST pero con múltiples llaves y sin sobrepasar la altura de 2 o 3 niveles en muchos casos.

4.1 Recorrido por claves del nodo

En cada nodo se recorre el arreglo de claves ordenadas hasta encontrar:

• Una coincidencia exacta: la búsqueda termina.
• Una clave mayor que la buscada: se decide descender al hijo anterior.
• El final del arreglo: se desciende al último hijo.

El recorrido puede implementarse con búsqueda lineal (simple y eficiente para pequeños t) o binaria para reducir comparaciones si el nodo es grande.

4.2 Búsqueda en subárboles

Cuando la clave no está en el nodo actual y el nodo no es hoja, se sigue el puntero al hijo que abarca el rango adecuado. Los invariantes del árbol B aseguran que el subárbol contiene el rango correcto de claves.

• Rangos: hijoi contiene todas las claves mayores a clavei-1 y menores a clavei.
• Lecturas de bloque: cada descenso suele implicar una lectura de disco; por eso se busca minimizar la altura.
• Control de nulls: los punteros a hijos solo existen en nodos internos; en hojas se omite el descenso.

4.3 Caso base: nodo hoja

Si el nodo es hoja, no hay más hijos a los que descender. Tras recorrer sus claves:

• Si se halló la clave, se devuelve el índice o el valor asociado.
• Si no se halló, la clave no está en el árbol.

En un B+ las hojas suelen contener también punteros a registros y enlaces a hojas vecinas, pero la lógica de búsqueda permanece igual.

4.4 Complejidad de la búsqueda

La complejidad depende de la altura del árbol y del costo de recorrer las claves de un nodo:

• Altura: O(log_t n), donde t es el grado mínimo; en la práctica la altura es muy baja.
• Dentro del nodo: O(t) comparaciones si es lineal, O(log t) si se usa búsqueda binaria.
• Costo I/O: cada nivel suele implicar una lectura de bloque, por lo que minimizar la altura tiene mayor impacto que optimizar comparaciones.

Con valores típicos (t entre 50 y 200 en discos), la altura se mantiene en 2 o 3, haciendo que la búsqueda sea prácticamente constante en número de accesos a disco.

/* Busqueda en B-Tree (version lineal por nodo) */
int btree_buscar(BTreeNode *nodo, int clave) {
  int i = 0;
  while (i < nodo->cuenta && clave > nodo->claves[i]) {
    i++;
  }
  if (i < nodo->cuenta && clave == nodo->claves[i]) {
    return 1; /* encontrado */
  }
  if (nodo->esHoja) {
    return 0; /* no esta */
  }
  return btree_buscar(nodo->hijos[i], clave);
}