Gridfile
Um Gridfile (engl. = Grade de grade) é uma estrutura de índice pelo menos bidimensional , a busca de dados tendo 2 ou mais critérios bastante acelerada. Com estruturas de dados unidimensionais tradicionais (por exemplo, tabela hash ), a busca por um critério é geralmente muito simples, enquanto a busca por um segundo critério consome muito tempo . Os arquivos de grade representam um tipo especial de hash no qual a função hash clássica é substituída por um diretório de grade.
Os arquivos de grade geral têm a dimensão k, o que significa que eles armazenam dados k-dimensionais com as teclas S1 ... Sk. Os arquivos de grade são uma das estruturas de dados simétricas , já que nenhum dos valores de chave é preferido, mas todas as chaves são sempre inseridas igualmente.
No arquivo de grade, por exemplo, ao pesquisar por três critérios, como um cubo tridimensional , o registro de dados relevante pode ser encontrado diretamente. Os dados geralmente não são armazenados no próprio arquivo de grade (o que ocuparia muito espaço se o cubo estivesse apenas moderadamente preenchido), mas apenas uma referência ao depósito no qual os dados desejados estão armazenados. Um depósito armazena vários registros de dados que estão próximos uns dos outros no arquivo de grade .
O chamado princípio de acesso a dois discos se aplica a um arquivo de grade. Isso significa que um registro de dados solicitado fica disponível após não mais do que duas solicitações para uma memória secundária . Para garantir isso, a estrutura do índice e os dados reais são armazenados em duas estruturas de dados separadas. Como a estrutura do índice é relativamente pequena em comparação com os dados a serem endereçados, idealmente também pode ser mantida na memória principal.
Os baldes são endereçados por meio das chamadas escalas, que formam a estrutura do índice. Uma escala é criada para cada dimensão k, que classifica os limites dos intervalos na dimensão correspondente e contém um índice para esta dimensão. Combinando as entradas nas escalas individuais, o intervalo correspondente pode ser determinado que contém os dados para as coordenadas procuradas.
Um arquivo de grade é insensível a clusters de dados, pois reage às propriedades do conteúdo como uma estrutura de dados adaptável por meio de divisão ou refinamento de dimensão (no caso de estouro de balde) e mesclagem (no caso de estouro de balde).
Veja também
Índice de banco de dados , quadtree , árvore Kd , árvore UB , R árvore , área árvore como alternativas
Links da web
- Palestra sobre sistemas de banco de dados na Universidade de Osnabrück , cap. 5
- Visão geral dos arquivos de grade (arquivo PDF; 350 kB)
