GUÍA 11-11-26 Estructuras de Datos

CN122 · miércoles 11/11/2026 · 13:00-14:15 · Sesión 27

Árboles B y tablas hash

ÁRBOLES B

Un árbol B de orden m es un árbol balanceado donde cada nodo puede contener hasta m−1 claves y tener hasta m hijos. Todas las hojas están al mismo nivel.

POR QUÉ EXISTEN

Fueron diseñados para almacenamiento en disco. Leer del disco cuesta miles de veces más que leer de RAM, y se lee por bloques. Si un nodo ocupa exactamente un bloque, cada lectura trae cientos de claves de una vez.

Un árbol binario con un millón de claves tiene altura 20: veinte accesos a disco. Un árbol B de orden 100 tiene altura 3. Esa diferencia es la razón de que todas las bases de datos y sistemas de archivos usen árboles B.

OPERACIONES

• Búsqueda: dentro de cada nodo se busca entre las claves y se baja por el hijo correspondiente.
• Inserción: siempre en una hoja; si se desborda, el nodo se divide y la clave media sube al padre.
• Eliminación: si un nodo queda con muy pocas claves, se fusiona con un hermano o le pide prestada una clave.

B+ FRENTE A B

En un B+ todos los datos están en las hojas y las hojas están enlazadas entre sí. Eso permite recorridos por rango eficientes, que es lo que hace un SELECT con BETWEEN. Es la variante que realmente usan las bases de datos.

TABLAS HASH

Una función hash convierte la clave en un índice de arreglo. El acceso es O(1) en promedio: no se compara nada, se calcula la posición.

COLISIONES

• Encadenamiento — cada celda guarda una lista de los elementos que colisionan. Simple y robusto.
• Direccionamiento abierto — se busca otra celda libre por sondeo lineal, cuadrático o doble hash.
• Factor de carga — al pasar de 0.7 aproximadamente conviene redimensionar y rehashear todo.

HASH CONTRA ÁRBOL

La tabla hash gana en búsqueda exacta; el árbol gana cuando se necesita orden, recorrido por rango o el mínimo y el máximo. La tabla hash no tiene noción de orden y esa es su única limitación seria.

PRÁCTICA

Implementar una tabla hash con encadenamiento y comparar sus tiempos de búsqueda contra los del ABB.