当前位置：首页 > article >正文

浅谈数据结构

article 2025/4/2 11:47:10

概念

数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。它包含三个方面的内容：即数据的逻辑结构、数据的存储结构和数据的操作，只有这三个方面的内容完全相同，才能成为完全相同的数据结构。

解释：计算机存储、组织数据的方式

研究对象

数据逻辑结构

数据的逻辑结构是指数据元素之间存在的逻辑关系，由数据元素的集合和定义在此集合上的关系组成。数据的逻辑结构与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。数据的逻辑结构由两个要素构成，分别是：数据元素的集合和关系的集合。一般来说，逻辑结构包括：

1.集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2.线性结构：数据结构中的元素存在一对一的相互关系；

3.树形结构：数据结构中的元素存在一对多的相互关系；

4.图形结构：数据结构中的元素存在多对多的相互关系。

数据的存储结构

数据的逻辑结构在计算机中的存储表示或实现叫做数据的存储结构，也叫物理结构。数据的存储结构依赖于计算机。

一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

常见数据结构及特点

在计算机科学的发展过程中，数据结构也随之发展。程序设计中常用的数据结构包括如下几个。

数组（Array）

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。

数组是有序元素的序列，在内存中的分配是连续的的，数组会为存储的元素都分配一个下标（索引），此下标是自增连续的，访问数组中的元素通过下标进行访问，数组下标从0开始

特点：

内存地址连续（物理存储地址连续）

查询效率高（因为他有索引）

新增，删除，效率低（比如在下标为0的位置插入或者删除数据，这样后面的所有元素的下标都要修改）

堆栈（Stack）

堆栈是一种特殊的线性表，又称为栈。它只能在表的固定端进行数据结点的插入和删除操作。栈按照先进后出、后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

特点：先进后出

队列（Queue）

队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列按照先进先出的原则来存储数据。队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。

特点：先进先出

链表（Linked List）

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序通过链表中的指针链接次序实现。

特点：

查询效率低（因为没有索引，只能遍历查找）

新增，删除效率高（因为只需要修改前一个或者后一个的元素的指针位置就可以了）

树（Tree）

树是典型的非线性结构，它是由n（n>0）个有限结点组成的一个具有层次关系的集合。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点。

图（Graph）

图是另一种非线性数据结构。图的数据结构包含一个有限的集合作为结点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边的集合。如果两个结点之间存在一条边，那么就表示这两个结点具有相邻关系。

堆（Heap）

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

散列表（Hash）

散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

常用算法

数据操作是指对数据结构中的数据元素进行运算或处理。数据操作定义在数据的逻辑结构上，每种逻辑结构都需要一组对其数据元素进行处理以实现特定功能的操作，如插入、删除、更新等。数据操作的实现依赖于数据的存储结构。一般有以下几种常用运算：

（1）创建操作

（2）插入操作

（3）删除操作

（4）查找操作

（5）修改操作

（6）遍历操作

mysql的B+tree索引数据结构

MySQL的InnoDB存储引擎采用了一种"页式管理+索引组织"的混合物理存储结构，既不是纯粹的顺序存储，也不是简单的链式存储，而是一种精心设计的"B+树索引+页链表"结构。

具体存储结构

1. 基本存储单元：页（Page）

每个页大小固定为16KB（像一页纸）
页是磁盘和内存之间传输数据的最小单位
一个表的所有数据被分配到多个这样的页中

[页结构示意图]
|-----------------------|
| 文件头 (38字节)        |
|-----------------------|
| 页头 (56字节)          |
|-----------------------|
| 最小记录 (Infimum)     |
|-----------------------|
| 用户记录 (你的数据)     | ← 实际存储行记录的地方
|-----------------------|
| 最大记录 (Supremum)    |
|-----------------------|
| 空闲空间               |
|-----------------------|
| 页目录 (槽位信息)       | ← 类似书的目录，快速定位记录
|-----------------------|
| 文件尾 (8字节)         |
|-----------------------|

2. 页如何组织成表

不是连续存储：页在物理磁盘上不一定是连续的（像散落的书架）
通过双向链表连接：每个页知道自己的"前一页"和"后一页"在哪里（像书架之间用绳子连着）
通过B+树索引定位：主键索引的B+树告诉你数据在哪个页（像图书索引卡）

[表空间物理结构示意图]
表空间文件.ibd
↓
[页1] ←→ [页2] ←→ [页3] ←→ [页4] ←→ ...
 ↑        ↑         ↑         ↑
 数据     数据      数据      数据

3. 不同类型的存储方式

聚簇索引（主键索引）：
- 数据行就存储在B+树的叶子节点页中
- 物理顺序大致按照主键排序，但不完全连续
二级索引：
- 叶子节点只存储索引列+主键值
- 需要回表查询聚簇索引获取完整数据
行记录存储：
- 每行记录像"一行字"写在页的"用户记录"区域
- 记录之间可以紧凑排列，删除记录会留下"空洞"

4. 记录怎么在页内存储

不是简单的数组：记录在页内不是严格顺序存储
使用槽位（Slot）管理：页目录维护了一个"槽位数组"，类似书的目录
插入新记录：会找到合适位置插入，可能造成页内记录物理顺序与逻辑顺序不一致

[页内记录存储示例]
物理顺序: [记录A][记录C][记录B] ← 看起来乱序
逻辑顺序: 通过槽位维护为 A→B→C

物理存储的三大真相

不是完全连续存储（不像数组）
- 不同书架（页）在磁盘上可能分散存放
- 但MySQL会尽量让相邻的书架放得近一些（减少磁头移动）
也不是纯链式存储（不像链表）
- 虽然有链表连接各个页
- 但通过B+树可以直接跳转到目标区域（不需要遍历）
更像"索引卡片+分散书架"的混合体
- 先用B+树快速定位到某个书架（类似查目录卡）
- 然后在书架内查找（页内通过槽位目录快速定位）

[磁盘上的实际存储样子]
▼ 表空间文件.ibd ▼
┌─────────┐    ┌─────────┐    ┌─────────┐
│ 页 103   │───→│ 页 107   │───→│ 页 110   │  ← 叶子节点（真实数据）
└─────────┘←──└─────────┘←──└─────────┘
   ↑             ↑             ↑
   │             │             │
┌─────────┐    ┌─────────┐    ┌─────────┐
│ 页 57    │    │ 页 58    │    │ 页 60    │  ← 非叶子节点（索引目录）
└─────────┘    └─────────┘    └─────────┘
        ↖_______↙    ↖_______↙
            ↓
        ┌─────────┐
        │ 根页 33 │   ← 常驻内存的根节点
        └─────────┘