Arquivo de grade - Grid file

Na ciência da computação , um arquivo de grade ou grade de balde é um método de acesso de ponto que divide um espaço em uma grade não periódica onde uma ou mais células da grade se referem a um pequeno conjunto de pontos. Os arquivos de grade (uma estrutura de dados simétrica ) fornecem um método eficiente de armazenamento desses índices em disco para realizar pesquisas de dados complexas.

Ele fornece uma grade de n- dimensões, onde n representa quantas chaves podem ser usadas para fazer referência a um único ponto.

Os arquivos de grade não contêm nenhum dado, mas, em vez disso, referências ao intervalo correto .

Usos

Um arquivo de grade é geralmente usado nos casos em que um único valor pode ser referenciado por várias chaves.

Um arquivo de grade começou a ser usado porque "estruturas de arquivo tradicionais que fornecem acesso de várias teclas a registros, por exemplo, arquivos invertidos, são extensões de estruturas de arquivos originalmente projetadas para acesso de uma única chave. Eles manifestam várias deficiências, em particular para acesso de várias teclas a arquivos altamente dinâmicos . "

Em uma estrutura de dados unidimensional tradicional (por exemplo, hash ), uma pesquisa em um único critério é geralmente muito simples, mas pesquisar um segundo critério pode ser muito mais complexo.

Os arquivos de grade representam um tipo especial de hash, em que o hash tradicional é substituído por um diretório de grade.

Exemplos

Banco de dados do censo

Considere um banco de dados contendo dados de um censo. Um único registro representa uma única família e todos os registros são agrupados em grupos. Todos os registros em um depósito podem ser indexados por sua cidade (que é a mesma para todos os registros no depósito) e pelas ruas dessa cidade cujos nomes começam com a mesma letra.

Um arquivo de grade pode ser usado para fornecer um índice eficiente para essa estrutura, onde os registros vêm em agrupamentos de 26, cada um deles relacionado a nomes de ruas em uma cidade começando com uma das letras do alfabeto. Essa estrutura pode ser pensada como um array , tabela ou grade com duas dimensões que chamaremos de eixos xey.

Pode-se considerar o eixo x como a cidade e o eixo y como cada uma das letras do alfabeto ou, alternativamente, a primeira letra de cada rua.

Cada registro nesta estrutura é conhecido como uma célula. Cada célula conterá um ponteiro para o intervalo apropriado no banco de dados onde os dados reais estão armazenados. Uma célula extra, ou cabeçalho de registro, pode ser necessária para armazenar o nome da cidade. Outras células agrupadas com ele só precisarão conter o ponteiro para seu respectivo balde, uma vez que a primeira célula corresponde aos nomes de ruas que começam com "A", a segunda a "B" e assim por diante.

O banco de dados pode ser estendido para conter um campo de continente para expandir o censo para outros continentes. Isso faria com que registros no mesmo balde correspondessem a domicílios em uma rua começando com a mesma letra, na mesma cidade, no mesmo continente.

As células no arquivo de grade consistiriam em um cabeçalho de cidade e seis (um para cada continente, não incluindo a Antártica ) agrupamentos de 26 células relacionadas às ruas com a mesma letra inicial, na mesma cidade, no mesmo continente e agora pode ser pensado como uma matriz tridimensional.

Vantagens

Uma vez que uma única entrada no arquivo de grade contém ponteiros para todos os registros indexados pelas chaves especificadas:

  • Nenhum cálculo especial é necessário
  • Apenas os registros corretos são recuperados
  • Também pode ser usado para consultas de uma única chave de pesquisa
  • Fácil de estender para consultas em n chaves de pesquisa
  • Melhoria significativa no tempo de processamento para consultas de várias chaves
  • Possui um limite superior de acesso a dois discos para acessar dados.

Desvantagens

No entanto, devido à natureza do arquivo de grade, o que dá a ele suas vantagens, também existem algumas desvantagens:

  • Impõe espaço acima da cabeça
  • Sobrecarga de desempenho na inserção e exclusão

Estruturas de dados relacionadas

Veja também

Referências