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

Abstract

En los sistemas manejadores de datos multidimensionales es necesario cons­truir índices para agilizar las consultas. Debido a la existencia de múltiples es­tructuras 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 GR.ID FILE, el árbol KDB y el árbol R. Los experimentos revelan que para rangos pequeños, independiente­mente de la escalabilidad, el comportamiento del número de accesos a disco mostrado por el árbol R es similar al del GRJD FILE. A medida que la extensibilidad aumenta, el árbol R muestra un menor número de accesos a dis­co. Para el caso del GRJD 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úme­ro de accesos a disco no depende de la extensibilidad. Del resultado del experi­mento 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.

Keywords

• Estructuras de datos multidimensionales
• procesamiento de consultas
• GRID FILE
• árbol KDB
• árbol R.