data-structures - delete - b tree simulator

Árbol AVL contra B-tree

Question

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

Answer 1

AVL se auto equilibra, garantizando que todas las operaciones sean O (log n) en el promedio y el peor de los casos.

Answer 2

El árbol B usa 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 al asegurarse de que los nodos interiores estén al menos medio llenos. Un B-tree puede manejar una cantidad arbitraria de inserciones y eliminaciones.

Answer 3

En realidad, son muy diferentes, aunque cumplen básicamente el mismo objetivo: apoyar una mesa 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.

Answer 4

En términos simples:

El árbol AVL y el árbol de búsqueda binaria son ambos iguales, pero el árbol AVL tiene una restricción 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 binaria cumple estas condiciones, se llamará como árbol AVL.

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

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

Answer 5

Los árboles AVL están diseñados para uso en memoria, donde el acceso aleatorio es relativamente barato. 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 que los árboles B se usan a menudo en sistemas de archivos y bases de datos, como SQLite ).

Answer 6

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

• El árbol AVL es un árbol binario, mientras que B-tree es un árbol multidireccional (árbol N-ary), es decir, cualquier nodo en el árbol AVL puede tener como máximo dos nodos secundarios y una información / datos mientras que cualquier nodo en un á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.

Answer 7

Tanto el árbol AVL como el árbol B son similares en cuanto a que son estructuras de datos que, a través de sus requisitos, hacen que se minimice la altura de sus respectivos árboles. 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 binario 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 á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 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 8

Un árbol AVL es un árbol binario autoequilibrado que permite 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 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 9

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 más detalles, mira el artículo de Wikipedia .