En informática , un árbol danzante es una estructura de datos de árbol similar a los árboles B + . Fue inventado por Hans Reiser , para ser utilizado por el sistema de archivos Reiser4 . A diferencia de los árboles de búsqueda binaria autoequilibrados que intentan mantener sus nodos equilibrados en todo momento, los árboles danzantes solo equilibran sus nodos cuando se descargan datos en un disco (ya sea por limitaciones de memoria o porque se ha completado una transacción). [1]
La idea detrás de esto es acelerar las operaciones del sistema de archivos retrasando la optimización del árbol y solo escribiendo en el disco cuando sea necesario, ya que escribir en el disco es miles de veces más lento que escribir en la memoria. Además, debido a que esta optimización se realiza con menos frecuencia que con otras estructuras de datos de árbol, la optimización puede ser más extensa.
En cierto sentido, se puede considerar que es un árbol de búsqueda binario autoequilibrado que está optimizado para el almacenamiento en un medio lento, en el sentido de que la forma en disco siempre estará equilibrada pero no obtendrá escrituras a mitad de la transacción; hacerlo alivia la dificultad (en el momento) de agregar y eliminar nodos y, en su lugar, realiza estas operaciones de reequilibrio (lentas) al mismo tiempo que la escritura (mucho más lenta) en el medio de almacenamiento.
Sin embargo, se observa un efecto secundario (negativo) de este comportamiento en casos de cierre inesperado, escrituras de datos incompletas y otras ocurrencias que pueden impedir que se complete la transacción final (equilibrada). En general, los árboles danzantes plantearán una mayor dificultad para la recuperación de datos de transacciones incompletas que un árbol normal; aunque esto se puede solucionar agregando registros de transacciones adicionales o desarrollando un algoritmo para ubicar datos en el disco que no estaban previamente presentes, luego se realizan las optimizaciones una vez más antes de continuar con cualquier otra operación / transacción pendiente.