B-деревья без явного задания параметров кэша
Ключевые слова и синонимы
Деревья поиска без явного задания параметров кэша; словарь без явного задания параметров кэша
Постановка задачи
Память в компьютерах устроена иерархическим образом, причем время доступа к каждому уровню значительно различается. Таким образом, скорость доступа зависит исключительно от того, на каком самом внутреннем уровне находятся данные, к которым осуществляется доступ. При анализе работы алгоритмов стандартная RAM-модель (или модель фон Неймана) не способна воспроизвести этот эффект; поэтому для более точного моделирования ситуации были введены модели с внешней памятью. Чаще всего в качестве такой модели используется модель ввода-вывода [1], также называемая моделью внешней памяти или моделью обращений к диску. Модель ввода-вывода аппроксимирует иерархию памяти при помощи моделирования двух уровней, из которых внутренний уровень имеет размер M, внешний имеет неограниченный размер, а перенос данных между уровнями осуществляется блоками по B последовательных элементов. Стоимость алгоритма равна количеству выполняемых им переносов содержимого памяти.
Модель памяти без явного задания параметров кэша, предложенная Фриго и др. [18], изящно обобщает модель ввода-вывода на многоуровневую модель, обладающую следующим свойством: алгоритм не может знать значения B и M. Более точно, алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ будет действительным при любых значениях B и M. Предполагается, что замещение содержимого кэша выполняется автоматически при помощи оптимальной автономной стратегии замещения. Поскольку анализ является допустимым при любых значениях B и M, он выполняется для всех уровней одновременно.
Мы будем рассматривать эффективные структуры данных без явного задания параметров кэша для задачи упорядоченного словаря, т.е. задачи хранения элементов с ключами из упорядоченной совокупности с поддержкой поиска, вставки, удаления и поиска в нужном диапазоне. В самом общем случае поиск представляет собой поиск предшественника, возвращающий элемент с максимальным ключом, меньшим или равным искомому ключу.
Основные результаты
Первый словарь без явного задания параметров кэша предложил Прокоп [21], который показал, как расположить статическое бинарное дерево в памяти таким образом, чтобы поиск занимал O(logB n) переносов содержимого памяти. Это расположение, часто называемое расположением ван Эмде Боаса из-за того, что оно напоминает классическую структуру данных ван Эмде Боаса, также гарантирует, что поиск в диапазоне занимает O(logB n + k/ B) переносов содержимого памяти [2], где k – размер выходного значения. Обе границы являются оптимальными для поиска на основе сравнения.
Первый динамический словарь без явного задания параметров кэша был предложен Бендером и др. [10]. Используя вариант расположения ван Эмде Боаса, алгоритм управления плотностью Итая и др. [10] и сбалансированные по весам B-деревья [5], авторы пришли к следующим результатам:
Теорема 1 ([10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за O(logB n) переносов содержимого памяти, а вставку и удаление – за амортизированные O(logB n) переносов содержимого памяти.
Теорема 2 ([10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за O(logB n) переносов содержимого памяти, вставку и удаление – за амортизированные O(logB n + (log 2n)/B) переносов, а поиск в диапазоне – за O(logB n + k/B) переносов, где k – размер выходного значения.
Позднее Бендер и др. [7] разработали структуру без явного задания параметров кэша для поддержки связанных списков, обеспечивающую вставку и удаление элементов за O(1) переносов содержимого памяти, а сканирование k последовательных элементов – за амортизированные O(k/B) переносов. Объединив эту структуру со структурой из теоремы 1, можно получить следующий результат.
Теорема 3 ([7, 10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за O(logB n) переносов содержимого памяти, вставку и удаление – за амортизированные O(logB n) переносов, а поиск в диапазоне – за амортизированные O(logB n + k/B) переносов, где k – размер выходного значения.
Был предложен длинный список расширений базовой структуры словаря без явного задания параметров кэша.
Бендер и др. [11], а также Бродал и др. [16] предложили довольно близкие идеи для воспроизведения результата теоремы 2, однако использовали значительно более простые структуры вместо сбалансированных по весам B-деревьев. На базе экспоненциальных деревьев Бендер и др. [8] предложили вариант, поддерживающий запросы и обновления за O(logB n) переносов в худшем случае. Они также предложили решение с частичной устойчивостью, в котором поиск (во всех версиях структуры) и обновление (в последней версии структуры) требовали амортизированные O(logB(m + n)) переносов содержимого памяти, где m – количество версий, а n – количество элементов в версии, находящейся в данный момент в работе. Бендер и др. [14] расширили модель без явного задания параметров кэша на параллельный вариант и сформулировали три предложения по использованию B-деревьев без явного задания параметров кэша в этом варианте. Бендер и др. [12] предложили структуры словаря без явного задания параметров кэша, использующие компромисс между более быстрой операцией вставки и более медленным поиском. Франческини и Гросси [17] показали, как добиться стоимости запросов и обновлений O(logB n) в худшем случае, используя O(1) дополнительной памяти помимо той, что требуется для хранения n элементов. Были представлены расширения словаря на другие типы данных – такие как строки [13, 15] и геометрические данные [3, 4, 6].
Было показано [9], что наилучная возможная мультипликативная константа в границе поиска @(logB n) для поиска на основе сравнения различается в модели ввода-вывода и в модели без явного задания параметров кэша.