Изменения

Перейти к: навигация, поиск

Индексация данных. Упорядоченные и хеш-индексы

175 байт добавлено, 12:43, 27 декабря 2021
→‎Расширяемое хеширование
=== Расширяемое хеширование ===
* Большое Изначально создаем большое количество корзин, сильно больше чем требуется* Несколько . Пока мало данных Храним несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницупо отдельной странице.** Обычно - последовательныхвыбираем набор корзин, которые идут подряд** Разделение корзин при При переполнении страницы разделенем корзины на две страницы
* Не работает при плохой хеш-функции, но у нас хорошая
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
* Каждой такой группе выделим по странице
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/82034»

Навигация