跳至主要內容

15. SQL

15. SQL

在计算机中，数据库（Database） 是一种持久化保存数据的方式，通常分为两类： SQL 数据库 和 NoSQL 数据库。SQL 是 Structured Query Language（结构化查询语言）的简称，它是关系型数据库管理系统（RDBMS）的核心组件，用于高效地查询、插入、更新和管理数据库中的数据。

RDBMS（如 MySQL、PostgreSQL、SQL Server）通过结构化的方式组织数据，主要依赖 SQL 语言来操作数据。其底层数据结构常使用 B+ Tree 进行存储。

B+ Tree

B+ Tree 是一种平衡树，用于高效地存储和检索有序数据。B+ Tree 提供快速的搜索、插入、删除操作，并能够很好地支持范围查询和顺序访问，因为其多路平衡特性和磁盘读取优化能力，它被广泛用于数据库索引。

B+ Tree 的每个节点包含键值及指向子节点的指针，叶子节点按顺序存储数据并相互链接。

B+ Tree 的结构特点

  1. 多路平衡性：

    • B+ Tree 是一种多路搜索树，每个节点可以有多个子节点。
    • 非叶子节点存储索引（key），而不存储实际数据。
    • 数据仅存储在叶子节点中。

  2. 叶子节点链表：

    • 所有的叶子节点通过双向链表相连，形成一个有序的链表结构。
    • 这使得范围查询、顺序遍历非常高效。

  3. 节点分裂和合并：

    • 当节点的存储超出容量时，会触发分裂。
    • 如果数据量减少导致节点利用率过低，会触发合并操作。
    • 这种机制保证了树的平衡，使得树的高度保持最小。

  4. 自平衡特性：

    • B+ Tree 保持平衡，即从根节点到任意叶子节点的路径长度相等。
    • 这种平衡性使得所有操作的时间复杂度为 O(log n)。

B+ Tree 的优势

  1. 快速检索：保证操作时间复杂度为 O(log n)。
  2. 顺序存取：通过链表支持高效的区间查询。
  3. 高 IO 效率：设计与磁盘读取特性匹配，减少随机读取。

B+ Tree 示例

假设我们有以下一组数字需要存储在一个 B+ Tree 中：10, 20, 30, 40, 50, 60, 70, 80

  • 每个节点最多可存储 3 个键，超出容量时需要分裂。
  • 数据存储在叶子节点中，非叶子节点只存储索引。

构建过程如下：

  1. 插入 10, 20, 30：

    • 根节点能容纳 3 个键，无需分裂。

  2. 插入 40：

    • 超出容量，节点分裂成两个：左节点存储 [10, 20]，右节点存储 [30, 40]。
    • 父节点新增索引 30。

  3. 插入 50, 60：

    • 右节点容量满，再次分裂。左叶节点 [10, 20]，中叶节点 [30, 40]，右叶节点 [50, 60]。
    • 父节点更新为 [30, 50]。

  4. 插入 70, 80：

    • 插入数据到右叶节点，最终结构完成。

最终的 B+ Tree 如下：

           [30, 50]
          /    |    \
  [10, 20]->[30, 40]->[50, 60, 70, 80]
  • 根节点为 [30, 50]：30 是左子树与中子树的分界点，50 是中子树与右子树的分界点。
  • 叶子节点存储所有数据并通过链表链接。

此时，如果要查询 35 到 75 的值，过程如下：

  1. 先寻找起点 35，从根节点找到范围属于 [30, 50] 的子树，即中子树 [30, 40]。
  2. 依次遍历链表，找到叶子节点 [30, 40] 和 [50, 60, 70, 80]。
  3. 过滤出属于 35 到 75 范围内的值，返回值：[40, 50, 60, 70]。

这种设计有效利用了磁盘页的读取特性，减少随机 IO 操作，提升性能。

SQL

使用示例

以电话本为例，数据库中的一个表可以存储如下信息：

IDNamePhone
1Alice123-456-7890
2Bob234-567-8901
3Charlie345-678-9012

查询示例

  1. 查询所有联系人：
    SELECT * FROM PhoneBook;
  2. 查询名字为 Alice 的电话：
    SELECT Phone FROM PhoneBook WHERE Name = 'Alice';
  3. 添加新联系人：
    INSERT INTO PhoneBook (Name, Phone) VALUES ('David', '456-789-0123');

两个表之间的查询示例

以一个简单的学生和课程管理系统为例，有两个表：students 和 courses。它们通过外键关系连接，展示 一对多 的关系。

表结构

  1. students 表 (学生信息表)：

    • id: 学生的唯一 ID
    • name: 学生姓名

  2. courses 表 (课程信息表)：

    • id: 课程的唯一 ID
    • student_id: 学生的 ID（外键，指向 students 表的 id 列）
    • course_name: 学生选择的课程名称

表数据示例：

students 表：

idname
1Alice
2Bob
3Charlie

courses 表：

idstudent_idcourse_name
11Math
21Science
32History
43Math
53Physics

查询示例

  1. 查询某个学生及其所选课程
    例如，查询 Alice 的课程：
SELECT students.name, courses.course_name
FROM students
JOIN courses ON students.id = courses.student_id
WHERE students.name = 'Alice';

结果：

namecourse_name
AliceMath
AliceScience
  1. 查询所有学生及其课程
SELECT students.name, courses.course_name
FROM students
JOIN courses ON students.id = courses.student_id;

结果：

namecourse_name
AliceMath
AliceScience
BobHistory
CharlieMath
CharliePhysics

通过建立两个表的关系，可以高效查询一对多的关系数据，甚至扩展到更复杂的场景，比如多对多或嵌套查询。这种设计使得关系型数据库能够灵活应对不同的数据管理需求。

SQL 的核心特性：ACID

为了确保数据库操作的可靠性，SQL 数据库遵循 ACID 属性：

1. Durability（持久性）

Durability 确保当事务完成后，数据会永久保存在存储设备上，即使系统发生崩溃。

Redis 通常不完全符合 Durability，因为它是内存数据库，某些配置下数据可能未写入磁盘。

事务的典型操作流程：

  1. 开始事务（BEGIN）。
  2. 执行操作（READ、WRITE、UPDATE、DELETE）。
  3. 提交事务（COMMIT）。

2. Atomicity（原子性）

原子性确保事务中的所有操作要么全部执行，要么完全回滚。

示例：银行转账

  • A 给 B 转账 500 元时，如果 A 转出成功但 B 账户更新时系统崩溃，A 的 500 元不会消失，而是整个事务回滚：
    转账前：A: 1000，B: 500
转账后（崩溃）：A: 1000，B: 500

3. Isolation（隔离性）

隔离性确保多个事务同时执行时，其结果与按顺序执行的结果一致。

示例：多事务并发

  • A 给 B 转 500 元，C 给 A 转 200 元。在 A 执行转账后，C 的操作不能影响事务的中间状态。

4. Consistency（一致性）

一致性确保事务前后，数据库都处于合法状态。

示例：

  • 如果数据库的规则要求账户余额总和不变，任何事务完成后都必须满足此规则。
Copyright © 2024 2xiao