Hispanopedia WikiEn informática , un archivo de cuadrícula o cuadrícula de cubetas es un método de acceso puntual 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 disco y realizar búsquedas de datos complejas.
Proporciona una cuadrícula de n dimensiones, donde n representa cuántas claves se pueden usar para hacer referencia a un solo punto.
Los archivos de cuadrícula no contienen datos en sí mismos, sino que contienen referencias al bucket correcto.
Usos
Un archivo de cuadrícula se suele utilizar en casos donde un único valor puede ser referenciado por múltiples claves.
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 estructuras de archivos diseñadas originalmente para el acceso con una sola clave. Presentan diversas deficiencias, en particular para el acceso multiclave a archivos altamente dinámicos". [ 1 ]
En una estructura de datos unidimensional tradicional (por ejemplo, una tabla hash ), la búsqueda de un único 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.
Ejemplos
Base de datos del censo
Consideremos una base de datos con información de un censo. Cada registro representa un hogar y todos los registros se agrupan en categorías. Todos los registros de una categoría se pueden indexar por su 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 agrupan en conjuntos de 26, cada uno relacionado con nombres de calles de una ciudad que comienzan con una de las letras del alfabeto. Esta estructura puede considerarse como una matriz , tabla o cuadrícula con dos dimensiones que denominaremos ejes x e y.
Se puede considerar que el eje x representa la ciudad y el eje y cada una de las letras del alfabeto, o bien, la primera letra de cada calle.
Cada registro en esta estructura se conoce como celda. Cada celda contiene un puntero al depósito correspondiente en la base de datos donde se almacenan los datos. Puede ser necesaria una celda adicional, o encabezado de registro, para almacenar el nombre de la ciudad. Las demás celdas agrupadas con ella solo necesitarán contener el puntero a su respectivo depósito, ya que la primera celda corresponde a 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 que indique el continente, lo que permitiría extender el censo a otros continentes. De esta forma, los registros de una misma categoría corresponderían a hogares ubicados en una calle que comience con la misma letra, en la misma ciudad y en el mismo continente.
Las celdas del archivo de cuadrícula consistirían entonces en un encabezado de ciudad y seis grupos (uno por cada continente, sin incluir la Antártida ) de 26 celdas relacionadas con las calles que comienzan con la misma letra, en la misma ciudad, en el mismo continente y que ahora podrían considerarse como una matriz tridimensional.
Ventajas
Dado que una sola entrada en el archivo de cuadrícula contiene punteros a todos los registros indexados por las claves especificadas: [ 4 ]
- No se requieren cálculos especiales.
- Solo se recuperan los registros correctos.
- También se puede utilizar para consultas con una sola palabra clave de búsqueda.
- Fácil de extender a consultas sobre n claves de búsqueda.
- Mejora significativa en el tiempo de procesamiento para consultas con múltiples claves.
- Tiene un límite superior de acceso a dos discos para acceder a los datos. [ 1 ]
Desventajas
Sin embargo, debido a la naturaleza del archivo de cuadrícula, que le confiere sus ventajas, también existen algunas desventajas: [ 4 ]
- Impone espacio por encima
- Sobrecarga de rendimiento en la inserción y eliminación
Estructuras de datos relacionadas
Véase también
- Grafo reticular
- Cuadrícula (índice espacial)
- Índice (base de datos) , quadtree , árbol k -d , árbol UB , árbol R , árbol de rango como alternativas.
Referencias
- 1 2 J. Nievergelt, H. Hinterberger El archivo de cuadrícula: una estructura de archivo multiclave simétrica y adaptable . Institut für Informatik, ETH y KC Sevcik, 1984. Resumen, pág. 1.
- ↑ Donald Knuth . El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998. ISBN 0-201-89685-0. Sección 6.5: Búsqueda, págs. 564–566.
- ↑ Elmasri y Navathe, Fundamentos de sistemas de bases de datos , Tercera edición. Addison-Wesley, 2000. ISBN 0-201-54263-3. Sección 6.4.3: Archivos de cuadrícula, pág. 185.
- 1 2 "Archivo de cuadrícula" . cs.sfu.ca. Consultado el 27 de noviembre de 2016 .
- archivos informáticos
- Matrices