Árbol AVL contra árbol B

Question

¿En qué se diferencia un árbol AVL de un árbol B?

Answer 1

Los árboles AVL están pensados ​​para uso en memoria, donde el acceso aleatorio es relativamente económico. Los B-trees son más adecuados para el almacenamiento respaldado por disco, porque agrupan un mayor número de claves en cada nodo para minimizar el número de búsquedas requeridas por una operación de lectura o escritura. (Esta es la razón por la cual B-trees se usa a menudo en sistemas de archivos y bases de datos, como SQLite).

Answer 2

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

Answer 3

Un árbol AVL es un árbol de búsqueda binaria autoequilibrante, 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 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 Wikipedia article.

Answer 4

Tanto el árbol AVL como el B-tree son similares en que son estructuras de datos que, a través de sus requisitos, causan altura de sus respectivos árboles para ser minimizado. Esta "brevedad" permite que la búsqueda se realice en el tiempo O (log n), porque la mayor cantidad 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 binaria en su núcleo. Sin embargo, se autoequilibra, 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 B-tree 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 la "animación B-tree", hay algunos applets realmente buenos que explican bastante bien un B-tree.

Son diferentes en que un árbol AVL se implementa con soluciones basadas en memoria en mente, mientras que un B-tree se implementa teniendo en cuenta las soluciones basadas en disco. Los árboles AVL no están diseñados para contener colecciones masivas de datos, ya que usan 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 un árbol B (factoid interesante: no hay consenso sobre lo que la "B" representa en realidad). Un árbol B contiene muchos niños en un nodo y muchos puntos en el nodo niños. De esta forma, 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 hoja". Esto permite que el tiempo de recuperación de los datos se amortice a log (n) time, lo que hace que el árbol B sea especialmente útil para las implementaciones de recuperación de bases de datos y grandes conjuntos de datos.

Answer 5

El B-tree 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 son al menos medio lleno. Un B-tree puede manejar una cantidad arbitraria de inserciones y eliminaciones.

Answer 6

Un árbol AVL es un árbol binario autoequilibrante que permite el promedio O (lgN) y el peor de los casos para operaciones de inserción y eliminación de búsqueda. Se utiliza para árboles de búsqueda con respaldo de memoria (conjuntos de datos de tamaño moderado).

Un B-Tree se usa principalmente como á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 teclas donde N> 1). Se dice que un árbol B es un árbol B (N, N + 1) donde N es el número de claves por nodo y N + 1 es el número de hijos por nodo. Cuantas más claves por nodo, menos veces necesitará leer del disco y, naturalmente, será un árbol menos profundo (menos niveles).

Answer 7

En términos simples -

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

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

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

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

Answer 8

Otros que responden ya han proporcionado bastante en profundidad detalles técnicos acerca tanto AVL y B-árbol, pero me gustaría añadir una información relativamente novato con respecto a estos dos :) -

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

Answer 9

De hecho, son muy diferentes, aunque cumplen básicamente el mismo objetivo: dar soporte a una tabla asociativa. Históricamente, se tomó el árbol AVL para superar el rendimiento del árbol B en operaciones en memoria, pero eso es especialmente cierto cuando acceder a la memoria era barato (er) en comparación con los ciclos de la CPU.

Aunque generalmente se usan en el almacén de bases de datos para claves de longitud variable, los B-trees funcionan mejor para registros de longitud fija y cortos (clave + datos). Para tales usos, eso puede superar significativamente 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 mucho mejor ubicación en caché).

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