Gridfile

Gridfile (Engl. = Сетка решетки) представляет собой по меньшей мере , двумерную структуру индекса , то поиск данных , имеющих 2 или более критериев значительно ускоряется. При использовании традиционных одномерных структур данных (например, хэш-таблицы ) поиск одного критерия обычно очень прост, в то время как поиск второго критерия занимает очень много времени . Файлы сетки представляют собой особый тип хеширования, в котором классическая хеш-функция заменяется каталогом сетки.

Файлы общей сетки имеют размерность k, что означает, что они хранят k-мерные данные с ключами S1 ... Sk. Файлы сетки являются одной из симметричных структур данных , поскольку ни одно из значений ключа не является предпочтительным, но все ключи всегда вводятся одинаково.

В файле сетки, например, при поиске трех критериев, таких как трехмерный куб, соответствующая запись данных может быть найдена напрямую. В большинстве случаев данные хранятся не в самом файле сетки (который занял бы слишком много места, если куб был лишь умеренно заполнен), а только в виде ссылки на сегмент, в котором хранятся желаемые данные. В корзине хранится несколько записей данных, расположенных рядом друг с другом в файле сетки .

К файлу сетки применяется так называемый принцип доступа к двум дискам. Это означает, что запрошенная запись данных доступна не более чем после двух запросов во вторичную память. Чтобы гарантировать это, структура индекса и фактические данные хранятся в двух отдельных структурах данных. Поскольку структура индекса относительно мала по сравнению с адресуемыми данными, в идеале ее также можно хранить в основной памяти.

Сегменты адресуются с помощью так называемых шкал, которые образуют структуру индекса. Для каждого измерения k создается шкала, которая сортирует границы сегментов в соответствующем измерении и содержит индекс для этого измерения. Комбинируя записи в отдельных шкалах, можно определить соответствующий сегмент, содержащий данные для искомых координат.

Файл сетки нечувствителен к кластерам данных, поскольку он реагирует на свойства содержимого как на адаптивную структуру данных посредством разделения или уточнения измерений (в случае переполнения сегмента) и слияния (в случае недостаточного заполнения сегмента).

Смотри тоже

Индекс базы данных , квадранты , Kd дерево , UB дерево , R дерево , площадь дерево в качестве альтернативы

веб ссылки