索引与DBMS的崛起

Source: Dev.to

Hello, I’m Maneshwar. 我正在在线开发 FreeDevTools，目前正在构建 一个汇集所有开发工具、作弊代码和 TLDR 的平台——一个免费、开源的中心，开发者可以快速找到并使用工具，无需在互联网上四处搜索的麻烦。

回顾

在上一篇文章中，我们看到关系模型如何为数据提供结构：

• 实体 变为关系。
• 关系 变为表。
• 完整性约束 定义了 有效 数据库状态的样子。

但仅有结构还不够。当数据规模超出微不足道的大小时，如何访问关系与 它们 表示的内容同样重要。这正是 索引 和 数据库管理系统 (DBMS) 发挥作用的地方。

为什么需要索引

全关系扫描（读取表中的每一行）是回答查询的最基本方式，也是数据库可以执行的最昂贵的操作之一。

根据我们已经了解的磁盘特性：

• 读取数据是按块进行的。
• 磁盘 I/O 主导了执行时间。
• 对大关系的顺序扫描代价高昂。

因此，数据库需要一种更快的定位行的方式。

什么是索引？

索引是一种构建在关系之上的数据结构，用于基于一个或多个属性的值高效查找行。索引不存储数据本身；它存储：

• 搜索键值
• 指向基关系中行的指针或引用
• 引导查找沿最有效路径的路由信息

索引不是关系模型本身的一部分，但在实际系统中是不可或缺的。

索引和关系

关系数据库中索引的重要属性：

每当行被 插入、删除 或 更新 时，DBMS 都会在后台自动更新所有受影响的索引。

哈希索引和树索引

两类索引结构在关系型系统中占主导地位。

哈希索引

哈希索引 旨在实现快速的 点查找。其工作方式如下：

1. 对搜索键值应用哈希函数。
2. 将该值映射到一个桶。
3. 只在该桶内部进行搜索。

哈希索引对 精确匹配 查询极其快速，但它有一个主要局限：

• 它 不 能高效支持范围查询。
  要查询介于两个边界之间的值需要扫描许多甚至全部桶，从而失去索引的意义。

B‑树和 B⁺‑树 索引

B‑树索引 将搜索键值按 排序顺序 存储，从而实现：

• 高效的点查找。
• 高效的范围查询。
• 有序遍历，无需扫描整个关系。

B‑树的每个节点包含：

• 搜索键值。
• 指向子节点的指针。

在每个节点通过比较搜索键来决定遍历方向。

一种广泛使用的变体是 B⁺‑树：

• 内部节点 仅包含路由信息。
• 叶子节点 包含实际的数据引用（通常相互链接，以支持快速的范围扫描）。

B⁺‑树特别适合磁盘存储，因为它们能最小化随机 I/O 并保持树的高度较小。

此时我们已经初步看到逻辑查询是如何映射到物理磁盘访问模式的。

为什么应用程序不应直接管理数据

历史上，应用程序直接操作数据库文件：

• 从文件读取字节。
• 修改内存中的结构。
• 将数据写回磁盘。

这种 file‑processing approach 很快会因若干根本性问题而失效：

• 与文件格式耦合紧密。
• 难以强制完整性约束。
• 部分写入和崩溃会导致数据损坏。
• 并发访问风险大。
• 失败后的恢复极其复杂。

随着数据库规模的扩大以及多个用户的并发访问，在应用层面几乎不可能保证正确性。即使是编写良好的应用程序，也可能在并发或故障情况下产生不一致的状态。

进入数据库管理系统

解决方案是在应用程序和存储之间插入一个专用软件层：数据库管理系统（DBMS）。

DBMS 提供：

• 更高级别的数据抽象（关系而非文件）。
• 明确定义的查询和更新数据的 API。
• 自动索引维护。
• 完整性约束的强制执行。
• 并发控制。
• 故障恢复。

从应用程序的角度

• 数据表现为表格。
• 操作是声明式的。
• 存储细节被隐藏。

从系统的角度

• 查询被翻译为高效的执行计划。
• 在有益时使用索引。
• 磁盘 I/O 被精心管理。
• 故障被透明地处理。

DBMS 充当一个黑盒，弥合以下之间的差距：

• 概念数据模型。
• 物理存储现实。

我们现在的位置

在此阶段，各层次清晰可见：

• Disks 定义物理约束。
• Relations 定义逻辑结构。
• Indexes 定义访问路径。
• DBMS 协调一切。

什么仍未解决是最难的问题

当许多用户并发修改数据且操作中途出现故障时会怎样？

这个问题直接引出 事务、ACID 属性、事务管理 和 并发控制。

这就是接下来旅程的方向，也是数据库不再是简单的数据存储而成为严肃系统的起点。

👉 查看: FreeDevTools

欢迎任何反馈或贡献！
它已上线、开源，任何人都可以使用。

⭐ 在 GitHub 上给它加星: FreeDevTools