World Library  
Flag as Inappropriate
Email this Article

Sequential access

Article Id: WHEBN0000027162
Reproduction Date:

Title: Sequential access  
Author: World Heritage Encyclopedia
Language: English
Subject: Random access, Sequential access memory, Linked list, Simple API for XML, Tape drive
Publisher: World Heritage Encyclopedia

Sequential access

Sequential access compared to random access.

In computer science, sequential access means that a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape. It may also be the access method of choice, for example if all that is wanted is to process a sequence of data elements in order.[1]

However, there is no consistent definition of sequential access or sequentiality.[2][3][4][5][6][7][8][9] In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, strided distance, backward accesses, re-accesses can affect sequentiality. For temporal sequentiality, characteristics such as multi-stream and inter-arrival time threshold has impact on the definition of sequentiality.[10]

In data structures, a data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the linked list. Indexing into a list that has sequential access requires O(k) time, where k is the index. As a result, many algorithms such as quicksort and binary search degenerate into bad algorithms that are even less efficient than their naïve alternatives; these algorithms are impractical without random access. On the other hand, some algorithms, typically those that do not have index, require only sequential access, such as mergesort, and face no penalty.

See also


  1. ^ Microsoft TechNet
  2. ^ Irfan Ahmad, Easy and Efficient Disk I/O Workload Characterization in VMware ESX Server, IISWC, 2007.
  3. ^ Eric Anderson, Capture, Conversion, and Analysis of an Intense NFS Workload, FAST, 2009.
  4. ^ Yanpei Chen et al. Design Implications for Enterprise Storage Systems via Multi-dimensional Trace Analysis. SOSP. 2011
  5. ^ Andrew Leung et al. Measurement and Analysis of Large-scale Network File System Workloads. USENIX ATC. 2008
  6. ^ Frank Schmuck and Roger Haskin, GPFS: A Shared-Disk File System for Large Computing Clusters, FAST. 2002
  7. ^ Alan Smith. Sequentiality and Prefetching in Database Systems. ACM TOS
  8. ^ Hyong Shim et al. Characterization of Incremental Data Changes for Efficient Data Protection. USENIX ATC. 2013.
  9. ^ Avishay Traeger et al. A Nine Year Study of File System and Storage Benchmarking. ACM TOS. 2007.
  10. ^ Cheng Li et al. Assert(!Defined(Sequential I/O)). HotStorage. 2014
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.