本文目录导读：
数据的物理结构种类全解析
顺序存储结构
1、基本概念
图片来源于网络，如有侵权联系删除
- 顺序存储结构是将数据元素按照逻辑顺序依次存放在一组地址连续的存储单元里，在这种结构中，数据元素之间的逻辑关系通过它们的存储位置来体现，对于一个线性表采用顺序存储结构时，如果线性表中的第一个元素存储在地址为 \(LOC(A_1)\) 的存储单元中，每个元素占用 \(l\) 个存储单元，那么第 \(i\) 个元素 \(A_i\) 的存储地址为 \(LOC(A_i)=LOC(A_1)+(i - 1)*l\)。
2、优点
随机访问效率高：由于元素的存储地址是连续的，并且可以通过简单的计算得到任意元素的地址，所以可以在 \(O(1)\) 的时间复杂度内访问表中的任意元素，在一个存储学生成绩的顺序表中，如果想要查询第 \(n\) 个学生的成绩，不需要遍历前面的 \(n - 1\) 个学生成绩，直接通过计算地址就能获取。
节省存储空间：不需要额外的空间来存储元素之间的逻辑关系，只需要存储数据元素本身即可，对于一些数据量较小且对存储空间要求较为严格的应用场景，顺序存储结构是比较合适的选择。
3、缺点
插入和删除操作效率低：当需要在顺序表中间插入或删除一个元素时，需要移动大量的后续元素，在一个长度为 \(n\) 的顺序表中，如果要在第 \(i\) 个位置插入一个元素，需要将第 \(i\) 个位置及其后面的 \(n - i+ 1\) 个元素依次向后移动一位，时间复杂度为 \(O(n)\)，同样，删除操作也需要类似的元素移动，这在数据频繁变动的情况下会导致性能下降。
预先分配空间的局限性：在创建顺序存储结构时，需要预先估计数据元素的最大数量并分配相应的存储空间，如果估计不准确，可能会导致存储空间的浪费或者存储空间不足的情况，创建一个顺序表来存储公司员工的信息，如果预先分配的空间过小，当员工数量增加时就需要重新分配更大的空间并进行数据迁移；而如果预先分配的空间过大，会造成内存资源的闲置。
链式存储结构
1、基本概念
- 链式存储结构是通过指针将数据元素链接起来存储的一种物理结构，每个数据元素由两部分组成：数据域和指针域，数据域用来存储数据元素的值，指针域用来存储下一个（或上一个）数据元素的地址，在单链表中，每个节点包含一个数据元素和一个指向下一个节点的指针。
2、优点
插入和删除操作灵活：在链式存储结构中，插入和删除一个元素只需要修改相关节点的指针，不需要移动大量的数据元素，在一个单链表中，如果要在节点 \(p\) 之后插入一个新节点 \(q\)，只需要将 \(q\) 的指针指向 \(p\) 的下一个节点，然后将 \(p\) 的指针指向 \(q\) 即可，时间复杂度为 \(O(1)\)（不考虑查找操作），同样，删除节点 \(p\) 的下一个节点 \(q\)，只需要将 \(p\) 的指针指向 \(q\) 的下一个节点即可。
图片来源于网络，如有侵权联系删除
动态分配空间：不需要预先分配固定大小的存储空间，可以根据实际需要动态地申请和释放内存空间，这对于数据量不确定或者数据增长较为缓慢的情况非常有利，能够有效地利用内存资源。
3、缺点
随机访问效率低：由于链式存储结构中的元素是通过指针链接的，要访问某个元素，需要从链表的头节点开始逐个遍历，直到找到目标元素，在最坏的情况下，需要遍历整个链表，时间复杂度为 \(O(n)\)，\(n\) 是链表的长度。
额外的存储空间开销：由于每个节点都需要额外的指针域来存储下一个（或上一个）节点的地址，相比于顺序存储结构，链式存储结构需要更多的存储空间，特别是当数据元素较小而指针域占用的空间相对较大时，这种存储空间的浪费会更加明显。
索引存储结构
1、基本概念
- 索引存储结构是在存储数据元素的同时，还建立了一个索引表，索引表中的每个索引项包含一个关键字和一个指向对应数据元素的指针，通过查找索引表，可以快速定位到数据元素的存储位置，在数据库系统中，对于一个包含大量记录的表，可以建立索引来提高查询效率。
2、优点
查询效率高：当需要查找某个数据元素时，可以先在索引表中进行查找，由于索引表通常是按照关键字有序排列的，所以可以采用二分查找等高效的查找算法，时间复杂度可以降低到 \(O(logn)\)，然后根据索引项中的指针直接定位到数据元素，大大提高了查询速度。
支持多种查询方式：可以根据不同的关键字建立多个索引表，以满足不同的查询需求，在一个学生信息管理系统中，可以建立按照学号索引的索引表，也可以建立按照姓名索引的索引表，方便按照不同的条件进行查询。
3、缺点
增加存储空间开销：除了存储数据元素本身，还需要额外存储索引表，索引表占用一定的存储空间，特别是当数据量非常大时，索引表的规模也会很大，可能会消耗大量的内存或磁盘空间。
图片来源于网络，如有侵权联系删除
数据更新维护成本高：当数据元素发生插入、删除或修改操作时，不仅要更新数据元素本身，还需要同时更新索引表，在插入一个新的学生记录时，需要在数据表中插入记录，同时在索引表中插入相应的索引项，这增加了数据操作的复杂性和时间成本。
散列存储结构
1、基本概念
- 散列存储结构是通过一个散列函数将数据元素的关键字映射到一个特定的存储地址，散列函数 \(h(key)\) 根据关键字 \(key\) 计算出数据元素在存储结构中的存储位置，对于一个存储员工工号和工资信息的散列表，可以根据员工工号通过散列函数计算出存储该员工工资信息的地址。
2、优点
查找速度快：理想情况下，通过散列函数可以直接计算出数据元素的存储位置，查找时间复杂度可以达到 \(O(1)\)，在一个散列表中存储了大量的用户名和密码信息，当用户登录时，通过对用户名进行散列计算，可以快速定位到对应的密码存储位置进行验证。
不需要排序：与索引存储结构不同，散列存储结构不需要对数据元素进行排序，数据元素可以按照任意顺序插入到散列表中，这在一些对数据顺序没有要求且注重查找速度的应用场景中非常有用。
3、缺点
散列冲突问题：由于散列函数的映射可能会将不同的关键字映射到相同的存储位置，这就产生了散列冲突，解决散列冲突需要采用额外的方法，如开放定址法、链地址法等，这些方法会增加一定的时间和空间开销，在开放定址法中，如果发生散列冲突，需要按照一定的探测序列寻找下一个可用的存储位置，这会增加查找时间。
散列函数的依赖性：散列存储结构的性能很大程度上依赖于散列函数的质量，如果散列函数设计不合理，可能会导致散列冲突频繁发生，从而降低散列表的性能，当数据元素的分布发生变化时，可能需要重新设计散列函数。
评论列表