顺序存储、链式存储、索引存储及其特点
一、顺序存储结构
1、基本原理
- 顺序存储结构是将文件中的记录按照其逻辑顺序依次存放在连续的存储介质上，在磁盘上，文件的记录一个接一个地存储，它们在物理地址上是相邻的，这种存储方式类似于数组的存储方式，文件中的第一个记录存放在存储介质的起始位置，后续记录依次存放。
图片来源于网络，如有侵权联系删除
2、优点
高效的顺序访问：当需要按照文件记录的顺序依次读取或处理文件内容时，顺序存储结构非常高效，因为记录在物理上是连续存储的，磁头不需要频繁地进行大幅度的移动，对于一个按时间顺序记录销售数据的文件，当需要分析整个时间段内的销售趋势时，顺序读取文件中的记录可以快速获取数据。
空间利用率较高：由于记录是紧凑存储的，没有额外的指针等空间开销（除了可能用于文件管理的少量元数据空间），所以在存储大量数据时，顺序存储结构能够有效地利用存储空间。
3、缺点
插入和删除操作复杂：如果要在顺序存储的文件中间插入一个新的记录，就需要将插入位置之后的所有记录依次向后移动，为新记录腾出空间，同样，删除一个记录时，需要将其后的记录向前移动来填补空缺，这种移动操作在文件较大时会非常耗时，尤其是在磁盘等外部存储设备上，因为涉及到大量的数据读写操作。
文件大小扩展不便：如果文件在创建时分配的存储空间不够，需要扩展文件大小时，可能需要重新分配更大的连续存储空间，并将原有的数据复制到新的存储空间，这是一个较为复杂和耗时的过程。
二、链式存储结构
1、基本原理
- 链式存储结构通过指针将文件中的各个记录链接在一起，每个记录除了包含自身的数据部分外，还包含一个指向下一个记录的指针（在单链表情况下），这些记录可以分散地存放在存储介质的不同位置，而指针则指示了记录之间的逻辑顺序。
图片来源于网络，如有侵权联系删除
2、优点
灵活的插入和删除操作：在链式存储结构中，插入和删除记录相对简单，要插入一个新记录，只需要修改相关记录的指针即可，要在链表中的某个位置插入一个新的节点，只需将前一个节点的指针指向新节点，新节点的指针再指向原来前一个节点指向的节点，删除操作也类似，只需修改指针来跳过要删除的节点。
不需要连续的存储空间：记录可以存放在存储介质的任意可用位置，不需要预先分配连续的大块存储空间，这对于动态增长和收缩的文件非常有利，因为它可以充分利用存储介质上的零散空间。
3、缺点
随机访问效率低：由于要访问文件中的某个特定记录，需要从链表的头开始，顺着指针依次查找，所以随机访问效率很低，如果要访问链表中的第n个记录，平均需要遍历n/2个节点，这在文件较大时会导致较长的访问时间。
空间开销较大：每个记录都需要额外的空间来存储指针，这增加了存储空间的开销，对于大型文件，指针所占用的空间可能会相当可观。
三、索引存储结构
1、基本原理
- 索引存储结构是在文件之外建立一个索引表，索引表中的每个条目包含一个关键字（通常是能够唯一标识文件记录的某个属性值）和对应的记录的存储地址，通过查找索引表，可以快速定位到文件中的特定记录。
图片来源于网络，如有侵权联系删除
2、优点
快速的随机访问：由于索引表提供了关键字到记录存储地址的映射，所以当需要根据关键字查找特定记录时，可以直接在索引表中查找关键字，然后根据对应的地址访问记录，在一个员工信息文件中，如果以员工的工号作为关键字建立索引，当需要查找某个员工的信息时，只需在索引表中查找工号对应的地址，然后直接获取员工信息，大大提高了随机访问的速度。
支持多种查询方式：除了根据关键字进行精确查找外，索引还可以支持范围查询等操作，在一个按照日期建立索引的销售记录文件中，可以方便地查询某个时间段内的销售记录。
3、缺点
索引维护成本高：当文件中的记录发生插入、删除或修改操作时，不仅要更新文件中的记录本身，还需要更新索引表，插入一个新记录时，可能需要在索引表中插入一个新的索引条目；删除记录时，要删除对应的索引条目，这种索引维护操作会增加系统的开销。
空间开销较大：索引表本身需要占用一定的存储空间，尤其是对于大型文件，索引表可能会变得很大，这增加了存储成本。
评论列表