目录

顺序和随机

顺序存取和随机存取

顺序存取就是存取第N个数据时,必须先访问前(N-1)个数据 (list),随机存取就是存取第N个数据时,不需要访问前(N-1)个数据,直接就可以对第N个数据操作 (array)。

随机存取就是直接存取,可以通过下标直接访问的那种数据结构,与存储位置无关,例如数组。非随机存取就是顺序存取了,不能通过下标访问了,只能按照存储顺序存取,与存储位置有关,例如链表。

顺序存储结构和随机存储结构

顺序存储结构

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

顺序存储结构是存储结构类型中的一种,该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构,通常顺序存储结构是借助于计算机程序设计语言(例如c/c++)的数组来描述的。

顺序存储结构的主要优点是节省存储空间,因为分配给数据的存储单元全用存放结点的数据(不考虑c/c++语言中数组需指定大小的情况),结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时,可实现对结点的随机存取,即每一个结点对应一个序号,由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改,对结点的插入、删除运算时,可能要移动一系列的结点。

随机存储结构

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

它不要求逻辑上相邻的元素在物理位置上也相邻。因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

链式存储结构特点

  • 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话链式比顺序存储更少)
  • 逻辑上相邻的节点物理上不必相邻。
  • 插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
  • 查找结点时链式存储要比顺序存储慢。
  • 每个结点是由数据域和指针域组成。

顺序IO和随机IO

https://gitee.com/lienhui68/picStore/raw/master/null/20201001173244.png

顺序IO是指读写操作的访问地址连续。在顺序IO访问中,HDD所需的磁道搜索时间显着减少,因为读/写磁头可以以最小的移动访问下一个块。数据备份和日志记录等业务是顺序IO业务。 随机IO是指读写操作时间连续,但访问地址不连续,随机分布在磁盘的地址空间中。产生随机IO的业务有OLTP服务,SQL,即时消息服务等。

Mysql 数据最终都会刷到磁盘上去,刷盘分随机IO和顺序IO,两者性能相差很大,大多情况下我们会改变一下设计使Mysql 的随机IO变为顺序IO来提高性能

给随机IO添加缓存有更大的收益:

  1. 顺序I/O一般只需扫描一次数据、所以、缓存对它用处不大(收益小,不是说没用)
  2. 顺序I/O比随机I/O快
  3. 随机I/O通常只要查找特定的行、但I/O的粒度是页级的、其中大部分是浪费的、而顺序I/O所读取的数据、通常发生在想要的数据块上的所有行。

顺序存储设备和随机存储设备

这两者属于硬件层面的说法,比如一般的内存设备和机械硬盘都属于顺序存储设备,固态硬盘属于随机存储设备。

扩展

什么是IOPS

IOPS(Input/OutputOperations Per Second)是一个用于计算机存储设备(如硬盘(HDD)、固态硬盘(SSD)或存储区域网络(SAN))性能测试的量测方式,可以视为是每秒的读写次数。

机械硬盘和固态硬盘在随机IO上性能的影响因素

对于机械硬盘或是其他类似的机电存储设备,其随机存取IOPS主要和存储设备的寻址时间有关,若是固态硬盘及其他固态电子设备,其随机存取IOPS主要和存储设备的内部控制器及记亿体接口速度有关。这两种设备的顺序访问IOPS(尤其是访问大数据区块)一般与包括存储设备可以持续的最大带宽有关。

SSD作为随机存储设备,其访问任意一块的时间应该是相等的,为什么顺序IO还是快于随机IO

有多种原因导致了这种情况,一是SSD通常是主控芯片包含若干个通道,每个通道和若干闪存芯片相连,随机IO并不能像顺序IO那样,由多块芯片分担且并行传输以获得更高的性能,二是SSD有擦写/垃圾回收等机制,随机IO明显会提高这些机制的难度和频率,三是预读和缓存等机制对顺序IO会有更好的效果。 不过现在的SSD在多线程下的随机IO吞吐量已经很接近顺序IO了,但还是有一定的差距。

总结

  • 顺序存储结构(数组)和随机存储结构(链表)是作为数据存储结构的两种形式,与存储介质无关
  • 顺序存取(访问)和随机存取(访问)更强调的是一种存储结构提供的能力,顺序存储结构可以对外提供随机访问的能力;随机存储结构只能提供顺序存取的能力。
  • 顺序IO和随机IO是指读写操作访问的地址是否连续,与存储结构无关,表示应用程序两种主观的IO形式,比如mysql刷盘分为随机刷盘和顺序刷盘。
  • 顺序存储设备和随机存储设备是两种存储介质的形式,是物理层面的表述,像一般的内存设备,机械硬盘属于顺序存储设备,固态硬盘属于随机存储设备。