4430
правок
B-деревья без явного задания параметров кэша: различия между версиями
Материал из WEGA
B-деревья без явного задания параметров кэша (посмотреть исходный код)
Версия от 00:30, 7 февраля 2017
, 7 февраля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
== Основные результаты == | == Основные результаты == | ||
Первый словарь без явного задания параметров кэша предложил Прокоп [21], который показал, как расположить статическое бинарное дерево в памяти таким образом, чтобы поиск занимал O(logB n) переносов содержимого памяти. Это расположение, часто называемое расположением ван Эмде Боаса из-за того, что оно напоминает классическую структуру данных ван Эмде Боаса, также гарантирует, что поиск в диапазоне занимает O(logB n + k/ B) переносов содержимого памяти [2], где k – размер выходного значения. Обе границы являются оптимальными для поиска на основе сравнения. | |||
Первый динамический словарь без явного задания параметров кэша был предложен Бендером и др. [10]. Используя вариант расположения ван Эмде Боаса, алгоритм управления плотностью Итая и др. [10] и сбалансированные по весам B-деревья [5], авторы пришли к следующим результатам: | |||
'''Теорема 1 ([10]). Существует структура словаря словарь без явного задания параметров кэша, поддерживающая поиск за O(logB n) переносов содержимого памяти, а вставку и удаление – за O(logB n) амортизированных переносов содержимого памяти.''' | |||
