Solución:
La publicación de Sean (la aceptada actualmente) contiene varias afirmaciones incorrectas. Lo siento Sean, no quiero ser grosero; Espero poder convencerlos de que mi declaración se basa 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, inserción y eliminación rápidas. Tienen la misma interfaz y la misma intención.
Los árboles RB suelen ser estructuras en memoria que se utilizan para proporcionar un acceso rápido (idealmente O (logN)) a los datos. […]
siempre O (log n)
Los árboles B suelen ser estructuras basadas en disco, por lo que son intrínsecamente más lentas que los datos en memoria.
Disparates. Cuando almacena árboles de búsqueda en el disco, normalmente usa árboles B. Eso es cierto. Cuando almacena datos en el disco, es más lento acceder a los datos en la memoria. Pero un árbol rojo-negro almacenado en el disco es además 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.
[As an aside: B-trees, as opposed to red-black trees, are theoretically efficient in the I/O-model. I have experimentally tested (and validated) the I/O-model for sorting; I’d expect it to work for B-trees as well.]
Los árboles B rara vez son árboles binarios, la cantidad de hijos que puede tener un nodo suele ser una gran cantidad.
Para ser claros, el rango de tamaño de los nodos del árbol B 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 resultar bastante complicada cuando cambian los datos.
Recuerdo que son 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 cierto.
No es raro ver algo como el acceso de 4 árboles B necesario para buscar un poco de datos en una misma base de datos.
¿Tienes datos?
En la mayoría de los casos, diría que los árboles RB en memoria son más rápidos.
¿Tienes datos?
Debido a que la búsqueda es binaria, es muy fácil encontrar algo. El árbol B puede tener varios hijos por nodo, por lo que en cada nodo debe escanear el nodo para buscar el hijo 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 superamos el tamaño de cada nodo, tenga en cuenta que normalmente mantiene la matriz ordenada para que sea O (log n).
En un árbol RB sería O (logN) ya que está haciendo una comparación y luego ramificando.
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 lo es para un árbol B.
Además, a menos que juegue trucos de asignación desagradables con los árboles rojo-negro, parece razonable conjeturar que los árboles B tienen un mejor comportamiento de almacenamiento en caché (accede a una matriz, no punteros esparcidos por todo el lugar, 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 parámetros de tamaño 32 y 64, específicamente) son muy competitivos con los árboles rojo-negro para tamaños pequeños, y los supera sin duda en valores de n incluso moderadamente grandes. Ver http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
Los árboles B son más rápidos. ¿Por qué? Conjeturo que se debe a la ubicación de la memoria, un mejor comportamiento de almacenamiento en caché y menos persecución de punteros (que son, si no las mismas cosas, superpuestas hasta cierto punto).
En realidad, Wikipedia tiene un gran artículo que muestra que cada árbol RB puede expresarse fácilmente como un árbol B. Tome el siguiente árbol como muestra:
ahora simplemente conviértalo en un B-Tree (para que esto sea más obvio, los nodos siguen siendo de color R / B, lo que normalmente no tienes en un B-Tree):
Mismo árbol que B-Tree
(no puedo agregar la imagen aquí por alguna extraña razón)
Lo mismo es cierto para cualquier otro RB-Tree. Está tomado de este artículo:
http://en.wikipedia.org/wiki/Red-black_tree
Para citar este artículo:
El árbol rojo-negro es entonces estructuralmente equivalente a un árbol B de orden 4, con un factor de llenado mínimo del 33% de los valores por grupo con una capacidad máxima de 3 valores.
No encontré datos de que uno de ambos 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 los B-Trees son mejores cuando se buscan datos, ya que tienen una mejor ubicación de datos y, por lo tanto, la memoria caché de la CPU puede comparar algo más rápido. Cuanto mayor sea el orden de un árbol B (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 es su orden. Esto se debe al 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 a la izquierda o todos los elementos a la derecha de el nuevo elemento debe moverse una posición a la derecha. Si un valor se mueve un nodo hacia arriba durante una inserción (lo que ocurre con frecuencia en un árbol B), deja un agujero que también debe llenarse moviendo todos los elementos de la izquierda una posición a la derecha o moviendo todos los elementos a la derecha una posición a la izquierda. Estas operaciones (en C generalmente realizadas por memmove) son de hecho O (n). Por tanto, cuanto mayor sea el orden del árbol B, 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 B-Tree muestra pequeñas ventajas o desventajas sobre otras estructuras de árbol 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 más está bien).
Los sistemas de archivos, que a menudo se basan en B-Trees, usan órdenes mucho más altos (orden 200 e incluso mucho más); esto se debe a que generalmente eligen el orden lo suficientemente alto como para que una nota (cuando contiene el número máximo de elementos permitidos) sea igual a el tamaño de un sector en el disco duro o de un clúster del sistema de archivos. Esto proporciona un rendimiento óptimo (dado que un disco duro 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 una 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 del clúster, sin importar cuán grandes sean realmente los datos). Debido al hecho de que el hardware ve los datos como sectores y el sistema de archivos agrupa sectores en clústeres, los B-Trees pueden producir un rendimiento y una utilización del espacio mucho mejores para los sistemas de archivos que cualquier otra estructura de árbol; por eso son tan populares para los sistemas de archivos.
Cuando su aplicación actualiza constantemente el árbol, agregando o quitando 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 un orden alto. Algo peor para las búsquedas y es posible que también necesiten más memoria, pero por lo tanto, las modificaciones suelen ser rápidas. En realidad, los árboles RB son incluso más rápidos para las modificaciones que los árboles AVL, por lo que los árboles AVL son un poco más rápidos para las búsquedas, ya que generalmente son menos profundos.
Entonces, como de costumbre, depende mucho de lo que esté haciendo tu aplicación. Mis recomendaciones son:
- Muchas búsquedas, pequeñas modificaciones: B-Tree (con orden alto)
- Muchas búsquedas, muchas modificaciones: AVL-Tree
- Pequeñas búsquedas, muchas modificaciones: RB-Tree
Una alternativa a todos estos árboles son los árboles AA. Como sugiere este documento PDF, los árboles AA (que de hecho son un subgrupo de árboles RB) son casi iguales en rendimiento a los árboles RB normales, pero son mucho más fáciles de implementar que los árboles RB, árboles AVL, o B-Trees. Aquí hay una implementación completa, mira que pequeño 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 de árbol clásica. Un Treap también es un árbol binario, pero uno que no intenta imponer el equilibrio. Para evitar los peores escenarios que puede tener en árboles binarios desequilibrados (lo que hace que las búsquedas se conviertan en 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.
Nada impide una implementación de B-Tree que solo funciona en memoria. De hecho, si las comparaciones de claves son baratas, el B-Tree en memoria se puede más rápido porque su empaque de múltiples claves en un nodo causará menos fallas de caché durante las búsquedas. Consulte este enlace para ver comparaciones de 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 árboles que contienen más de 16.000 elementos”. (B + Tree es solo una variación de B-Tree).