数据库blog2_数据结构与效率

🌿计算机中的数据————存储结构与逻辑结构

🍂存储结构（物理结构）

定义：存储结构是指数据在计算机存储器中的实际存储方式，由计算机硬件特性决定。它涉及到数据的物理位置和存储顺序。存储结构直接影响数据的访问速度和存储效率。

• 在计算机中，数据的存储离不开地址的操作即与硬件有关。由此，相关的存储方式有限，无论现实世界的数据是什么类型的，最终在计算机里都要被转化为有限的存储结构来存储。根据现实世界数据的逻辑关系的复杂度不同，到存储结构所经历的处理难度也不同。
  • 如，线性结构可以直接与计算机的顺序存储结构映射
  • 而键值对结构就要经过复杂的映射
  • 矩阵会映射到二维上数组最终以顺序存储结构存储着

● 常见的存储结构

○ 顺序存储结构

特点：数据元素在存储器中占据连续的存储空间，通过地址计算来访问数据。
适用场景：适用于线性结构，如数组。例如，一个一维数组在内存中是连续存储的，可以通过数组名和下标快速计算出任意元素的地址。

优点：存储密度高，空间利用率高；访问速度快，尤其是随机访问。
缺点：插入和删除操作效率较低，因为需要移动大量元素。

○ 链式存储结构

特点：数据元素在存储器中的存储位置是不连续的，通过指针（或链接）将数据元素连接起来。
适用场景：适用于线性表、链表等结构。例如，单链表中每个节点包含数据部分和指向下一个节点的指针。

优点：插入和删除操作方便，不需要移动大量元素；动态分配存储空间，灵活性高。
缺点：存储密度较低，因为需要额外的空间存储指针；访问速度较慢，只能顺序访问。

○ 散列存储结构

特点：通过散列函数将数据元素映射到存储器中的某个位置，以实现快速查找。
适用场景：适用于需要快速查找的场景，如哈希表。

优点：查找速度快，平均时间复杂度接近常数时间。
缺点：可能会出现散列冲突，需要解决冲突的方法（如开放定址法、拉链法）；存储空间利用率可能较低。

○ 索引存储结构

特点：通过建立索引表来快速定位数据元素的位置。
适用场景：适用于大型数据库和文件系统。

优点：查找速度快，尤其是对于大量数据的查找。
缺点：需要额外的空间存储索引表；插入和删除操作需要更新索引表，效率可能较低。

🍂逻辑结构

定义：数据元素之间的抽象关系，与具体实现无关。现实中数据的逻辑关系多种多样，但要存储在存储器上，需要处理，转化为存储器上可以表示的物理结构。
注意：

现实的数据的逻辑结构是一种数学上的描述，而数据要实际存储，就要遵守计算上数据的存储（物理）结构。即数据从逻辑结构到物理结构的转化这一步是必须的。

• （eg.线性逻辑结构因为正好和顺序存储结构可以直接映射，所以看起来似乎没有转化。但实际上是经历了这一步的）

● 常见的逻辑结构

○ 线性结构

特点：数据元素呈线性排列，每个元素（除首尾元素外）都有一个前驱和一个后继。
典型实现：数组、链表

○ 树形结构

特点：数据元素呈层次结构，每个元素（除根节点外）都有一个父节点和多个子节点。
典型实现：二叉树、B树、红黑树

○ 图结构

特点：数据元素之间没有固定的层次关系，任意两个元素之间可能存在直接或间接的关系。
典型实现：无向图、有向图

○ 集合结构

特点：数据元素之间没有固定的顺序关系，每个元素唯一。
典型实现：集合（Set）、哈希集合（HashSet）

🍂总结

逻辑结构是数据的逻辑 描述，不涉及实现，是抽象的概念，与实际无关。而存储结构是逻辑结构在计算机中的实现，涉及到现实的硬件（存储器）。

逻辑结构与存储结构的关系

