Solución:
Los árboles AVL están pensados para uso en memoria, donde el acceso aleatorio es relativamente barato. Los árboles B son más adecuados para el almacenamiento con respaldo en disco, porque agrupan una mayor cantidad de claves en cada nodo para minimizar la cantidad de búsquedas requeridas por una operación de lectura o escritura. (Esta es la razón por la que los árboles B se utilizan a menudo en sistemas de archivos y bases de datos, como SQLite).
Tanto el árbol AVL como el árbol B son similares en el sentido de que son estructuras de datos que, a través de sus requisitos, hacen que la altura de sus respectivos árboles se minimice. Esta “brevedad” permite realizar la búsqueda en tiempo O (log n), ya que el mayor número posible de lecturas corresponde a la altura del árbol.
5
/
3 7
/ /
1 6 9
Este es un árbol AVL y es un árbol de búsqueda binario en su núcleo. Sin embargo, es autoequilibrante, lo que significa que a medida que agrega elementos al árbol, se reestructurará para mantener una altura lo más uniforme posible. Básicamente, no permitirá ramas largas.
Un árbol B también hace esto, pero a través de un esquema de reequilibrio diferente. Es un poco complicado de escribir, pero si buscas en Google “animación de árbol B”, hay algunos applets realmente buenos que explican bastante bien un árbol B.
Son diferentes en que un árbol AVL se implementa con soluciones basadas en memoria en mente, mientras que un árbol B se implementa con soluciones basadas en disco en mente. Los árboles AVL no están diseñados para contener colecciones masivas de datos, ya que utilizan la asignación de memoria dinámica y punteros al siguiente bloque de memoria. Obviamente, podríamos replicar la funcionalidad del árbol AVL con ubicaciones de disco y punteros de disco, pero sería mucho más lento porque aún tendríamos una cantidad significativa de lecturas para leer un árbol de un tamaño muy grande.
Cuando la colección de datos es tan grande que no cabe en la memoria, la solución es un árbol B (hecho interesante: no hay consenso sobre lo que realmente significa la “B”). Un árbol B contiene muchos elementos secundarios en un nodo y muchos indicadores del nodo secundario. De esta manera, durante una lectura de disco (que puede tardar alrededor de 10 ms en leer un solo bloque de disco), se devuelve la cantidad máxima de datos de nodo relevantes, así como punteros a bloques de disco de “nodo hoja”. Esto permite que el tiempo de recuperación de datos se amortice en log (n) tiempo, lo que hace que el árbol B sea especialmente útil para implementaciones de recuperación de bases de datos y grandes conjuntos de datos.
Un árbol AVL es un árbol de búsqueda binario autoequilibrado, equilibrado para mantener la altura O (log n).
Un árbol B es un árbol equilibrado, pero no es un árbol binario. Los nodos tienen más hijos, lo que aumenta el tiempo de búsqueda por nodo, pero reduce la cantidad de nodos que la búsqueda debe visitar. Esto los hace buenos para árboles basados en disco. Para obtener más detalles, consulte el artículo de Wikipedia.