1294
правки
B-деревья без явного задания параметров кэша: различия между версиями
Материал из WEGA
B-деревья без явного задания параметров кэша (посмотреть исходный код)
Версия от 04:57, 23 ноября 2024
, 23 ноября 2024→Литература
Irina (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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-деревья]] | ||
* [[Модель без явного задания параметров кэша]] | * [[Модель без явного задания параметров кэша]] | ||
* [[Сортировка без явного задания параметров кэша]] | * [[Сортировка без явного задания параметров кэша]] | ||
| Строка 97: | Строка 99: | ||
22. Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol. 2141, pp. 67-78. Springer, Berlin (2001) | 22. Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol. 2141, pp. 67-78. Springer, Berlin (2001) | ||
[[Категория: Совместное определение связанных терминов]] | |||
