Gridfile

Un Gridfile (engl. = Grid grille) est une structure d'index au moins bidimensionnelle , la recherche de données ayant 2 critères ou plus étant grandement accélérée. Avec les structures de données unidimensionnelles traditionnelles (par exemple, table de hachage ), la recherche d'un critère est généralement très simple, tandis que la recherche d'un deuxième critère prend beaucoup de temps . Les fichiers de grille représentent un type spécial de hachage dans lequel la fonction de hachage classique est remplacée par un répertoire de grille.

Les fichiers de grille générale ont la dimension k, ce qui signifie qu'ils stockent des données de dimensions k avec les touches S1 ... Sk. Les fichiers de grille sont l'une des structures de données symétriques , car aucune des valeurs de clé n'est préférée, mais toutes les clés sont toujours entrées de la même manière.

Dans le fichier de grille, par exemple, lors de la recherche de trois critères, comme un cube en trois dimensions , l'enregistrement de données pertinent peut être trouvé directement. Dans la plupart des cas, les données ne sont pas stockées dans le fichier de grille lui-même (ce qui prendrait trop d'espace si le cube n'est que modérément plein), mais uniquement une référence au compartiment dans lequel les données souhaitées sont stockées. Un compartiment stocke plusieurs enregistrements de données côte à côte dans le fichier de grille .

Le principe dit d'accès à deux disques s'applique à un fichier de grille. Cela signifie qu'un enregistrement de données demandé est disponible après pas plus de deux requêtes à une mémoire secondaire . Pour garantir cela, la structure d'index et les données réelles sont stockées dans deux structures de données distinctes. La structure d'index étant relativement petite par rapport aux données à adresser, elle peut idéalement également être conservée dans la mémoire principale.

Les buckets sont adressés à l'aide de ce que l'on appelle des échelles, qui forment la structure d'index. Une échelle est créée pour chaque dimension k, qui trie les limites des compartiments dans la dimension correspondante et contient un index pour cette dimension. En combinant les entrées dans les échelles individuelles, il est possible de déterminer le seau correspondant qui contient les données pour les coordonnées recherchées.

Un fichier de grille est insensible aux clusters de données, car il réagit aux propriétés du contenu en tant que structure de données adaptative via le fractionnement ou le raffinement de dimension (dans le cas d'un débordement de compartiment) et la fusion (dans le cas d'un sous-dépassement de compartiment).

Voir également

Indice de base de données , quadtree , arbre Kd , arbre UB , arbre R , zone arbre comme des alternatives

liens web