algorithm - geeksforgeeks - B-tree más rápido que AVL o RedBlack-Tree?

red black tree simulator (9)

Sé que el rendimiento nunca es en blanco y negro, a menudo una implementación es más rápida en el caso X y más lenta en el caso de Y, etc., pero, en general, ¿son B-trees más rápidos que AVL o RedBlack-Trees? Son considerablemente más complejos para implementar los árboles AVL (¿y quizás incluso los árboles negros rojos?), Pero ¿son más rápidos (su complejidad vale la pena)?

Editar: También me gustaría añadir que si son más rápidos que el árbol AVL / RedBlack equivalente (en términos de nodos / contenido), ¿por qué son más rápidos?

Chicos de Google lanzaron recientemente su implementación de contenedores STL, que se basa en B-trees. Afirman que su versión es más rápida y consume menos memoria en comparación con los contenedores estándar STL, implementados a través de árboles rojo-negro. Más detalles here

En realidad, Wikipedia tiene un excelente artículo que muestra que cada árbol RB se puede expresar fácilmente como un árbol B. Tome el siguiente árbol como muestra:

ahora solo conviértalo en un B-Tree (para hacer esto más obvio, los nodos siguen siendo de color R / B, lo que normalmente no tienes en un B-Tree):

El mismo árbol que B-Tree

(No se puede agregar la imagen aquí por alguna razón extraña)

Lo mismo es cierto para cualquier otro árbol RB. Está tomado de este artículo:

http://en.wikipedia.org/wiki/Red-black_tree

Para citar de este artículo:

El árbol rojo-negro es estructuralmente equivalente a un árbol B de orden 4, con un factor de relleno mínimo de 33% de valores por grupo con una capacidad máxima de 3 valores.

No encontré datos de que uno de los dos sea significativamente mejor que el otro. Supongo que uno de los dos ya se había extinguido si ese fuera el caso. Son diferentes en cuanto a la cantidad de datos que deben almacenar en la memoria y lo complicado que es agregar / eliminar nodos del árbol.

Actualizar:

Mis pruebas personales sugieren que B-Trees es mejor cuando se buscan datos, ya que tienen una mejor localidad de datos y, por lo tanto, la memoria caché de la CPU puede hacer comparaciones algo más rápido. Cuanto mayor sea el orden de un B-Tree (el orden es el número de hijos que puede tener una nota), más rápida será la búsqueda. Por otro lado, tienen un peor rendimiento para agregar y eliminar nuevas entradas cuanto mayor sea su orden. Esto es causado por el hecho de que agregar un valor dentro de un nodo tiene una complejidad lineal. Como cada nodo es una matriz ordenada, debe mover muchos elementos dentro de esa matriz al agregar un elemento en el medio: todos los elementos a la izquierda del nuevo elemento deben moverse una posición hacia la izquierda o todos los elementos a la derecha de el nuevo elemento debe moverse una posición hacia la derecha. Si un valor mueve un nodo hacia arriba durante un inserto (que ocurre con frecuencia en un árbol B), deja un orificio que también debe rellenarse moviendo todos los elementos de la posición izquierda a la derecha o moviendo todos los elementos a la derecha una posición a la izquierda. Estas operaciones (en C usualmente realizadas por memmove) son de hecho O (n). Por lo tanto, cuanto mayor sea el orden del B-Tree, más rápida será la búsqueda, pero más lenta será la modificación. Por otro lado, si elige el orden demasiado bajo (por ejemplo, 3), un árbol B muestra pocas ventajas o desventajas sobre otras estructuras de árboles en la práctica (en tal caso, también puede usar otra cosa). Por lo tanto, siempre crearía B-Trees con órdenes altas (al menos 4, 8 y hasta está bien).

Los sistemas de archivos, que a menudo se basan en B-Trees, usan pedidos mucho más altos (orden 200 e incluso mucho más); esto es porque generalmente eligen el orden lo suficientemente alto para que una nota (cuando contiene la cantidad máxima de elementos permitidos) sea igual el tamaño de un sector en disco duro o de un clúster del sistema de archivos. Esto proporciona un rendimiento óptimo (ya que una HD solo puede escribir un sector completo a la vez, incluso cuando solo se cambia un byte, el sector completo se reescribe de todos modos) y la utilización óptima del espacio (ya que cada entrada de datos en la unidad equivale al menos al tamaño de un clúster o es un múltiplo de los tamaños de clúster, sin importar qué tan grandes sean realmente los datos). Causado por el hecho de que el hardware ve los datos como sectores y el sistema de archivos agrupa los sectores en clústeres, B-Trees puede producir mucho mejor rendimiento y utilización de espacio para los sistemas de archivos que cualquier otra estructura de árbol; es por eso que son tan populares para los sistemas de archivos.

