Файл сетки

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

Он предоставляет сетку из n измерений, где n представляет собой количество ключей, которые можно использовать для ссылки на одну точку.

Файлы сетки сами по себе не содержат никаких данных, а вместо этого содержат ссылки на правильный сегмент.

Использование

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

Файл сетки стал использоваться потому, что «традиционные файловые структуры, обеспечивающие многоключевой доступ к записям, например, инвертированные файлы, являются расширениями файловых структур, изначально предназначенных для одноключевого доступа. Они проявляют различные недостатки, в частности, для многоключевого доступа к высокодинамичным файлам. ." ^[1]

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

Файлы сетки представляют собой особый вид хеширования, при котором традиционный хеш заменяется каталогом сетки.

Примеры

База данных переписи населения

Источники: ^[2]^[3]

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

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

Можно считать, что ось X — это город, а ось Y — каждая буква алфавита или, альтернативно, первая буква каждой улицы.

Каждая запись в этой структуре называется ячейкой. Каждая ячейка будет содержать указатель на соответствующий сегмент в базе данных, где хранятся фактические данные. Для хранения названия города может потребоваться дополнительная ячейка или заголовок записи. Другие ячейки, сгруппированные с ней, должны будут содержать только указатель на соответствующий сегмент, поскольку первая ячейка соответствует названиям улиц, начинающимся с «А», вторая — с «Б» и так далее.

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

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

Преимущества

Поскольку одна запись в файле сетки содержит указатели на все записи, проиндексированные указанными ключами: ^[4]

Никаких специальных вычислений не требуется
Извлекаются только нужные записи
Также может использоваться для запросов с одним ключевым словом поиска.
Легко распространить на запросы по n ключам поиска.
Значительное сокращение времени обработки запросов с несколькими ключами.
Имеет верхнюю границу доступа к данным с двумя дисками. ^[1]

Недостатки

Однако из-за особенностей файла сетки, которые дают ему преимущества, есть и некоторые недостатки: ^[4]

Налагает накладные расходы на пространство
Накладные расходы на производительность при вставке и удалении

Связанные структуры данных

См. также

Решетчатый граф
Сетка (пространственный индекс)
Индекс (база данных) , квадродерево , k дерево -d , UB-дерево , R-дерево , дерево диапазонов в качестве альтернатив.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Дж. Нивергельт, Х. Хинтербергер Файл Grid: адаптируемая симметричная многоключевая файловая структура . Институт информатики, ETH и KC Sevcik, 1984. Аннотация, с. 1.
^ Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0 . Раздел 6.5: Поиск, стр. 564–566.
^ Эльмасри и Навате «Основы систем баз данных» , третье издание. Аддисон-Уэсли, 2000. ISBN 0-201-54263-3 . Раздел 6.4.3: Файлы сетки, стр. 6.4.3. 185.
^ Jump up to: Перейти обратно: ^а ^б «Файл сетки» . cs.sfu.ca. Проверено 27 ноября 2016 г.

[tgf-1] Jump up to: Перейти обратно: ^а ^б Дж. Нивергельт, Х. Хинтербергер Файл Grid: адаптируемая симметричная многоключевая файловая структура . Институт информатики, ETH и KC Sevcik, 1984. Аннотация, с. 1.

[2] Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0 . Раздел 6.5: Поиск, стр. 564–566.

[3] Эльмасри и Навате «Основы систем баз данных» , третье издание. Аддисон-Уэсли, 2000. ISBN 0-201-54263-3 . Раздел 6.4.3: Файлы сетки, стр. 6.4.3. 185.

[adv-4] Jump up to: Перейти обратно: ^а ^б «Файл сетки» . cs.sfu.ca. Проверено 27 ноября 2016 г.

[1]

[2]

[3]

[4]