B-деревья без явного задания параметров кэша: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Деревья поиска без явного задания параметров кэша; словарь…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Память в компьютерах устроена иерархическим образом, причем время доступа к каждому уровню значительно различается. Таким образом, скорость доступа зависит исключительно от того, на каком самом внутреннем уровне находятся данные, к которым осуществляется доступ. При анализе работы алгоритмов стандартная RAM-модель (или модель фон Неймана) не способна воспроизвести этот эффект; поэтому для более точного моделирования ситуации были введены модели с внешней памятью. Чаще всего в качестве такой модели используется модель ввода-вывода [1], также называемая моделью внешней памяти или моделью обращений к диску. Модель ввода-вывода аппроксимирует иерархию памяти при помощи моделирования двух уровней, из которых внутренний уровень имеет размер M, внешний имеет неограниченный размер, а перенос данных между уровнями осуществляется блоками по B последовательных элементов. Стоимость алгоритма равна количеству выполняемых им переносов содержимого памяти. | |||
Модель памяти без явного задания параметров кэша, предложенная Фриго и др. [18], изящно обобщает модель ввода-вывода на многоуровневую модель, обладающую следующим свойством: алгоритм не может знать значения B и M. Более точно, алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ будет действительным при любых значениях B и M. Предполагается, что замещение содержимого кэша выполняется автоматически при помощи оптимальной автономной стратегии замещения. Поскольку анализ является допустимым при любых значениях B и M, он выполняется для всех уровней одновременно. | |||
Мы будем рассматривать эффективные структуры данных без явного задания параметров кэша для задачи упорядоченного словаря, т.е. задачи хранения элементов с ключами из упорядоченной совокупности с поддержкой поиска, вставки, удаления и поиска в нужном диапазоне. В самом общем случае поиск представляет собой поиск предшественника, возвращающий элемент с максимальным ключом, меньшим или равным искомому ключу. | |||
== Основные результаты == | |||
Версия от 00:35, 3 февраля 2017
Ключевые слова и синонимы
Деревья поиска без явного задания параметров кэша; словарь без явного задания параметров кэша
Постановка задачи
Память в компьютерах устроена иерархическим образом, причем время доступа к каждому уровню значительно различается. Таким образом, скорость доступа зависит исключительно от того, на каком самом внутреннем уровне находятся данные, к которым осуществляется доступ. При анализе работы алгоритмов стандартная RAM-модель (или модель фон Неймана) не способна воспроизвести этот эффект; поэтому для более точного моделирования ситуации были введены модели с внешней памятью. Чаще всего в качестве такой модели используется модель ввода-вывода [1], также называемая моделью внешней памяти или моделью обращений к диску. Модель ввода-вывода аппроксимирует иерархию памяти при помощи моделирования двух уровней, из которых внутренний уровень имеет размер M, внешний имеет неограниченный размер, а перенос данных между уровнями осуществляется блоками по B последовательных элементов. Стоимость алгоритма равна количеству выполняемых им переносов содержимого памяти.
Модель памяти без явного задания параметров кэша, предложенная Фриго и др. [18], изящно обобщает модель ввода-вывода на многоуровневую модель, обладающую следующим свойством: алгоритм не может знать значения B и M. Более точно, алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ будет действительным при любых значениях B и M. Предполагается, что замещение содержимого кэша выполняется автоматически при помощи оптимальной автономной стратегии замещения. Поскольку анализ является допустимым при любых значениях B и M, он выполняется для всех уровней одновременно.
Мы будем рассматривать эффективные структуры данных без явного задания параметров кэша для задачи упорядоченного словаря, т.е. задачи хранения элементов с ключами из упорядоченной совокупности с поддержкой поиска, вставки, удаления и поиска в нужном диапазоне. В самом общем случае поиск представляет собой поиск предшественника, возвращающий элемент с максимальным ключом, меньшим или равным искомому ключу.