Последовательный доступ - Sequential access

Последовательный доступ по сравнению с произвольный доступ

Последовательный доступ это термин, описывающий группу элементов (например, данные в массиве памяти или диск файл или на хранение данных на магнитной ленте ), доступ к которому осуществляется в заранее определенном, упорядоченном последовательность. Это противоположность произвольный доступ, возможность получить доступ к произвольному элементу последовательности так же легко и эффективно, как и к любому другому, в любое время.

Последовательный доступ иногда является единственным способом доступа к данным, например, если они находятся на ленте. Это также может быть предпочтительный метод доступа, например, если все, что нужно, - это обработать последовательность элементов данных по порядку.[1]

Определение

В Информатика последовательного доступа или последовательности.[2][3][4][5][6][7][8][9] Фактически, разные определения последовательности могут привести к различным результатам количественной оценки последовательности. В пространственном измерении размер запроса, пройденное расстояние, обратные обращения, повторные обращения могут влиять на последовательность. Для временной последовательности такие характеристики, как многопоточность и пороговое время между поступлениями, влияют на определение последовательности.[10]

В структуры данных, структура данных считается имеющей последовательный доступ, если можно посещать только те значения, которые она содержит, в одном определенном порядке. Канонический пример - это связанный список. Для индексации в список с последовательным доступом требуется О (п) время, где п это индекс. В результате многие алгоритмы, такие как быстрая сортировка и бинарный поиск вырождаются в плохие алгоритмы, которые даже менее эффективны, чем их наивные альтернативы; эти алгоритмы непрактичны без произвольный доступ. С другой стороны, некоторые алгоритмы, обычно те, которые не имеют индекса, требуют только последовательного доступа, например Сортировка слиянием, и не подлежат наказанию.

Смотрите также

Рекомендации

  1. ^ Случайный и последовательный доступ к данным, Microsoft TechNet
  2. ^ Ирфан Ахмад, Простая и эффективная характеристика рабочих нагрузок дискового ввода-вывода в VMware ESX Server, IISWC, 2007.
  3. ^ Эрик Андерсон, Захват, преобразование и анализ интенсивной рабочей нагрузки NFS, БЫСТРО, 2009.
  4. ^ Янпей Чен и др. Последствия проектирования для корпоративных систем хранения данных с помощью многомерного анализа трассировки. СОСП. 2011 г.
  5. ^ Эндрю Люнг и др. Измерение и анализ крупномасштабных рабочих нагрузок сетевой файловой системы. USENIX ATC. 2008 г.
  6. ^ Фрэнк Шмук и Роджер Хаскин, GPFS: файловая система с общим диском для больших вычислительных кластеров, БЫСТРЫЙ. 2002 г.
  7. ^ Алан Смит. Последовательность и предварительная выборка в системах баз данных. ACM TOS
  8. ^ Хён Шим и др. Характеристика дополнительных изменений данных для эффективной защиты данных. USENIX ATC. 2013.
  9. ^ Avishay Traeger et al. Девятилетнее исследование сравнительного анализа файловой системы и хранилища. ACM TOS. 2007 г.
  10. ^ Cheng Li et al. Утвердить (! Определено (Последовательный ввод-вывод)). HotStorage. 2014 г.