Cuando su aplicación actualiza constantemente el árbol, agregando o eliminando valores de él, un árbol RB o un árbol AVL pueden mostrar un mejor rendimiento en promedio en comparación con un árbol B con alto orden. Algo peor para las búsquedas y también pueden necesitar más memoria, pero las modificaciones suelen ser rápidas. En realidad, los RB-Trees son incluso más rápidos para las modificaciones que AVL-Trees, por lo que los AVL-Trees son un poco más rápidos para las búsquedas, ya que generalmente son menos profundos.

Como de costumbre, depende en gran medida de lo que esté haciendo tu aplicación. Mis recomendaciones son:

Muchas búsquedas, pequeñas modificaciones: B-Tree (con alto orden)
Muchas búsquedas, muchas modificaciones: AVL-Tree
Pequeñas búsquedas, muchas modificaciones: RB-Tree

Una alternativa a todos estos árboles son los árboles de AA-Trees . Como sugiere este documento PDF , AA-Trees (que en realidad son un subgrupo de RB-Trees) son casi iguales en rendimiento a los RB-Trees normales, pero son mucho más fáciles de implementar que los RB-Trees, AVL-Trees, o B-Trees. Aquí hay una implementación completa , fíjate qué tan pequeña es (la función principal no es parte de la implementación y la mitad de las líneas de implementación son en realidad comentarios).

Como muestra el documento PDF, un Treap también es una alternativa interesante a la implementación clásica de árboles. Un Treap también es un árbol binario, pero uno que no intenta forzar el equilibrio. Para evitar los peores escenarios que pueda obtener en árboles binarios desbalanceados (lo que hace que las búsquedas se vuelvan O (n) en lugar de O (log n)), un Treap agrega algo de aleatoriedad al árbol. La aleatoriedad no puede garantizar que el árbol esté bien equilibrado, pero también hace que sea muy poco probable que el árbol esté extremadamente desequilibrado.

La pregunta es antigua, pero creo que sigue siendo relevante. Jonas Kölker y Mecki dieron muy buenas respuestas, pero no creo que las respuestas cubran toda la historia. Incluso diría que a toda la discusión le falta el punto :-).

Lo que se dijo sobre B-Trees es verdadero cuando las entradas son relativamente pequeñas (enteros, cadenas / palabras pequeñas, flotantes, etc.). Cuando las entradas son grandes (más de 100B) las diferencias se vuelven más pequeñas / insignificantes.

Permítanme resumir los puntos principales sobre B-Trees:

Son más rápidos que cualquier árbol de búsqueda binaria (BST) debido a la ubicación de la memoria (lo que resulta en menos errores de caché y TLB).
B-Trees usualmente son más eficientes en el uso del espacio si las entradas son relativamente pequeñas o si las entradas son de tamaño variable. La administración de espacio libre es más fácil (se asignan trozos más grandes de memoria) y la sobrecarga de metadatos adicionales por entrada es menor. B-Trees desperdiciará espacio ya que los nodos no siempre están llenos, sin embargo, siguen siendo más compactos que los Binary Search Trees.
El gran rendimiento O (O (logN)) es el mismo para ambos. Además, si haces una búsqueda binaria dentro de cada nodo B-Tree, incluso terminarás con el mismo número de comparaciones que en una BST (es un buen ejercicio matemático para verificar esto). Si el tamaño del nodo B-Tree es razonable (tamaño de línea de caché de 1 a 4 veces), la búsqueda lineal dentro de cada nodo es aún más rápida debido a la recuperación previa de hardware. También puede usar instrucciones SIMD para comparar tipos de datos básicos (por ejemplo, enteros).
Los B-Trees son más adecuados para la compresión: hay más datos por nodo para comprimir. En ciertos casos, esto puede ser un gran beneficio. Solo piense en una clave de incremento automático en una tabla de base de datos relacional que se usa para crear un índice. Los nodos principales de un B-Tree contienen enteros consecutivos que se comprimen muy, muy bien.
Los B-Trees son claramente mucho, mucho más rápidos cuando se almacenan en un almacenamiento secundario (donde se necesita hacer un bloque IO).

