Estoy estudiando las mejores estructuras de datos para implementar una base de datos temporal de objetos de código abierto simple, y actualmente estoy muy encariñado con el uso de árboles rojo-negros persistentes para hacer eso.Árboles rojos-negros persistentes (puramente funcionales) en el rendimiento del disco
Mi principal razón para utilizar estructuras de datos persistentes es ante todo para minimizar el uso de bloqueos, por lo que la base de datos puede ser lo más paralela posible. También será más fácil implementar transacciones ACID e incluso ser capaz de abstraer la base de datos para trabajar en paralelo en un clúster de algún tipo. Lo bueno de este enfoque es que hace posible la implementación de bases de datos temporales casi de forma gratuita. Y esto es algo bastante agradable de tener, especialmente para la web y para el análisis de datos (por ejemplo, tendencias).
Todo esto es genial, pero sospecho un poco sobre el rendimiento general del uso de una estructura de datos persistente en el disco. A pesar de que hay algunos discos muy rápidos disponibles hoy en día, y todas las escrituras se pueden realizar de forma asíncrona, por lo que una respuesta es siempre inmediata, no quiero construir todas las aplicaciones bajo una premisa falsa, solo darme cuenta de que no es realmente una buena forma de hacerlo
Esta es mi línea de pensamiento: - Dado que todas las escrituras se realizan de forma asincrónica, y utilizando una estructura de datos persistente no invalidará la estructura anterior - y actualmente válida -, el tiempo de escritura no es realmente un cuello de botella. - Hay literatura sobre estructuras como this que son exactamente para el uso del disco. Pero me parece que estas técnicas agregarán más sobrecarga de lectura para lograr escrituras más rápidas. Pero creo que exactamente lo opuesto es preferible. También muchas de estas técnicas realmente terminan con árboles de múltiples versiones, pero no son estrictamente inmutables, lo cual es algo muy crucial para justificar la sobrecarga persistente. - Sé que todavía habrá algún tipo de bloqueo al agregar valores a la base de datos, y también sé que debería haber una buena lógica de recolección de basura si no se mantienen todas las versiones (de lo contrario, el tamaño del archivo seguramente aumentará drásticamente)) También podría pensarse en un sistema de compresión delta. - De todas las estructuras de árboles de búsqueda, realmente creo que los Red-Blacks son los más cercanos a lo que necesito, ya que ofrecen el menor número de rotaciones.
Pero hay algunas posibles dificultades en el camino: - Las escrituras asincrónicas pueden afectar a las aplicaciones que necesitan los datos en tiempo real. Pero no creo que ese sea el caso con las aplicaciones web, la mayoría de las veces. Además, cuando se necesitan datos en tiempo real, se podrían idear otras soluciones, como un sistema de check-in/check-out de datos específicos que deberán trabajarse de una manera más en tiempo real. - También podrían provocar algunos conflictos de compromiso, aunque no puedo pensar en un buen ejemplo de cuándo podría suceder. También pueden ocurrir conflictos de compromiso en RDBMS normal, si dos hilos funcionan con los mismos datos, ¿no? - La sobrecarga de tener una interfaz inmutable como esta crecerá exponencialmente y todo está destinado a fallar pronto, por lo que todo esto es una mala idea.
¿Alguna idea?
Gracias!
edición: Parece que hay un malentendido de lo que una estructura de datos persistente es: http://en.wikipedia.org/wiki/Persistent_data_structure
Me estás matando Smalls. –
¿Puedes explicar por qué "Mis razones principales para usar estructuras de datos persistentes es antes que nada para minimizar el uso de bloqueos" ??? Persistente o no, aún necesitas bloqueos ... –
Bueno, tienes razón. Todavía existe la necesidad de utilizar bloqueos, pero se reduce al mínimo a un mínimo absoluto. Por ejemplo, en mi caso, los únicos lugares donde necesitaremos candados son referencias "débiles", como la cabeza del árbol rojo-negro. Después de agregar todos los cambios de árbol al archivo, debemos bloquearlo solo para cambiar el puntero (solo un int) al encabezado del árbol. No hay posibilidad de que un lector que no se está moviendo atrape el árbol en un estado incoherente, y el bloqueo debería funcionar realmente rápido. También para escribir, la única vez que se necesita un bloqueo es cambiar el tamaño del archivo (agregando datos) – Waneck