Árbol AVL vs B-árbol

Tanto el árbol AVL como el árbol B son similares en 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 que la búsqueda se realice en tiempo O(log n), porque 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 demasiado complicado de escribir, pero si buscas en Google "B-tree animation" hay algunos applets realmente buenos que explican un B-tree bastante bien.

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 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 todavía tendríamos un número significativo de lecturas para leer un árbol de un tamaño muy grande.

Cuando la recopilación de datos es tan grande que no cabe en la memoria, la solución es una B-tree (dato interesante: no hay consenso sobre lo que significa la "B" en realidad). Un árbol B sostiene a muchos niños en un nodo y muchos punteros al nodo niños. De esta manera, durante una lectura de disco (que puede tomar alrededor de 10 ms para 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 de hoja". Esto permite que el tiempo de recuperación de los datos se amortize para log (n), lo que hace que el árbol B sea especialmente útil para bases de datos y conjuntos de datos grandes implementaciones de recuperación.

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 disminuye el número de nodos que la búsqueda necesita visitar. Esto los hace buenos para árboles basados en discos. Para más detalles, vea el artículo de Wikipedia .

AVL es autoequilibrante, lo que garantiza que todas las operaciones son O(log n) en promedio y en el peor de los casos.

El árbol B utiliza todas las ideas descritas anteriormente. En particular, un árbol B:

1)keeps keys in sorted order for sequential traversing
2)uses a hierarchical index to minimize the number of disk reads
3)uses partially full blocks to speed insertions and deletions
4)keeps the index balanced with an elegant recursive algorithm

Además, un árbol B minimiza el desperdicio asegurándose de que los nodos interiores estén al menos medio llenos. Un árbol B puede manejar un número arbitrario de inserciones y eliminaciones.

Un árbol AVL es un árbol binario de autoequilibrio que habilita el promedio O(lgN) y el peor caso para las operaciones de inserción y eliminación de búsqueda. Se utiliza para árboles de búsqueda respaldados en memoria (conjuntos de datos de tamaño moderado).

Un árbol B se usa principalmente como un árbol de búsqueda respaldado por almacenamiento para conjuntos de datos muy grandes porque requiere menos lecturas en el disco (ya que cada nodo contiene N claves donde N >1). Un Árbol B se dice que es un (N,N+1) B-Árbol donde N es el número de claves por nodo y N+1 es el número de niños por nodo. Cuantas más claves por nodo, menos veces tendrá que leer desde el disco y, naturalmente, también será un árbol menos profundo (menos niveles).

Son muy diferentes de hecho, aunque sirven en gran medida el mismo propósito: apoyar una tabla asociativa. Históricamente, el árbol AVL se tomó para superar al árbol B para las operaciones en memoria, pero eso es especialmente cierto cuando el acceso a la memoria era barato(er) en comparación con los ciclos de CPU.

Aunque generalmente se usa en el almacén de bases de datos para claves de longitud variable, los árboles B funcionan mejor para registros de longitud fija y cortos (clave + datos). Para tales usos, que puede significativamente superan a los árboles AVL para usos en memoria, tanto en términos de huella de memoria (ya que almacenan datos de forma más compacta) como de velocidad (tendrían una ubicación de caché mucho mejor).

L2 es una biblioteca de estructuras de datos que implementa tablas y secuencias asociativas muy rápidas sobre árboles B. También tiene árboles AVL, y hacer una comparación entre el rendimiento de dos es fácil.

En términos sencillos -

El árbol AVL y el árbol de búsqueda binario son los mismos, pero el árbol AVL tiene una restricción de que la diferencia entre la altura del sub árbol izquierdo y el sub árbol derecho debe ser 0, 1 o -1.

Si cualquier árbol de búsqueda binario cumple con estas condiciones, se llamará como árbol AVL.

Árbol de búsqueda binario + CONDICIÓN DE ALTURA es un árbol AVL.

Consulte: Introducción a los algoritmos por Cormen https://books.google.co.in/books...

Otras respuestas ya han proporcionado detalles técnicos bastante detallados sobre AVL y B-Tree, pero me gustaría agregar una información relativamente novata con respecto a estos dos :) -

• El árbol AVL es un árbol binario, mientras que B-tree es un árbol de múltiples vías (árbol N-ario), es decir, cualquier nodo en el árbol AVL puede tener como máximo dos nodos hijos y una pieza de información/datos mientras que cualquier nodo en a el árbol B puede tener n nodos y n-1 pieza de información/datos. Para B-tree, n también se conoce como su orden.