Линейное хеширование

Линейное хеширование ( LH ) — это динамическая структура данных, которая реализует хеш-таблицу и увеличивает или сжимает одну корзину за раз. Его изобрел Витольд Литвин в 1980 году. ^[1]^[2] Его проанализировали Баеза-Йейтс и Соза-Полман. ^[3] Это первая из ряда схем, известных как динамическое хеширование. ^[3]^[4] такие как линейное хеширование Ларсона с частичным расширением, ^[5] Линейное хеширование с разделением приоритетов, ^[6] Линейное хеширование с частичным расширением и разделением приоритетов, ^[7] или рекурсивное линейное хеширование. ^[8]

Файловая структура структуры данных динамического хеширования адаптируется к изменениям размера файла, что позволяет избежать дорогостоящей периодической реорганизации файла. ^[4] Файл линейного хеширования расширяется за счет разделения заранее определенного сегмента на два и сжимается за счет объединения двух заранее определенных сегментов в один. Повод для реконструкции зависит от разновидности схемы; это может быть переполнение сегмента или коэффициент загрузки (т. е. количество записей, разделенное на количество сегментов), выходящий за пределы заранее определенного диапазона. ^[1] В линейном хешировании есть два типа сегментов: те, которые должны быть разделены, и те, которые уже разделены. В то время как расширяемое хеширование разделяет только переполненные сегменты, спиральное хеширование (также известное как спиральное хранилище) распределяет записи по сегментам неравномерно, так что сегменты с высокими затратами на вставку, удаление или извлечение оказываются первыми в очереди на разделение. ^[5]

Линейное хеширование также было преобразовано в масштабируемую распределенную структуру данных LH* . В LH* каждый сегмент находится на отдельном сервере. ^[9] Сам LH* был расширен, чтобы обеспечить доступность данных в случае сбоя сегментов. ^[10] Операции на основе ключей (вставка, удаление, обновление, чтение) в LH и LH* занимают максимальное постоянное время, независимое от количества сегментов и, следовательно, записей. ^[1]^[10]

Детали алгоритма

Записи в LH или LH* состоят из ключа и содержимого, причем последнее в основном включает все остальные атрибуты записи. ^[1]^[10] Их хранят в ведрах. Например, в реализации Эллиса сегмент представляет собой связанный список записей. ^[2] Файл позволяет выполнять операции CRUD на основе ключей, создавать или вставлять, читать, обновлять и удалять, а также операции сканирования, при которых сканируются все записи, например, для выполнения операции выбора базы данных по неключевому атрибуту. ^[10] Записи хранятся в сегментах, нумерация которых начинается с 0. ^[10]

Ключевое отличие от таких схем, как расширяемое хеширование Феджина, заключается в том, что по мере расширения файла за счет вставок одновременно разбивается только один сегмент, а порядок разделения сегментов уже предопределен. ^[11]

Хэш-функции

Хэш-функция $h_{i}(c)$ возвращает индекс сегмента, начинающийся с 0, который содержит запись с ключом $c$ . Когда сегмент, использующий хэш-функцию $h_{i}$ разделен на два новых сегмента, хэш-функция $h_{i}$ заменяется на $h_{i+1}$ для обоих этих новых ведер. В любое время не более двух хэш-функций $h_{l}$ и $h_{l+1}$ используются; такой, что $l$ соответствует текущему уровню . Семейство хэш-функций $h_{i}(c)$ также называется динамической хэш-функцией.

Как правило, значение $i$ в $h_{i}$ соответствует количеству крайних правых двоичных цифр ключа $c$ которые используются для разделения ведер. Эту динамическую хеш-функцию можно арифметически выразить как ${\textstyle h_{i}(c)\mapsto (c{\bmod {2}}^{i})}$ . Обратите внимание, что когда общее количество сегментов равно одному, $i=0$ .

Выполните приведенные ниже расчеты, чтобы определить правильную функцию хеширования для данного ключа хеширования. $c$ . ^[10]

# l represents the current level# s represents the split pointer indexa = h_l(c)if (a < s): a = h_{l+1}(c)

Разделенное управление

Алгоритмы линейного хеширования могут использовать только контролируемые разделения или как контролируемые, так и неконтролируемые разделения.

Управляемое разделение происходит, если разделение выполняется всякий раз, когда коэффициент загрузки , который отслеживается файлом, превышает заранее определенный порог. ^[10] Если хэш-индекс использует контролируемое разделение, сегменты могут переполняться с помощью связанных блоков переполнения. Когда коэффициент загрузки превышает установленный порог, сегмент, назначенный указателем разделения, разделяется. Вместо использования коэффициента загрузки этот порог также можно выразить как процент занятости, и в этом случае максимальное количество записей в хеш-индексе равно (процент занятости)*(максимальное количество записей на непереполненную корзину)*(количество ведра). ^[12]

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

Сжатие файла происходит в некоторых реализациях алгоритма LH, если контролируемое разделение приводит к падению коэффициента загрузки ниже порогового значения. В этом случае будет запущена операция слияния, которая отменит последнее разделение и сбросит состояние файла. ^[10]

Разделить указатель

