Файл сетки
В информатике файл сетки или сетка бакета — это метод доступа к точке , который разбивает пространство на непериодическую сетку, где одна или несколько ячеек сетки ссылаются на небольшой набор точек. Файлы сетки ( симметричная структура данных ) предоставляют эффективный метод хранения этих индексов на диске для выполнения сложных поисков данных.
Он предоставляет сетку из n измерений, где n представляет собой количество ключей, которые можно использовать для ссылки на одну точку.
Файлы сетки не содержат сами по себе никаких данных, но вместо этого содержат ссылки на правильный контейнер.
Использует
Файл сетки обычно используется в случаях, когда на одно значение могут ссылаться несколько ключей.
Файл сетки начал использоваться, поскольку «традиционные файловые структуры, которые обеспечивают многоключевой доступ к записям, например, инвертированные файлы, являются расширениями файловых структур, изначально разработанных для одноключевого доступа. Они проявляют различные недостатки, в частности, для многоключевого доступа к высокодинамичным файлам». [1]
В традиционной одномерной структуре данных (например, хэше ) поиск по одному критерию обычно очень прост, но поиск по второму критерию может оказаться гораздо более сложным.
Файлы сетки представляют собой особый вид хеширования, в котором традиционный хеш заменяется каталогом сетки.
Примеры
База данных переписи населения
Источники: [2] [3]
Рассмотрим базу данных, содержащую данные переписи. Одна запись представляет одно домохозяйство, и все записи сгруппированы в корзины. Все записи в корзине могут быть проиндексированы либо по их городу (который одинаков для всех записей в корзине), либо по улицам в этом городе, названия которых начинаются с той же буквы.
Файл сетки может быть использован для предоставления эффективного индекса для этой структуры, где записи группируются по 26, каждая из которых относится к названиям улиц в городе, начинающимся с одной из букв алфавита. Эту структуру можно рассматривать как массив , таблицу или сетку с двумя измерениями, которые мы будем называть осями x и y.
Можно считать, что ось x — это город, а ось y — каждая из букв алфавита или, в качестве альтернативы, первая буква каждой улицы.
Каждая запись в этой структуре называется ячейкой. Каждая ячейка будет содержать указатель на соответствующий сегмент в базе данных, где хранятся фактические данные. Для хранения названия города может потребоваться дополнительная ячейка или заголовок записи. Другие ячейки, сгруппированные с ней, должны будут содержать только указатель на соответствующий сегмент, поскольку первая ячейка соответствует названиям улиц, начинающимся с «A», вторая — с «B» и т. д.
Базу данных можно расширить, включив в нее поле континента, чтобы распространить перепись на другие континенты. Это приведет к тому, что записи в одном и том же сегменте будут соответствовать домохозяйствам на улице, начинающейся с той же буквы, в том же городе, на том же континенте.
Ячейки в файле сетки тогда будут состоять из заголовка города и шести (по одной на каждый континент, не включая Антарктиду ) групп по 26 ячеек, относящихся к улицам с одинаковой начальной буквой, в одном городе, на одном континенте, и теперь их можно будет рассматривать как трехмерный массив.
Преимущества
Поскольку одна запись в файле сетки содержит указатели на все записи, индексированные указанными ключами: [4]
- Никаких специальных вычислений не требуется.
- Извлекаются только нужные записи.
- Может также использоваться для запросов с одним ключевым словом поиска.
- Легко расширить до запросов по n ключам поиска
- Значительное улучшение времени обработки многоключевых запросов
- Имеет верхнюю границу доступа к двум дискам для доступа к данным. [1]
Недостатки
Однако, из-за природы файла сетки, которая дает ему преимущества, существуют и некоторые недостатки: [4]
- Оставляет пространство над головой
- Снижение производительности при вставке и удалении
Связанные структуры данных
- Многослойный файл сетки
- Файлы двойной сетки
- Файл BANG
Смотрите также
- Решётчатый граф
- Сетка (пространственный индекс)
- Индекс (база данных) , квадродерево , k -d дерево , UB-дерево , R-дерево , диапазонное дерево в качестве альтернатив.
Ссылки
- ^ ab J. Nievergelt, H. Hinterberger Файл сетки: адаптируемая симметричная структура файла с несколькими ключами . Institut fur Informatik, ETH и KC Sevcik, 1984. Аннотация, стр. 1.
- ^ Дональд Кнут . Искусство программирования , том 3: Сортировка и поиск , второе издание. Addison-Wesley, 1998. ISBN 0-201-89685-0 . Раздел 6.5: Поиск, стр. 564–566.
- ^ Elmasri & Navathe Fundamentals of Database Systems , Third Edition. Addison-Wesley, 2000. ISBN 0-201-54263-3 . Раздел 6.4.3: Grid Files, стр. 185.
- ^ ab "Файл сетки". cs.sfu.ca . Получено 2016-11-27 .
