PDF de programación - Estructuras de datos multidimensionales

Indice

Tema 0.-Estructuras de datos multidimensionales

. . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Módulo 1.- Monodimensionalismo.

Métodos separativos.

Tema 1.- Ficheros invertidos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

Tema 2.- Multilistas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

Tema 3.- Ordenación multiclave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

Métodos integrados secuenciales.

Tema 4.- Códigos superpuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

Métodos integrados arbóreos con agregación de claves.

Tema 5.-

Indices combinados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

Tema 6.- Multiclaves fundidas en monoclave . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Módulo 2.- Integración arbórea.

Claves independientes.

Tema 7.- Arbol Cuaternario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Tema 8.- Arbol de múltiples claves (Arbol mc)

. . . . . . . . . . . . . . . . . . . . . . . . 153

Tema 9.- Arbol binario k-dimensional (Arbol kd) . . . . . . . . . . . . . . . . . . . . . . . 165

Tema 10.- Arbol de división binaria k-dimensional con expresión de zona

discriminadora (Arbol bd)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

Tema 11.- Arbol k-dimensional equilibrado en altura (Arbol kdea)

. . . . . . . . . . . 235

Tema 12.- Arbol Quintario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Tema 13.- Arbol b multidimensional (Arbol bm)

. . . . . . . . . . . . . . . . . . . . . . . . 287

Tema 14.- Arbol b con división del tipo árbol kd (Arbol kdb) . . . . . . . . . . . . . . . 313

Propiedad del espacio de las claves.

Tema 15.- Arbol de Burkhard y Keller (Arbol bk) . . . . . . . . . . . . . . . . . . . . . . . 345

Módulo 3.- Acceso directo.

Desmenuzamientos con agregación de claves.

Extensibles.

Tema 16.- Búsquedas parciales basadas en el desmenuzamiento extensible . . . . . . 357

Lineales.

Tema 17.- Búsquedas parciales basadas en el desmenuzamiento lineal

. . . . . . . . . 371

Desmenuzamientos con claves independientes.

Extensibles.

Tema 18.- Desmenuzamiento extensible multidimensional

. . . . . . . . . . . . . . . . . . 391

Lineales.

Tema 19.- Desmenuzamiento lineal multidimensional

. . . . . . . . . . . . . . . . . . . . . 399

Tema 20.- Desmenuzamiento digital multidimensional

. . . . . . . . . . . . . . . . . . . . 407

Organización enrejada.

Tema 21.- Organización enrejada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

Estructuras de datos Multidimensionales

1.- Objetivos.

El alumno conocedor de las estructuras monodimensionales, cursadas anteriormente, ha

visto que el micromundo de las peticiones de información en tales tipos de estructuras es

restringido. Sólo es capaz de dilucidar si un determinado valor de clave se encuentra o no en

la base de datos; todo lo más, recuperar un conjunto de valores de clave acotados por unos

límites, realizando búsquedas que se denominan no-asociativas. Como una expansión de los

tipos de peticiones de información surgen las que involucran a más de una clave, que reciben

el nombre de asociativas, como las búsquedas parciales, en rango, en rango parcial y ya con

la introducción de la idea de disimilitud aparecen las recuperaciones del más parecido y de

los vecinos más próximos.

Nuestro primer objetivo será enseñar al alumno las estructuras de datos multidimensionales

más importantes, con un orden más o menos creciente de complicación, que se aplican para

conducir conjuntamente con sus procedimientos de manipulación a la satisfacción de las

peticiones asociativas. No debe quedarse en sólo una presentación de cada una de las

estructuras, ni de sus procesos de mantenimiento, sino que además queremos transmitir al

discente ideas de discusión y de comparación de sus realizaciones. Esta presentación ha de

parecer al alumno no como un producto acabado impermeable, duro y frío sino más bien,

como una aproximación, aunque no total, de su realidad evolutiva con lo que notará cómo son

los balbuceos de una nueva técnica que se abre paso, adoleciendo primero de una infancia en

la que no se atreve a despegar del monodimensionalismo, para más tarde consolidarse y

explorar cada vez posibilidades más atrevidas y desconocidas en el micromundo de origen,

pero ya en un terreno que le es absolutamente propio. La perfección de Mozart puede

desalentar a los jóvenes; la grandeza de Beethoven, que se sacude el yugo de la tradición,

suscita la emulación renovadora.

Es muy importante, asimismo, que el alumno absorba una visión general del estado actual

de la materia, de forma que sea capaz de proponer variadas y certeras clasificaciones de las