Индекс следующего разделяемого сегмента является частью состояния файла и называется указателем разделения. $s$ . Указатель разделения соответствует первому сегменту, который использует хэш-функцию. $h_{l}$ вместо $h_{l+1}$ . ^[10]

Например, если числовые записи вставляются в хэш-индекс в соответствии с их крайними правыми двоичными цифрами, сегмент, соответствующий добавленному сегменту, будет разделен. Таким образом, если у нас есть сегменты, помеченные как 000, 001, 10, 11, 100, 101, мы разделим сегмент 10, потому что мы добавляем и создаем следующий последовательный сегмент 110. Это даст нам сегменты 000, 001, 010. , 11, 100, 101, 110. ^[12]

Когда сегмент разделен, указатель разделения и, возможно, уровень обновляются в соответствии со следующим: уровень равен 0, когда индекс линейного хеширования имеет только 1 сегмент. ^[10]

# l represents the current level# s represents the split pointer indexs = s + 1if (s >= 2^l):     l = l + 1    s = 0

Левый*

Основная задача LH* — позволить клиенту файла LH* найти корзину, в которойзапись сохраняется, даже если клиент не знает состояние файла. Клиенты фактически хранятсвою версию состояния файла, которая изначально представляет собой просто знание первого сегмента, а именно сегмента 0. На основе состояния файла клиент вычисляет адресkey и отправляет запрос в эту корзину. В сегменте запрос проверяется и, еслизапись не находится в корзине, она пересылается. В достаточно стабильной системе, т.е. если во время обработки запроса происходит только одно разделение или слияние, это можетпоказать, что существует не более двух нападающих. После пересылки последний сегмент отправляет Сообщение о настройке изображения для клиента, состояние которого теперь ближе к состоянию распространяемого файла. ^[10] Хотя форварды достаточно редки для активных клиентов, их число может быть еще сокращено за счет дополнительного обмена информацией между серверы и клиенты ^[13]

Другие объекты недвижимости

Расчет состояния файла

Состояние файла состоит из разделенного указателя $s$ и уровень $l$ . Если исходный файл начинался с $N=1$ ведер, затем количество ведер $n$ и состояние файла связаны через ^[13]

$n=2^{l}+s$ .

Принятие в языковых системах

Грисволд и Таунсенд ^[14] обсудили внедрение линейного хеширования в языке Icon . Они обсудили варианты реализации алгоритма динамических массивов , используемого в линейном хешировании, и представили сравнение производительности с использованием списка тестовых приложений Icon.

Принятие в системах баз данных

Линейное хеширование используется в системе баз данных Беркли (BDB) , которая, в свою очередь, используется во многих программных системах, используя реализацию C, полученную из статьи CACM и впервые опубликованную в Usenet в 1988 году Эсмондом Питтом.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Литвин, Витольд (1980), «Линейное хеширование: новый инструмент для адресации файлов и таблиц» (PDF) , Proc. 6-я конференция по очень большим базам данных : 212–223.
^ Перейти обратно: ^а ^б Эллис, Карла Шлаттер (июнь 1987 г.), «Параллелизм в линейном хешировании», Транзакции ACM в системах баз данных , 12 (2): 195–217, doi : 10.1145/22952.22954 , S2CID 14260177
^ Перейти обратно: ^а ^б Баеза-Йейтс, Рикардо; Соза-Полман, Гектор (1998), «Пересмотренный анализ линейного хеширования» (PDF) , Nordic Journal of Computing : 70–85, S2CID 7497598 , заархивировано из оригинала (PDF) 7 марта 2019 г.
^ Перейти обратно: ^а ^б Энбоди, Ричард; Ду, ХК (июнь 1988 г.), «Схемы динамического хеширования», ACM Computing Surveys , 20 (2): 85–113, doi : 10.1145/46157.330532 , S2CID 1437123
^ Перейти обратно: ^а ^б Ларсон, Пер-Оке (апрель 1988 г.), «Динамические хеш-таблицы», Communications of the ACM , 31 (4): 446–457, doi : 10.1145/42404.42410 , S2CID 207548097
^ Рухте, Уиллард; Тарп, Алан (февраль 1987 г.), «Линейное хеширование с разделением приоритетов: метод повышения производительности поиска при линейном хешировании», Третья международная конференция IEEE по инженерии данных : 2–9.
^ Манолопулос, Яннис; Лоренцос, Н. (1994), «Производительность схем линейного хеширования для поиска первичного ключа», Information Systems , 19 (5): 433–446, doi : 10.1016/0306-4379(94)90005-1
^ Рамамоханарао, К.; Сакс-Дэвис, Р. (сентябрь 1984 г.), «Рекурсивное линейное хеширование», Транзакции ACM в базах данных , 9 (3): 369–391, doi : 10.1145/1270.1285 , S2CID 18577730
^ Литвин, Витольд; Неймат, Мари-Анн; Шнайдер, Донаван А. (1993), «LH: линейное хеширование для распределенных файлов», ACM SIGMOD Record , 22 (2): 327–336, doi : 10.1145/170036.170084 , S2CID 259938726
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Литвин, Витольд; Мусса, Рим; Шварц, Томас (сентябрь 2005 г.), «LH*RS — высокодоступная масштабируемая распределенная структура данных» , Транзакции ACM в системах баз данных , 30 (3): 769–811, doi : 10.1145/1093382.1093386 , S2CID 1802386
^ Феджин, Рональд; Нивергельт, Юрг; Пиппенджер, Николас; Стронг, Рэймонд (сентябрь 1979 г.), «Расширяемое хеширование — метод быстрого доступа к динамическим файлам» , Транзакции ACM в системах баз данных , 4 (2): 315–344, doi : 10.1145/320083.320092 , S2CID 2723596
^ Перейти обратно: ^а ^б Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. ISBN 978-1-260-08450-4 .
^ Перейти обратно: ^а ^б Чабкинян, Хуан; Шварц, Томас (2016), «Fast LH*», Международный журнал параллельного программирования , 44 (4): 709–734, doi : 10.1007/s10766-015-0371-8 , S2CID 7448240
^ Грисволд, Уильям Г .; Таунсенд, Грегг М. (апрель 1993 г.), «Проектирование и реализация динамического хеширования для наборов и таблиц в Icon» , Software: Practice and Experience , 23 (4): 351–367, doi : 10.1002/spe.4380230402 , S2CID 11595927

