Cota inferior

El costo de búsqueda de $O(\log_B \frac{N}{M})$ es óptimo si se busca mediante comparaciones. Demostraremos la cota inferior usando el método del adversario. El modelo es que el algoritmo sabe todo el tiempo el rango del input ordenado en el cual puede estar la clave $x$ que se busca. Si inicialmente partimos con la memoria llena de datos, éstos particionan el input en $M+1$ zonas, y las comparaciones (gratis) con $x$ le permiten al algoritmo establecer que $x$ está en una de las $M+1$ zonas. El adversario se encargará de que se busque una clave que cae en la partición más larga. Esta debe medir al menos $\frac{N}{M+1}$, pues si todas midieran menos, no podrían sumar $N$. De modo que comenzamos con un rango de ese tamaño.

Cada vez que el algoritmo lee un bloque de $B$ elementos de disco, lee hasta $B$ nuevas claves con las que comparar. El algoritmo y la estructura de datos eligen qué claves son esas. Nuevamente, particionan el rango actual que conoce el algoritmo en $B+1$ subrangos, uno de los cuales pasa a ser el nuevo rango después de las comparaciones. El adversario siempre elige que $x$ esté en el mayor de los rangos, de modo que el rango se reduce en un factor de a lo más $B+1$ por cada lectura. Se deduce que el algoritmo necesita leer al menos $\log_{B+1} \frac{N}{M+1}$ páginas de disco para poder reducir el rango a tamaño 1 y poder responder correctamente.

Con modificaciones simples, el árbol $B$ puede recuperar un rango de elementos, es decir, todos los $occ$ objetos cuyas claves estén en un intervalo $[x_1,x_2]$, en tiempo $O(\log_B \frac{N}{M} + occ/B)$, lo cual es nuevamente óptimo.