Estructuras de datos multidimensionales : un análisis de desempeño

Abstract

RESUMEN: En los sistemas manejadores de datos multidimensionales es necesario construir índices para agilizar las consultas. Debido a la existencia de múltiples estructuras definidas para representar los índices, se dificulta la decisión acerca de cuál estructura utilizar. Este artículo muestra los resultados de una evaluación del proceso de consulta por rangos sobre varias estructuras de datos multidimensionales, con base en el comportamiento del número de accesos a disco. Las estructuras de datos evaluadas fueron: el GRID FILE, el árbol KDB y el árbol R. Los experimentos revelan que para rangos pequeños, independientemente de la escalabilidad, el comportamiento del número de accesos a disco mostrado por el árbol R es similar al del GRID FILE. A medida que la extensibilidad aumenta, el árbol R muestra un menor número de accesos a disco. Para el caso del GRID FILE, el número de accesos a disco crece linealmente con una pendiente alta, a medida que aumenta la extensibilidad, lo que limita su uso a rangos pequeños. En el caso del árbol KDB, el comportamiento del número de accesos a disco no depende de la extensibilidad. Del resultado del experimento se deduce que de las tres estructuras evaluadas, la más recomendable, para el propósito de disminuir el número de accesos a disco en consultas por rango, es la estructura del árbol R.