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