En papel, B-Trees tiene muchas ventajas y casi ninguna desventaja. Entonces, ¿debería uno usar B-Trees para obtener el mejor rendimiento?

La respuesta generalmente es NO - si el árbol se ajusta en la memoria. En los casos en que el rendimiento es crucial, se necesita una estructura de datos similar a un árbol segura para subprocesos (en pocas palabras, varios subprocesos pueden hacer más trabajo que uno solo). Es más problemático hacer que un árbol B soporte accesos simultáneos que hacer una BST. La forma más sencilla de hacer que un árbol admita accesos concurrentes es bloquear nodos a medida que los atraviesa / modifica. En un árbol B, bloquea más entradas por nodo, lo que genera más puntos de serialización y más bloqueos controlados.

Todas las versiones de árbol (AVL, Rojo / Negro, B-Tree y otras) tienen innumerables variantes que difieren en cómo admiten la concurrencia. Los algoritmos de vanilla que se enseñan en un curso universitario o que se leen de algunos libros introductorios casi nunca se usan en la práctica. Por lo tanto, es difícil decir qué árbol funciona mejor ya que no hay un acuerdo oficial sobre los algoritmos exactos que hay detrás de cada árbol. Sugeriría pensar en los árboles que se mencionan más como clases de estructura de datos que obedecen a ciertas invariantes arbóreas en lugar de a estructuras de datos precisas.

Tomemos, por ejemplo, el B-Tree. El árbol B de vainilla casi nunca se usa en la práctica: ¡no se puede escalar bien! La variante más común de B-Tree utilizada es B + -ree (ampliamente utilizada en sistemas de archivos, bases de datos). Las principales diferencias entre B + -Tree y B-Tree: 1) no almacena entradas en los nodos internos del árbol (por lo tanto, no necesita escribir bloqueos en el árbol cuando modifica una entrada almacenada en un nodo interno) ; 2) tiene enlaces entre nodos en el mismo nivel (por lo tanto, no es necesario bloquear el padre de un nodo al realizar búsquedas de rango).

Espero que esto ayude.

La publicación de Sean (la actualmente aceptada) contiene varias afirmaciones incorrectas. Lo siento Sean, no quiero ser grosero; Espero poder convencerte de que mi declaración está basada en hechos.

Son totalmente diferentes en sus casos de uso, por lo que no es posible hacer una comparación.

Ambos se utilizan para mantener un conjunto de elementos totalmente ordenados con búsqueda rápida, inserción y eliminación. Tienen la misma interfaz y la misma intención.

Los árboles RB suelen ser estructuras en memoria utilizadas para proporcionar un acceso rápido (idealmente O (logN)) a los datos. [...]

siempre O (log n)

B-trees son típicamente estructuras basadas en disco, y por lo tanto son intrínsecamente más lentas que los datos en la memoria.

Disparates. Cuando almacena árboles de búsqueda en el disco, normalmente usa B-trees. Eso es verdad Cuando almacena datos en el disco, es más lento acceder que los datos en la memoria. Pero un árbol rojo-negro almacenado en el disco también es más lento que un árbol rojo-negro almacenado en la memoria.

Estás comparando manzanas y naranjas aquí. Lo que es realmente interesante es una comparación de árboles B en memoria y árboles rojo-negro en memoria.

[Como comentario adicional: los árboles B, a diferencia de los árboles rojo-negro, son teóricamente eficientes en el modelo de E / S. He probado experimentalmente (y validado) el modelo I / O para la clasificación; Yo también esperaría que funcione para B-trees.]

B-trees raramente son árboles binarios, la cantidad de hijos que un nodo puede tener es típicamente un gran número.

Para que quede claro, el rango de tamaño de los nodos B-tree es un parámetro del árbol (en C ++, es posible que desee utilizar un valor entero como parámetro de plantilla).

La gestión de la estructura del árbol B puede ser bastante complicada cuando los datos cambian.

Recuerdo que eran mucho más simples de entender (e implementar) que los árboles rojo-negro.

B-tree intenta minimizar el número de accesos al disco para que la recuperación de datos sea razonablemente determinista.

Eso es verdad

No es raro ver algo como el acceso a 4 B-tree necesario para buscar un poco de datos en una base de datos muy.

¿Tienes datos?