estructuras estudiadas, en función de diversos parámetros aplicables. Ya sea dentro de una

familia de estructuras, o bien en el ámbito general, deberá aprender la forma de establecer las

adecuadas comparaciones y valoraciones de los métodos estudiados respecto al espacio de

almacenamiento utilizado y el tiempo aplicado a

la contestación de

las peticiones

multidimensionales planteables. Debe hacerse especial hincapié en la relativización de estos

valores ante la diversidad de los tipos de peticiones y de los grados de dinamicidad

solicitables.

Por último, es fundamental posibilitar la participación activa del alumno en el proceso de

1

sedimentación de los conocimientos. Para ello se pretende conseguir que el discente plantee,

teórica y prácticamente, las variaciones aplicables a las diversas estructuras presentadas, y

desarrolle los procesos de resolución de peticiones y de mantenimiento más adecuados para

cada posible modificación sugerida. Asimismo, realizará las valoraciones pertinentes, tanto

teóricas como empíricas, de los parámetros adecuados a la estructura, en un proceso que traerá

como consecuencia una mejor comprensión y clasificación del nuevo método de indización

dentro del esquema general presentado.

2.- Programa.

Tema 0.- Estructuras de datos multidimensionales.

0.1.- Objetivos.

0.2.- Programa.

0.3.- Justificación del contenido.

Módulo 1.- Monodimensionalismo.

Métodos separativos.

Tema 1.- Ficheros invertidos.

Tema 2.- Multilistas.

Tema 3.- Ordenación multiclave.

Métodos integrados secuenciales.

Tema 4.- Códigos superpuestos.

Métodos integrados arbóreos con agregación de claves.

Tema 5.-

Indices combinados.

Tema 6.- Multiclaves fundidas en monoclave.

2

Módulo 2.- Integración arbórea.

Claves independientes.

Tema 7.- Arbol Cuaternario.

Tema 8.- Arbol de múltiples claves (Arbol mc).

Tema 9.- Arbol binario k-dimensional (Arbol kd).

Tema 10.- Arbol de división binaria k-dimensional con expresión de zona discriminadora

(Arbol bd).

Tema 11.- Arbol k-dimensional equilibrado en altura (Arbol kdea).

Tema 12.- Arbol Quintario.

Tema 13.- Arbol b multidimensional (Arbol bm).

Tema 14.- Arbol b con división del tipo árbol kd (Arbol kdb).

Propiedad del espacio de las claves.

Tema 15.- Arbol de Burkhard y Keller (Arbol bk).

Módulo 3.- Acceso directo.

Desmenuzamientos con agregación de claves.

Extensibles.

Tema 16.- Búsquedas parciales basadas en el desmenuzamiento extensible.

Lineales.

Tema 17.- Búsquedas parciales basadas en el desmenuzamiento lineal.

Desmenuzamientos con claves independientes.

Extensibles.

Tema 18.- Desmenuzamiento extensible multidimensional.

Lineales.

Tema 19.- Desmenuzamiento lineal multidimensional.

Tema 20.- Desmenuzamiento digital multidimensional.

Organización enrejada.

Tema 21.- Organización enrejada.

3

3.- Justificación del contenido.

Los métodos para la recuperación de datos multidimensionales son de la máxima

importancia en el diseño de sistema de bases de datos y en muchas y variadas aplicaciones

específicas. Dichos métodos hacen uso de estructuras de datos multidimensionales a fin de

llevar a cabo eficientemente diversos tipos de búsquedas en las que se especifican condiciones

para múltiples claves. Este tipo de búsqueda se considera asociativa, como contraposición a

las búsquedas no-asociativas en las que tan sólo se especifica una condición para la clave

primaria.

Considérese una base de datos de personal. Es posible que nos encontremos con los

siguientes problemas de búsqueda:

Caso 1: Conocemos el número de la seguridad social de un individuo, y nos interesa

alguna otra información acerca del mismo. Podemos usar el número de la

seguridad social para buscar la ficha del individuo. Este es por tanto, un

problema de búsqueda monoclave.

Caso 2: No conocemos ni el número de la seguridad social, ni cualquier otro número

que identifique al sujeto, pero tenemos toda la demás información del mismo,

como peso, edad, altura; y queremos identificarlo. Este es un problema de

búsqueda multiclave. Los problemas de búsqueda multiclave serán los que

discutiremos en este programa.

El problema anterior es un problema de búsqueda multiclave exacta. En muchos casos lo

que tendremos será un problema de bús