data structures - orden - Árbol negro rojo contra árbol B
orden arbol b (2)
Tengo un proyecto en el que tengo que lograr operaciones de búsqueda, inserción y eliminación rápidas en datos que van desde megabytes a terabytes. Estuve estudiando estructuras de datos últimamente y analizándolas. Siendo específico, quiero presentar 3 casos y hacer preguntas al respecto:
Los datos son mucho más de lo que la memoria puede manejar (rangos de muestra en 10-15 terabytes) de una sola vez. En este caso, almacenaría la estructura de datos en un disco.
La información es relativamente menor en comparación con la memoria del sistema y, por lo tanto, puede almacenarse y manejarse en la memoria para mayor velocidad.
Los datos son más que memoria libre y se supone que es menor que el tamaño de una posible porción contigua de datos en el archivo de paginación. así almaceno la estructura de datos en un archivo en el disco y realizo una asignación de memoria del archivo.
Las conclusiones que he extraído son:
Para el caso 1, debería usar un B-Tree para un acceso más rápido, ya que ahorra en el retraso producido por la rotación del disco
Para el caso 2, debería usar un Árbol Rojo Negro para un acceso más rápido ya que los datos están en la memoria y no. de los elementos necesarios para escanear en el peor de los casos sería menor que uno que tengo que hacer si uso B Trees
Para el caso 3, dudo mucho de que este, el archivo de página que está en el disco usa la E / S del sistema operativo nativo para operar en los archivos, entonces ¿B Tree debería ser una mejor opción o un árbol de Red Black?
Quiero saber dónde van las tres conclusiones anteriores y dónde va mal, y cómo puedo mejorar el rendimiento en los tres casos separados.
Estoy usando el lenguaje C ++, con un árbol rojo negro y un árbol B, ambos diseñados por mí desde cero. Estoy usando la biblioteca de Boost para mapeo de archivos.
Actualización 1 :: Estaba leyendo this publicación en stackoverflow. Obtuve algunas ideas realmente buenas, que me hacen sentir que el tipo de comparaciones que he hecho en los casos puede ser defectuoso. Se publicó un enlace en el http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html más votado.
Para entender la diferencia entre estos, lea a continuación 2 puntos:
1) Un "Árbol rojo-negro" es un "Árbol de búsqueda binaria autoequilibrante", con cada nodo marcado con un color (rojo o negro) y tiene operaciones adicionales definidas en él para mantener el "equilibrio"
2) Todos los "árboles rojos y negros" son "árboles de búsqueda binarios", pero todos los "árboles de búsqueda binarios" no son "árboles rojos y negros"
Un árbol rojo / negro es más o menos equivalente a un árbol 2-3-4, que es solo un tipo de árbol B. El peor de los casos es idéntico, siempre que realice una búsqueda binaria de los valores del nodo B-tree.
La desventaja obvia de un B-tree es el espacio desperdiciado, pero dependiendo del lenguaje / asignador de memoria utilizado, puede encontrar que un árbol 2-3-4 usa menos espacio que un árbol rojo-negro en promedio. Por ejemplo, en Java de 32 bits, hay aproximadamente una sobrecarga de 8 bytes por objeto. (También depende mucho del asignador; IIRC phkmalloc redondea asignaciones pequeñas a un tamaño de potencia de 2).
Para responder a sus casos,
- La latencia del disco está aproximadamente dividida en partes iguales entre el tiempo de búsqueda y la espera de que el disco gire.
- Un árbol B debería ser capaz de superar a un árbol rojo-negro si lo estás haciendo bien (en particular, un árbol B debería ser más rápido si los nodos encajan en una línea de caché).
- No necesita ser contiguo en el archivo de página; simplemente necesita ser contiguo en el espacio de direcciones virtuales del proceso. Para sistemas operativos sanos, también es prácticamente idéntico al caso 1, a menos que los datos sean lo suficientemente pequeños como para que quepan en la memoria y la sobrecarga de memcpy sea significativa.
Para simplificar, me gustaría ir con un árbol B y ejecutar algunos puntos de referencia en varios tamaños de nodo.