• 逻辑结构是抽象的：它描述了数据元素之间的关系，但不涉及具体的存储方式。
• 存储结构是具体的：它是逻辑结构在计算机中的实现方式，涉及到数据的实际存储位置和存储顺序。
• 转化过程是必要的：数据从逻辑结构到存储结构的转化是必须的，因为计算机硬件只能处理具体的存储结构。

图片描述

PS: 《数据结构》就是干了这样的一件事，分析数据的逻辑关系，转化为对应的存储结构实现。

🌿数据的操作

同时，无论数据采取了啥样的存储结构和逻辑结构，最终对数据的操作都离不开基本操作（增删查改）以及由这些基本操作组成的复杂操作（eg.排序、过滤、聚合、关联、分组…）

• 存储结构直接影响效率，逻辑结构间接影响效率（逻辑结构决定了数据的组织形式和操作方式，而这些因素直接影响了数据操作的复杂度和效率。）
• 不同的逻辑结构以及不同的存储结构会影响最终对数据的操作效率，最终影响数据处理整个过程的效率。
  • 线性表用顺序存储结构实现/链式存储结构实现，同一个逻辑结构不同存储结构，最终效率不同。
  • 数据采用不同的逻辑结构后即使采用相同的存储结构，也会影响效率

🍂效率的评价————时/空

● 理论

理论分析提供了算法或数据结构在理想条件下的性能预测，帮助我们在设计阶段做出合理的决策。它可以帮助我们避免选择在理论上就表现不佳的方案，从而提高系统的整体性能。

空间复杂度

• 定义： 空间复杂度衡量的是算法或数据结构在运行过程中所需的额外存储空间。
• 表示方法： 通常用大 O 记号表示，例如 O(1) 表示常数空间复杂度，O(n) 表示线性空间复杂度。

时间复杂度

• 定义： 时间复杂度衡量的是算法或数据结构在运行过程中所需的时间，通常与输入规模 n 的关系来表示。
• 表示方法： 同样用大 O 记号表示，例如 O(1) 表示常数时间复杂度，O(n) 表示线性时间复杂度，O(n²) 表示二次时间复杂度。

● 实际表现

实际表现是指在真实环境中运行算法或数据结构时的性能表现。它通过实际运行代码来评估算法或数据结构在特定条件下的运行时间和内存占用情况。实际表现是理论分析的验证手段，能够反映算法在真实场景中的性能。

测试方法：

基准测试、压力测试、比较测试、性能分析工具。

● 二者关系

理论分析： 提供了一个通用的框架，帮助我们在设计阶段预测和比较算法或数据结构的性能。它可以帮助我们避免选择性能不佳的方案，从而提高系统的整体性能。
实际表现： 是理论分析的验证手段。通过实际运行，我们可以发现理论分析中没有考虑到的问题，并进行优化和调整。
两者相辅相成： 理论分析是实际表现的基础，实际表现是理论分析的验证。在实际应用中，我们需要结合两者来做出最优的决策。

● 实际应用中的决策步骤

设计阶段：

• 使用理论分析筛选出适合的算法或数据结构。
• 评估时间复杂度和空间复杂度，初步确定候选方案。

实现阶段：

• 进行实际测试，验证候选方案的性能。
• s通过基准测试和压力测试，发现性能瓶颈。

优化阶段：

• 根据实际测试结果，调整或优化算法或数据结构。
• 重复测试，验证优化效果。

🍂基本操作的效率评价

体现了存储结构 + 逻辑结构都会影响最终的效率

● 查找（Search）

时间复杂度：

• 顺序存储结构（数组）：
• 无序数组：O(n)
• 有序数组（二分查找）：O(logn)
• 链式存储结构（链表）：O(n)
• 散列存储结构（哈希表）：平均 O(1)，最坏 O(n)
• 树形存储结构（二叉搜索树）：平均 O(logn)，最坏 O(n)
• 索引存储结构：平均 O(logn)

空间复杂度：

• 通常与存储结构本身的空间占用有关，查找操作本身的空间复杂度通常为 O(1)。

● 插入（Insert）

时间复杂度：

