Editing Sequential access (section)

==Definition==
There is no consistent definition in [[computer science]] of sequential access or sequentiality.<ref>''Irfan Ahmad'', [http://www.vmware.com/files/pdf/iiswc_2007_distribute.pdf Easy and Efficient Disk I/O Workload Characterization in VMware ESX Server], IISWC, 2007.</ref><ref>''Eric Anderson'', [https://www.usenix.org/legacy/event/fast09/tech/full_papers/anderson/anderson.pdf Capture, Conversion, and Analysis of an Intense NFS Workload], FAST, 2009.</ref><ref>''Yanpei Chen et al.'' [http://dl.acm.org/citation.cfm?id=2043562 Design Implications for Enterprise Storage Systems via Multi-dimensional Trace Analysis]. SOSP. 2011</ref><ref>''Andrew Leung et al.'' [http://www.ssrc.ucsc.edu/Papers/leung-usenix08.pdf Measurement and Analysis of Large-scale Network File System Workloads]. USENIX ATC. 2008</ref><ref>''Frank Schmuck and Roger Haskin'', [https://www.usenix.org/legacy/events/fast02/full_papers/schmuck/schmuck.pdf GPFS: A Shared-Disk File System for Large Computing Clusters], FAST. 2002</ref><ref>''Alan Smith''. [http://www-inst.eecs.berkeley.edu/~cs266/sp10/readings/smith78.pdf Sequentiality and Prefetching in Database Systems]. ACM TOS</ref><ref>''Hyong Shim et al.'' [http://0b4af6cdc2f0c5998459-c0245c5c937c5dedcca3f1764ecc9b2f.r43.cf2.rackcdn.com/11747-atc13-shim.pdf Characterization of Incremental Data Changes for Efficient Data Protection]. USENIX ATC. 2013.</ref><ref>''Avishay Traeger et al.'' [http://www.fsl.cs.sunysb.edu/docs/fsbench/fsbench.pdf A Nine Year Study of File System and Storage Benchmarking]. ACM TOS. 2007.</ref>{{Synthesis inline|date=June 2024}} In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, stride 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.<ref>''Cheng Li et al.'' [https://www.usenix.org/node/183622 Assert(!Defined(Sequential I/O))]. HotStorage. 2014</ref>

In [[data structure]]s, a data structure is said to have sequential access if one can only visit the values it contains in one particular order.{{Citation needed|date=October 2023}} The canonical example is the [[linked list]]. Indexing into a list that has sequential access requires [[Big O notation|O]](''n'') time, where ''n'' is the index. As a result, many algorithms such as [[quicksort]] and [[Binary search algorithm|binary search]] degenerate into bad algorithms that are even less efficient than their naive 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.