Внешние ссылки

См. также

[WL80-1] Перейти обратно: ^а ^б ^с ^д Литвин, Витольд (1980), «Линейное хеширование: новый инструмент для адресации файлов и таблиц» (PDF) , Proc. 6-я конференция по очень большим базам данных : 212–223.

[Ellis-2] Перейти обратно: ^а ^б Эллис, Карла Шлаттер (июнь 1987 г.), «Параллелизм в линейном хешировании», Транзакции ACM в системах баз данных , 12 (2): 195–217, doi : 10.1145/22952.22954 , S2CID 14260177

[BS-3] Перейти обратно: ^а ^б Баеза-Йейтс, Рикардо; Соза-Полман, Гектор (1998), «Пересмотренный анализ линейного хеширования» (PDF) , Nordic Journal of Computing : 70–85, S2CID 7497598 , заархивировано из оригинала (PDF) 7 марта 2019 г.

[RD-4] Перейти обратно: ^а ^б Энбоди, Ричард; Ду, ХК (июнь 1988 г.), «Схемы динамического хеширования», ACM Computing Surveys , 20 (2): 85–113, doi : 10.1145/46157.330532 , S2CID 1437123

[AL-5] Перейти обратно: ^а ^б Ларсон, Пер-Оке (апрель 1988 г.), «Динамические хеш-таблицы», Communications of the ACM , 31 (4): 446–457, doi : 10.1145/42404.42410 , S2CID 207548097

[ruchte-6] Рухте, Уиллард; Тарп, Алан (февраль 1987 г.), «Линейное хеширование с разделением приоритетов: метод повышения производительности поиска при линейном хешировании», Третья международная конференция IEEE по инженерии данных : 2–9.

[7] Манолопулос, Яннис; Лоренцос, Н. (1994), «Производительность схем линейного хеширования для поиска первичного ключа», Information Systems , 19 (5): 433–446, doi : 10.1016/0306-4379(94)90005-1

[RS-8] Рамамоханарао, К.; Сакс-Дэвис, Р. (сентябрь 1984 г.), «Рекурсивное линейное хеширование», Транзакции ACM в базах данных , 9 (3): 369–391, doi : 10.1145/1270.1285 , S2CID 18577730

[WL93-9] Литвин, Витольд; Неймат, Мари-Анн; Шнайдер, Донаван А. (1993), «LH: линейное хеширование для распределенных файлов», ACM SIGMOD Record , 22 (2): 327–336, doi : 10.1145/170036.170084 , S2CID 259938726

[LMS-10] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Литвин, Витольд; Мусса, Рим; Шварц, Томас (сентябрь 2005 г.), «LH*RS — высокодоступная масштабируемая распределенная структура данных» , Транзакции ACM в системах баз данных , 30 (3): 769–811, doi : 10.1145/1093382.1093386 , S2CID 1802386

[Fagin-11] Феджин, Рональд; Нивергельт, Юрг; Пиппенджер, Николас; Стронг, Рэймонд (сентябрь 1979 г.), «Расширяемое хеширование — метод быстрого доступа к динамическим файлам» , Транзакции ACM в системах баз данных , 4 (2): 315–344, doi : 10.1145/320083.320092 , S2CID 2723596

[:0-12] Перейти обратно: ^а ^б Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. ISBN 978-1-260-08450-4 .

[CS-13] Перейти обратно: ^а ^б Чабкинян, Хуан; Шварц, Томас (2016), «Fast LH*», Международный журнал параллельного программирования , 44 (4): 709–734, doi : 10.1007/s10766-015-0371-8 , S2CID 7448240

[14] Грисволд, Уильям Г .; Таунсенд, Грегг М. (апрель 1993 г.), «Проектирование и реализация динамического хеширования для наборов и таблиц в Icon» , Software: Practice and Experience , 23 (4): 351–367, doi : 10.1002/spe.4380230402 , S2CID 11595927

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]