Recorrido narrado

Costos con la memoria en la cuenta

Con n claves y nodos de m claves:

	Árbol binario balanceado	B-tree
altura	unos log₂ n	unos log en base m de n
nodos visitados al buscar	log₂ n	log en base m de n
comparaciones al buscar	log₂ n	log₂ n (búsqueda binaria dentro de cada nodo)

Las comparaciones son las mismas, O(log n) en el peor caso. Lo que cambia es cuántos nodos distintos se visitan: cada uno es un acceso a memoria o a disco.

Con m = 1000 y n = mil millones: log₁₀₀₀ 10⁹ = 3. Con la raíz siempre en memoria, una búsqueda lee 2 o 3 páginas.

Su fila en la tabla de costos

El B-tree, en las columnas de conjunto y diccionario de la ruta. Como el árbol balanceado, su garantía no depende del orden de las claves; lo que lo distingue es cuántos nodos distintos visita.

Representación	buscar(k)	insertar(k)	borrar(k)	mínimo	sucesor(k)	rango(a, b) con r resultados
B-tree	O(log n) en el peor caso; unos log en base m de n nodos visitados	O(log n) en el peor caso	O(log n) en el peor caso	O(log n)	O(log n)	O(log n + r)