1294
правки
B-деревья без явного задания параметров кэша: различия между версиями
Перейти к навигации
Перейти к поиску
B-деревья без явного задания параметров кэша (посмотреть исходный код)
Версия от 11:54, 23 ноября 2024
, 23 ноябрьнет описания правки
Irina (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''B-деревья без явного задания параметров кэша —''' ''Cache-oblivious B-trees'' | |||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Деревья поиска без явного задания параметров кэша; | [[Деревья поиска без явного задания параметров кэша]]; [[словари без явного задания параметров кэша]] | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 12: | Строка 14: | ||
== Основные результаты == | == Основные результаты == | ||
Первый словарь без явного задания параметров кэша предложил Прокоп [21], который показал, как расположить статическое бинарное дерево в памяти таким образом, чтобы поиск занимал <math>O(log_B \; n)</math> переносов содержимого памяти. Это расположение, часто называемое ''расположением ван Эмде Боаса'' из-за того, что оно напоминает классическую структуру данных ван Эмде Боаса, также гарантирует, что поиск в диапазоне занимает <math>O(log_B \; n + k/B)</math> переносов содержимого памяти [2], где k – размер выходного значения. Обе границы являются оптимальными для поиска на основе сравнения. | Первый словарь без явного задания параметров кэша предложил Прокоп [21], который показал, как расположить статическое бинарное дерево в памяти таким образом, чтобы поиск занимал <math>O(log_B \; n)</math> переносов содержимого памяти. Это расположение, часто называемое '''расположением ван Эмде Боаса''' (''Van Emde Boas layout'') из-за того, что оно напоминает классическую структуру данных дерево ван Эмде Боаса (''Van Emde Boas tree, vEB tree''), также гарантирует, что поиск в диапазоне занимает <math>O(log_B \; n + k/B)</math> переносов содержимого памяти [2], где k – размер выходного значения. Обе границы являются оптимальными для поиска на основе сравнения. | ||
| Строка 48: | Строка 50: | ||
== См. также == | == См. также == | ||
* [[B-деревья]] | * [[B-дерево (дерево многоканального поиска)|B-деревья]] | ||
* [[Модель без явного задания параметров кэша]] | * [[Модель без явного задания параметров кэша]] | ||
* [[Сортировка без явного задания параметров кэша]] | * [[Сортировка без явного задания параметров кэша]] | ||