En informática , un árbol danzante es una estructura de almacenamiento de datos similar a un árbol que es similar a los árboles B+ . Fue diseñado por Hans Reiser para su uso en el sistema de archivos Reiser4 . En comparación con los árboles binarios equilibrados, que intentan mantener sus nodos equilibrados todo el tiempo, los árboles danzantes solo mantienen el equilibrio entre los nodos cuando los datos se escriben en el disco, ya sea debido a limitaciones de memoria o porque se ha completado una transacción. [una]
La idea es acelerar las operaciones del sistema de archivos al no optimizar el árbol y escribir en el disco solo cuando sea necesario, ya que escribir en el disco es miles de veces más lento que escribir en la memoria. Además, dado que esta optimización es menos frecuente que con otras estructuras de datos de árbol, las ganancias pueden ser aún mayores.
Sin embargo, el efecto secundario de este comportamiento aparece en el caso de un apagado inesperado del sistema, escrituras de datos incompletas y otros fenómenos que pueden impedir la finalización de la transacción final (saldada). En general, los árboles danzantes dificultan más la recuperación de datos de operaciones pendientes que los árboles normales, aunque este problema se puede resolver agregando registros de transacciones adicionales o desarrollando un algoritmo para encontrar datos previamente inexistentes en el disco, luego realizar optimizaciones y reanudar operaciones. .
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |