Спиральное хеширование

Спиральное хеширование , также известное как спиральное хранилище, представляет собой расширяемую систему хранения данных. алгоритм хеширования. ^[1]^[2]^[3]^[4]^[5] Как и во всех схемах хеширования, спиральное хеширование хранит записи в различном количестве сегментов, используя для адресации ключ записи. В расширяющемся файле линейного хеширования сегменты делятся в заранее определенном порядке. Это приводит к добавлению нового сегмента в конец файла. Хотя это позволяет осуществлять постепенную реорганизацию файла, ожидаемое количество записей во вновь созданном сегменте и сегменте, который он разделяет, падает вдвое по сравнению с предыдущим числом. Было предпринято несколько попыток смягчить это внезапное падение использования пространства. Спиральное хранилище Мартина использует другой подход. Файл состоит из нескольких непрерывно пронумерованных сегментов. Корзины с меньшим номером (слева) имеют большее ожидаемое количество записей. Когда файл расширяется, крайний левый сегмент заменяется двумя сегментами справа. Существуют некоторые варианты этой идеи. ^[6] ^[7]^[8]

Спиральное хеширование требует однородной хэш-функции ключей записей в единичном интервале. $[0,1]$ . Если хеш-файл начинается с ведра $S$ , ключ $k$ отображается в действительное число $x=S+h(k)\in [S,S+1]$ . Конечный адрес затем вычисляется как $\lfloor d^{x}\rfloor$ где $d$ является «коэффициентом расширения». Когда $S$ увеличивается примерно $d$ новые сегменты создаются справа. Ларсон ^[9] провели эксперименты, которые показали, что линейное хеширование по-прежнему превосходит спиральное хеширование по производительности.

См. также

Ссылки

^ Мартин, Дж.Н. (1979), «Спиральное хранилище», Tech. Репутация 27, унив. Уорик, Ковентри, Великобритания
^ Маллин, Джеймс К. (1981), «Тщательно контролируемое линейное хеширование без отдельного хранилища переполнения», BIT Numerical Mathematics , 21 (4): 390–400, doi : 10.1007/BF01932837 , S2CID 43311559
^ Маллин, Джеймс К. (1985), «Спиральное хранилище: эффективное динамическое хеширование с постоянной производительностью», The Computer Journal , 28 (3): 330–334, doi : 10.1093/comjnl/28.3.330
^ Чу, Дж. Х.; Нотт, Г.Д. (1994), «Анализ спирального хеширования», The Computer Journal , 37 (8): 715-719, doi : 10.1093/comjnl/37.8.715.
^ Энбоди, Ричард; Ду, ХК (июнь 1988 г.), «Схемы динамического хеширования», ACM Computing Surveys , 20 (2): 85–113, doi : 10.1145/46157.330532 , S2CID 1437123
^ Маллин, Джеймс К. (1984), «Унифицированное динамическое хеширование», Материалы 10-й Международной конференции по очень большим базам данных (VLDB)
^ Каваго, К. (1985), «Модифицированное динамическое хеширование», Труды международной конференции SIGMOD по управлению данными.
^ Чанг, Е-Ин; Ли, Чиен-И; ЧангЛио, Ванн-Бэй (1999), «Линейное спиральное хеширование для расширяемых файлов», IEEE Transactions on Knowledge and Data Engineering , 11 (6)
^ Ларсон, Пер-Оке (апрель 1988 г.), «Динамические хеш-таблицы», Communications of the ACM , 31 (4): 446–457, doi : 10.1145/42404.42410 , S2CID 207548097

[Martin-1] Мартин, Дж.Н. (1979), «Спиральное хранилище», Tech. Репутация 27, унив. Уорик, Ковентри, Великобритания

[Mullin81-2] Маллин, Джеймс К. (1981), «Тщательно контролируемое линейное хеширование без отдельного хранилища переполнения», BIT Numerical Mathematics , 21 (4): 390–400, doi : 10.1007/BF01932837 , S2CID 43311559

[Mullin85-3] Маллин, Джеймс К. (1985), «Спиральное хранилище: эффективное динамическое хеширование с постоянной производительностью», The Computer Journal , 28 (3): 330–334, doi : 10.1093/comjnl/28.3.330

[CK-4] Чу, Дж. Х.; Нотт, Г.Д. (1994), «Анализ спирального хеширования», The Computer Journal , 37 (8): 715-719, doi : 10.1093/comjnl/37.8.715.

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

[Mullin84-6] Маллин, Джеймс К. (1984), «Унифицированное динамическое хеширование», Материалы 10-й Международной конференции по очень большим базам данных (VLDB)

[Ka85-7] Каваго, К. (1985), «Модифицированное динамическое хеширование», Труды международной конференции SIGMOD по управлению данными.

[Chang-8] Чанг, Е-Ин; Ли, Чиен-И; ЧангЛио, Ванн-Бэй (1999), «Линейное спиральное хеширование для расширяемых файлов», IEEE Transactions on Knowledge and Data Engineering , 11 (6)

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]