• 顺序存储结构（数组）：
• 在末尾插入：O(1)
• 在中间或开头插入：O(n)（需要移动元素）
• 链式存储结构（链表）：
• 在头部插入：O(1)
• 在尾部或中间插入：O(n)（需要找到插入位置）
• 散列存储结构（哈希表）：平均 O(1)，最坏 O(n)
• 树形存储结构（二叉搜索树）：平均 O(logn)，最坏 O(n)
• 索引存储结构：平均 O(logn)

空间复杂度：

• 通常为 O(1)，但可能需要额外空间来存储新节点（如链表或树）。

● 删除（Delete）

时间复杂度：

• 顺序存储结构（数组）：
• 删除末尾元素：O(1)
• 删除中间或开头元素：O(n)（需要移动元素）
• 链式存储结构（链表）：
• 删除头部元素：O(1)
• 删除尾部或中间元素：O(n)（需要找到目标节点）
• 散列存储结构（哈希表）：平均 O(1)，最坏 O(n)
• 树形存储结构（二叉搜索树）：平均 O(logn)，最坏 O(n)
• 索引存储结构：平均 O(logn)

空间复杂度：

• 通常为 O(1)，但可能需要额外空间来存储临时变量。

● 修改（Update）

时间复杂度：

• 顺序存储结构（数组）：O(1)（直接通过索引访问）
• 链式存储结构（链表）：O(n)（需要找到目标节点）
• 散列存储结构（哈希表）：平均 O(1)，最坏 O(n)
• 树形存储结构（二叉搜索树）：平均 O(logn)，最坏 O(n)
• 索引存储结构：平均 O(logn)

空间复杂度：

• 通常为 O(1)。

🌿数据库的功能

🍂功能

● 逻辑结构设计

将现实数据转换为合适的逻辑结构（如关系表）

● 存储结构实现

根据逻辑结构的特点，选择合适的存储结构（如顺序存储结构/链式存储结构等）来实现数据的物理存储。

● 性能加速结构实现

额外的对数据的处理————如，索引、视图、缓存以及其它。以提高效率

○ 数据库性能加速结构总结

本质

在逻辑层和物理存储层之间构建高效访问路径，但不改变基础数据逻辑。

核心原理

在逻辑层（表、查询）和物理层（磁盘存储）之间，构建额外的辅助结构，以空间换时间，提升访问效率。

结构	作用	示例
索引	加速单表数据定位（B+树、哈希）	CREATE INDEX idx_name ON users(name)
物化视图	缓存复杂查询结果（聚合、多表连接）	CREATE MATERIALIZED VIEW sales_summary AS SELECT ...
缓存	内存存储热点数据，减少磁盘IO	Redis缓存查询结果、InnoDB Buffer Pool
分区表	按规则拆分大表，减少扫描范围	PARTITION BY RANGE (date)
布隆过滤器	快速判断数据是否存在，避免无效IO	LSM-Tree中的SSTable查询优化
预写日志(WAL)	优化写入性能，保证崩溃恢复	PostgreSQL的WAL、MySQL的redo log

共同特点

• 透明性：用户无需手动管理，数据库自动选择使用（如优化器选索引）。
• 派生性：基于原始数据构建，不改变业务逻辑。
• 权衡性：占用额外资源（存储/内存）换取更快访问速度。

一句话总结

数据库通过索引、物化视图、缓存等“加速结构”，在逻辑和物理层之间架设“高速通道”，让查询更快、写入更稳，但需付出存储或计算成本。

🍂总结

• 即数据库是一个研究如何把存储逻辑实现在计算机上的实践型知识。它具体研究理论的落地，而不是相关概念。

🌿总结

1. 数据处理过程整体效率要高
2. 各步骤效率要高
3. 数据输入/输出效率要高
4. 计算机中数据存储与存储器有关
5. 优化存储器效率————物理优化与逻辑优化
6. 数据在计算机中————存储结构与顺序结构
7. 对数据的操作的效率受到数据存储结构与顺序结构的影响
8. 选择合适的结构提高效率
9. 数据库：为现实数据选择合适的逻辑结构和存储结构，并加以其它的逻辑优化。