En la mayoría de los casos, diría que los árboles RB en memoria son más rápidos.

¿Tienes datos?

Como la búsqueda es binaria, es muy fácil encontrar algo. B-tree puede tener varios hijos por nodo, por lo que en cada nodo debe escanear el nodo para buscar el elemento secundario apropiado. Esta es una operación O (N).

El tamaño de cada nodo es un parámetro fijo, por lo que incluso si realiza un escaneo lineal, es O (1). Si somos grandes-oh por encima del tamaño de cada nodo, tenga en cuenta que normalmente mantiene la matriz ordenada por lo que es O (log n).

En un árbol RB sería O (logN) ya que está haciendo una comparación y luego una bifurcación.

Estás comparando manzanas y naranjas. El O (log n) se debe a que la altura del árbol es como máximo O (log n), al igual que para un B-tree.

Además, a menos que juegues trucos desagradables con los árboles rojo-negro, parece razonable conjeturar que los B-trees tienen mejor comportamiento de caché (accede a una matriz, no punteros esparcidos por todos lados, y tiene menos sobrecarga de asignación aumentando la memoria localidad aún más), lo que podría ayudarlo en la carrera de velocidad.

Puedo señalar la evidencia experimental de que los árboles B (con los parámetros de tamaño 32 y 64, específicamente) son muy competitivos con los árboles rojo-negros para tamaños pequeños, y los supera claramente incluso para valores de n moderadamente grandes. Ver http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

B-trees son más rápidos. ¿Por qué? Supongo que se debe a la localidad de memoria, mejor comportamiento de almacenamiento en caché y menos persecución de punteros (que son, si no las mismas cosas, superpuestas hasta cierto punto).

Nada impide una implementación de B-Tree que solo funciona en la memoria. De hecho, si las comparaciones de claves son baratas, B-Tree en memoria puede ser más rápido porque su empaque de múltiples claves en un nodo causará menos errores de caché durante las búsquedas. Vea this enlace para comparar el rendimiento. Una cita: "Los resultados de la prueba de velocidad son interesantes y muestran que el árbol B + es significativamente más rápido para los árboles que contienen más de 16,000 elementos". (B + Tree es solo una variación en B-Tree).

Para algunas aplicaciones, B-trees es significativamente más rápido que BSTs. Los árboles que puedes encontrar aquí:

http://freshmeat.net/projects/bps

son bastante rápidos También utilizan menos memoria que las implementaciones BST normales, ya que no requieren la infraestructura BST de 2 o 3 punteros por nodo, más algunos campos adicionales para mantener la información de equilibrio.

Se utilizan en diferentes circunstancias: los árboles B se utilizan cuando los nodos de los árboles deben mantenerse juntos en el almacenamiento, generalmente porque el almacenamiento es una página de disco y, por lo tanto, el reequilibrio puede ser costoso. Los árboles RB se usan cuando no tienes esta restricción. Entonces, los B-trees probablemente serán más rápidos si desea implementar (digamos) un índice de base de datos relacional, mientras que los árboles RB probablemente serán más rápidos para (por ejemplo) una búsqueda en la memoria.

Todos tienen el mismo comportamiento asintótico, por lo que el rendimiento depende más de la implementación que del tipo de árbol que está utilizando. En realidad, una combinación de estructuras de árbol podría ser el enfoque más rápido, donde cada nodo de un árbol B se ajusta exactamente a una línea de caché y se utiliza algún tipo de árbol binario para buscar dentro de cada nodo. Administrar la memoria para los nodos usted mismo también podría permitirle alcanzar una localidad de caché aún mayor, pero a un precio muy alto.

Personalmente, solo uso lo que esté en la biblioteca estándar para el idioma que estoy usando, ya que es mucho trabajo para una ganancia de rendimiento muy pequeña (si la hay).

En una nota teórica ... los árboles RB son en realidad muy similares a los B-trees, ya que simulan el comportamiento de 2-3-4 árboles. Los árboles AA son una estructura similar, que simula 2-3 árboles en su lugar.

además ... la altura de un árbol negro rojo es O (log [2] N) mientras que la de B-tree es O (log [q] N) donde techo [N] <= q <= N. Entonces, si consideramos las comparaciones en cada matriz de claves de B-tree (que se fija como se mencionó anteriormente), entonces la complejidad del tiempo de B-tree <= time complex of Red-black tree. (caso igual para un solo registro igual en tamaño de un tamaño de bloque)