En informática , un archivo de cuadrícula o una cuadrícula de cubo es un método de acceso de puntos que divide un espacio en una cuadrícula no periódica donde una o más celdas de la cuadrícula se refieren a un pequeño conjunto de puntos. Los archivos de cuadrícula (una estructura de datos simétrica ) proporcionan un método eficaz de 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 hacer referencia a un solo punto.
Los archivos de cuadrícula no contienen datos en sí mismos, sino que contienen referencias al depósito correcto .
Usos
Un archivo de cuadrícula se usa generalmente en los casos en que varias claves pueden hacer referencia a un solo valor.
Se empezó a utilizar un archivo de cuadrícula porque "las estructuras de archivo tradicionales que brindan acceso de múltiples claves a los registros, por ejemplo, archivos invertidos, son extensiones de estructuras de archivos diseñadas originalmente para el acceso de una sola clave. Manifiestan varias deficiencias, en particular para el acceso de múltiples claves 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 simple, 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 de
Base de datos del censo [2] [3]
Considere una base de datos que contenga datos de un censo. Un solo registro representa un solo hogar y todos los registros se agrupan en depósitos. Todos los registros de un depósito se pueden indexar por su ciudad (que es la misma para todos los registros del depósito) y las calles de esa ciudad cuyos nombres comienzan con la misma letra.
Se puede usar un archivo de cuadrícula para proporcionar un índice eficiente para esta estructura, donde los registros vienen 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 , tabla o cuadrícula con dos dimensiones que llamaremos ejes xey.
Se puede considerar que el eje x es la ciudad y el eje y es 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 depósito apropiado en la base de datos donde se almacenan los datos reales. Es posible que se requiera una celda adicional o un encabezado de registro para almacenar el nombre de la ciudad. Otras celdas agrupadas con él solo necesitarán contener el puntero a su respectivo depósito, ya que la primera celda corresponde a los nombres de las calles que comienzan con "A", la segunda a "B", y así sucesivamente.
La base de datos se puede ampliar aún más para contener un campo de continente para expandir el censo a otros continentes. Esto haría que los registros en el mismo cubo correspondan a hogares en una calle que comience con la misma letra, en la misma ciudad, en el mismo continente.
Las celdas del archivo de cuadrícula consistirían entonces en un encabezado de ciudad y seis (una para cada continente, sin incluir la Antártida ) agrupaciones de 26 celdas relacionadas con las calles con la misma letra inicial, en la misma ciudad, en el mismo continente y ahora podría pensarse 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 de clave de búsqueda única
- Fácil de ampliar a consultas sobre n claves de búsqueda
- Mejora significativa en el tiempo de procesamiento para consultas de 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 da sus ventajas, también existen algunas desventajas: [4]
- Impone espacio por encima de la cabeza
- Sobrecarga de rendimiento en la inserción y eliminación
Estructuras de datos relacionadas
- archivo de cuadrícula multicapa
- archivos de cuadrícula gemela
- Archivo BANG
Ver también
- Gráfico de celosía
- Cuadrícula (índice espacial)
- Index (base de datos) , Quadtree , Kd-tree , UB-tree , R-tree , range tree como alternativas.
Referencias
- ^ a b J. Nievergelt, H. Hinterberger El archivo de cuadrícula: una estructura de archivo simétrica y adaptable . Institut fur Informatik, ETH y KC Sevcik, 1984. Resumen, pág. 1.
- ^ Donald Knuth . El arte de la programación informática , volumen 3: clasificació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 & Navathe Fundamentals of Database Systems , tercera edición. Addison-Wesley, 2000. ISBN 0-201-54263-3 . Sección 6.4.3: Archivos de cuadrícula, pág.185.
- ^ a b "Archivo de cuadrícula" . cs.sfu.ca . Consultado el 27 de noviembre de 2016 .