En informática , un archivo de cuadrícula o cuadrícula de cubos es un método de acceso a puntos que divide un espacio en una cuadrícula no periódica donde una o más celdas de la cuadrícula hacen referencia a un pequeño conjunto de puntos. Los archivos de cuadrícula (una estructura de datos simétrica ) proporcionan un método eficiente para almacenar estos índices en el disco para realizar búsquedas de datos complejas.
Proporciona una cuadrícula de n dimensiones donde n representa cuántas claves se pueden usar para referenciar un solo punto.
Los archivos de cuadrícula no contienen ningún dato en sí mismos, sino que contienen referencias al contenedor correcto.
Un archivo de cuadrícula se utiliza generalmente en casos en los que varias claves pueden hacer referencia a un único valor.
Se empezó a utilizar un archivo de cuadrícula porque "las estructuras de archivos tradicionales que proporcionan acceso multiclave a los registros, por ejemplo, los archivos invertidos, son extensiones de las estructuras de archivos diseñadas originalmente para el acceso con una sola clave. Presentan diversas deficiencias, en particular en el acceso multiclave a archivos altamente dinámicos". [1]
En una estructura de datos unidimensional tradicional (por ejemplo, hash ), una búsqueda de un solo criterio suele ser muy sencilla, pero la búsqueda de un segundo criterio puede ser mucho más compleja.
Los archivos de cuadrícula representan un tipo especial de hash, donde el hash tradicional se reemplaza por un directorio de cuadrícula.
Fuentes: [2] [3]
Considere una base de datos que contiene datos de un censo. Un único registro representa un único hogar y todos los registros se agrupan en categorías. Todos los registros de una categoría se pueden indexar por ciudad (que es la misma para todos los registros de la categoría) y por las calles de esa ciudad cuyos nombres comienzan con la misma letra.
Se puede utilizar un archivo de cuadrícula para proporcionar un índice eficiente para esta estructura, donde los registros se presentan en grupos de 26, cada uno de ellos relacionado con los nombres de las calles de una ciudad que comienzan con una de las letras del alfabeto. Esta estructura se puede considerar como una matriz , una tabla o una cuadrícula con dos dimensiones que llamaremos ejes x e y.
Se puede considerar el eje x como la ciudad y el eje y como cada una de las letras del alfabeto o, alternativamente, la primera letra de cada calle.
Cada registro de esta estructura se conoce como celda. Cada celda contendrá un puntero al contenedor correspondiente en la base de datos donde se almacenan los datos reales. Es posible que se requiera una celda adicional, o encabezado de registro, para almacenar el nombre de la ciudad. Otras celdas agrupadas con ella solo necesitarán contener el puntero a su contenedor respectivo, ya que la primera celda corresponde a los nombres de calles que comienzan con "A", la segunda a "B", y así sucesivamente.
La base de datos se puede ampliar para incluir un campo de continente y ampliar el censo a otros continentes. Esto haría que los registros de un mismo grupo se correspondan con hogares de una calle que comience con la misma letra, en la misma ciudad, en el mismo continente.
Las celdas en el archivo de cuadrícula consistirían entonces en un encabezado de ciudad y seis agrupaciones (una para cada continente, sin incluir la Antártida ) de 26 celdas relacionadas con las calles con la misma letra inicial, en la misma ciudad, en el mismo continente y ahora podrían considerarse como una matriz tridimensional.
Dado que una sola entrada en el archivo de cuadrícula contiene punteros a todos los registros indexados por las claves especificadas: [4]
Sin embargo, debido a la naturaleza del archivo de cuadrícula, que le otorga sus ventajas, también existen algunas desventajas: [4]