【系统设计】探索数据库的世界:轻松掌握基本原理
关系型数据库管理系统(RDBMS)在软件开发和系统设计中扮演着至关重要的角色,负责存储应用程序的大部分状态。尽管其重要性不可忽视,许多人对这些数据库的内部运作知之甚少。本文深入探讨关系型数据库中的两个关键概念:索引和事务,并通过纯文本图示帮助您更好地理解这些概念。
什么是关系型数据库管理系统(RDBMS)?
关系型数据库基于1970年E.F. Codd提出的关系数据模型。关系型数据库管理系统(RDBMS)用于维护关系型数据库。许多关系型数据库系统支持使用SQL(结构化查询语言)进行查询和维护,如MySQL和PostgreSQL。
关系型数据库架构
+----------------------------+
| 关系型数据库 |
+----------------------------+
| 表(Tables) |
| +--------+ +--------+ |
| | 表1 | | 表2 | ... |
| +--------+ +--------+ |
| |
| 每个表包含多行(Rows) |
| +---+---+---+---+---+ |
| |行1 |行2 |行3 |… | |
| +---+---+---+---+---+ |
| |
| 每行包含多列(Columns) |
| +---+---+---+---+---+ |
| |列A |列B |列C |… | |
| +---+---+---+---+---+ |
+----------------------------+
什么是索引?
索引是一种数据结构,旨在减少数据查找的时间。通过额外的存储和内存开销,以及维持索引的更新(导致写操作变慢),索引使我们能够跳过逐行检查表格的繁琐任务。
书籍索引与数据库索引对比
书籍索引 数据库索引
+---------+ +---------+
| 主题 A |-----> 页码1, 页码3, 页码5 | 值1 |-----> RowID1, RowID3
| 主题 B |-----> 页码2, 页码4 | 值2 |-----> RowID2, RowID4
| 主题 C |-----> 页码6 | 值3 |-----> RowID6
+---------+ +---------+
索引的类型
在关系型数据库中,最常见的索引类型包括 B树索引(包括B树和B+树)和 倒排索引。每种索引类型都有其特定的应用场景和优势。
B树与B+树的索引
为了高效管理和查找大量数据,关系型数据库通常使用平衡树结构,如B树和B+树。这两种树结构都属于平衡树,能够在对数时间内完成插入、删除和查找操作。
B树(B-Tree)
B树是一种多路平衡查找树,每个节点可以包含多个子节点和多个键。B树的每个节点包含键和值的对,键用于快速搜索,值指向存储的数据记录或子节点。
B树结构
+--------+
| Root |
| |
+--------+
/ | \
+--+ +--+ +--+
|A | |B | |C |
|1 | |2 | |3 |
+--+ +--+ +--+
/ \
+---+ +---+
|D | |E |
|4 | |5 |
+---+ +---+
- 特点:
- 每个节点含有多个子节点,可以减少树的高度。
- 所有叶节点在同一层,保持树的平衡。
- 中间节点存储数据,便于快速查找。
B+树(B±Tree)
B+树是B树的一种变体,具有以下不同点:
- 所有实际的数据记录都存储在叶节点,中间节点仅存储键值,不存储实际数据。
- 叶节点通过链表相连,便于范围查询和顺序访问。
- B+树的结构通常比B树更高效,因为中间节点只存储键,没有存储数据,能够存储更多的键,提高缓存命中率。
B+树结构
+--------+
| Root |
| |
+--------+
/ | \
+-----+ +-----+ +-----+
|Key1 | |Key2 | |Key3 |
+-----+ +-----+ +-----+
| | |
+--+--+ +--+--+ +--+--+
|Leaf1| |Leaf2| |Leaf3|
|Row1 | |Row2 | |Row3 |
+-----+ +-----+ +-----+
- 特点:
- 中间节点不存储实际数据,仅存储键值用于导航。
- 所有数据记录集中存储在叶节点,叶节点之间通过指针相连,支持高效的范围查询。
- 更高的缓存效率,因为中间节点更紧凑,能在内存中存储更多的键值。
B树与B+树的结构对比
B树 B+树
+--------+ +--------+
| Root | | Root |
| | | |
+--------+ +--------+
/ | \ |
+--+ +--+ +--+ +-----+ +-----+
|A | |B | |C | |Key1 | |Key2 |
|1 | |2 | |3 | +-----+ +-----+
+--+ +--+ +--+ | |
/ \ | |
+---+ +---+ +-----+ +-----+
|D | |E | |Leaf1| |Leaf2|
|4 | |5 | |Row1 | |Row2 |
+---+ +---+ +-----+ +-----+
-
B树:
- 中间节点存储键和值。
- 数据分布在内部节点和叶节点。
-
B+树:
- 中间节点仅存储键,不存储实际数据。
- 所有数据集中存储在叶节点,叶节点通过链表相连。
为什么使用B+树而不是B树?
B+树在关系型数据库中的应用比B树更为广泛,主要原因包括:
-
更高的缓存命中率:
- B+树的中间节点只存储键值,不存储数据,因此每个节点可以容纳更多的键,提高了树的扇出度(每个节点的子节点数),从而减少了树的高度。
-
支持高效的范围查询:
- 所有数据记录集中在叶节点,并且叶节点之间通过链表相连,B+树可以通过顺序遍历叶节点实现高效的范围查询,而B树需要遍历多个路径,效率较低。
-
更好的磁盘读取性能:
- 由于B+树的中间节点更紧凑,能更好地利用磁盘块(block)的读写效率,减少磁盘I/O操作次数。
-
更简化的结构:
- B+树中间节点不存储数据,只存储键,简化了树的结构和实现,提高了维护效率。
因此,B+树因为其高效的范围查询能力、更高的缓存命中率以及更好的磁盘读取性能,成为了关系型数据库中索引实现的首选数据结构。
B+树索引结构
B+树索引结构
+--------+
| Root |
| |
+--------+
|
+--------+
| Inner |
| |
+--------+
/ \
+---+ +---+
|叶1 | |叶2 |
|Row1| |Row2|
+---+ +---+
对数可扩展性
B+树的高度随着叶节点数量的增加而缓慢增长(对数级别),这使得查找操作几乎瞬时完成。即使数据量极大,B+树也能高效地管理和查找数据。
高度计算方法:
- 阶数 m:一个节点最多可以有的子节点数量。在此例中,m=5。
- 叶节点:包含实际数据的节点。
- 高度 h:从根节点到叶节点的层数。
B+树的高度 h可以通过以下公式计算:
B+树的高度 ( h ) 可以通过以下公式计算:
[ h = log_m(n) ]
其中:
- ( n ) 是叶节点的数量。
- ( m ) 是树的阶数。
B+树高度与叶节点数量关系
叶节点数量 | 树的高度
---------------------
125 | 3
625 | 4
3125 | 5
15625 | 6
78125 | 7
390625 | 8
1953125 | 9
倒排索引(Inverted Index)
除了B树和B+树索引外,倒排索引是一种常用于全文搜索引擎和某些类型的数据库(如NoSQL数据库)的索引结构。倒排索引特别适合于快速查找包含特定关键词的所有记录。
倒排索引的概念
倒排索引通过建立词汇表(每个关键词)与包含该关键词的文档或记录之间的映射关系,实现高效的文本搜索。
词语 文档列表
+---------+ +--------------------+
| 关键词1 |-----> DocID1, DocID3, DocID5
| 关键词2 |-----> DocID2, DocID4
| 关键词3 |-----> DocID6
+---------+ +--------------------+
倒排索引结构示例
倒排索引结构
+-----------+
| 关键词 |
+-----------+
| 苹果 |-----> 文档1, 文档3, 文档5
| 香蕉 |-----> 文档2, 文档4
| 橙子 |-----> 文档6
+-----------+
- 组成部分:
- 词汇表:包含所有索引的关键词。
- 文档列表:每个关键词对应的文档或记录ID列表,表示包含该关键词的所有文档。
倒排索引与B+树索引的对比
特性 | B+树索引 | 倒排索引 |
---|---|---|
用途 | 精确查找、范围查询、主键索引 | 全文搜索、包含关键词的文档、布尔查询 |
数据结构 | 多路平衡树(B+树) | 词汇表与文档列表的映射 |
存储内容 | 中间节点存储键,叶节点存储Row指针 | 关键词存储在词汇表中,关联文档列表 |
查询效率 | 快速的单值查找与范围查找 | 高效的全文搜索与复杂文本查询 |
适用场景 | 传统的结构化数据查询 | 全文搜索引擎、大规模文本数据查询 |
- B+树索引 主要用于支持精确查找和范围查询,适用于传统的结构化数据。
- 倒排索引 主要用于支持全文搜索和复杂文本查询,适用于非结构化或半结构化数据。
为什么需要索引?
当数据量较小时(例如小班级的考勤名单),管理和查询数据相对简单。然而,随着数据量的增长(例如大城市的出生登记),原本快速的操作变得缓慢。索引的存在让我们能够尽快获取所需的相关数据。
索引的重要性
无索引查找 有索引查找
全表扫描:O(n) B+树查找:O(log n)
+---+---+---+---+---+ +--------+
| 1 | 2 | 3 | ... | n | | Root |
+---+---+---+---+---+ +--------+
/ \
Intermediate Intermediate
- 无索引查找:需要扫描整个表,时间复杂度为O(n),适用于小数据量。
- 有索引查找:通过索引结构(如B+树)快速定位,时间复杂度为O(log n),适用于大数据量。
索引如何工作?
索引提高了读取性能,但牺牲了写入性能,因为需要保持索引的最新状态。通过某种逻辑方式存储数据(例如按名字排序),数据库能够快速定位到特定的数据行,而无需扫描整个表。
索引叶节点与数据行映射
B+树索引结构
+--------+
| Root |
| |
+--------+
|
+--------+
| Inner |
| |
+--------+
/ \
+---+ +---+
|叶1 | |叶2 |
|Row1| |Row2|
+---+ +---+
- 叶节点包含实际的数据引用(如RowID),指向具体的数据行。
- 中间节点用于导航,快速定位到叶节点。
倒排索引的工作原理
倒排索引结构
+-----------+
| 关键词 |
+-----------+
| 苹果 |-----> 文档1, 文档3, 文档5
| 香蕉 |-----> 文档2, 文档4
| 橙子 |-----> 文档6
+-----------+
- 查询步骤:
- 分词:将查询字符串分解为关键词。
- 查找关键词:在词汇表中找到对应的文档列表。
- 合并结果:根据查询逻辑(如AND、OR)合并文档列表,获取最终结果。
存储介质:SSD 与 HDD
SSD 与 HDD 的区别
- HDD(机械硬盘):使用机械旋转的盘片和移动的读写头来访问数据,具有较高的延迟。
- SSD(固态硬盘):使用更快的存储芯片,特别适合读取大量小文件,访问速度显著优于HDD。
SSD与HDD的结构对比
HDD结构 SSD结构
+---------+ +---------+
| 盘片 |---- 旋转数据存储 | 存储芯片 |
| 读写头 |---- 机械定位数据 | 无机械部件|
+---------+ +---------+
什么是事务?
事务是一个工作单元,必须作为一个整体执行,要么全部完成,要么全部不做。事务主要涉及ACID中的隔离性,确保数据的一致性和可靠性。
ACID 特性
ACID 特性
+-------------------+
| 原子性 (Atomicity) |
+-------------------+
| 一致性 (Consistency)|
+-------------------+
| 隔离性 (Isolation) |
+-------------------+
| 持久性 (Durability) |
+-------------------+
- 原子性(Atomicity):事务中的所有操作要么全部完成,要么全部不做。
- 一致性(Consistency):事务使数据库从一个一致状态转变到另一个一致状态,遵守所有定义的数据库规则。
- 隔离性(Isolation):事务的执行不应被其他并发事务干扰。
- 持久性(Durability):一旦事务提交,其结果将永久保存在数据库中。
事务的提交与回滚
- 提交(COMMIT):确保事务中的所有更改持久化。
- 回滚(ROLLBACK):撤销事务中的所有更改,恢复到事务开始前的状态。
事务流程
+---------+ +---------+
| BEGIN | ----> | 操作1 |
+---------+ +---------+
|
V
+---------+
| 操作2 |
+---------+
|
V
+---------+
| COMMIT | 或 | ROLLBACK |
+---------+
隔离级别与读取现象
SQL 标准的隔离级别
SQL标准定义了四种隔离级别,每种隔离级别在并发处理和性能之间平衡不同:
- 可重复读(REPEATABLE READ):确保在事务期间多次读取同一数据时,数据保持一致。
- 可序列化(SERIALIZABLE):最高级别的隔离,所有事务按顺序执行,杜绝所有并发读取现象。
- 读已提交(READ COMMITTED):每次读取都是一个新的已提交数据快照,但可能会出现幻读。
- 读未提交(READ UNCOMMITTED):允许读取未提交的数据,可能导致脏读。
隔离级别与读取现象
隔离级别 | 读取现象 |
---|---|
READ UNCOMMITTED | 脏读 |
READ COMMITTED | 不可重复读,幻读 |
REPEATABLE READ | 幻读 |
SERIALIZABLE | 无读取现象 |
读取现象
-
不可重复读(Non-repeatable Reads):在同一事务中多次读取同一数据,第二次读取时数据被其他事务修改。
事务A读取数据X 事务B修改数据X并提交 事务A再次读取数据X
-
脏读(Dirty Reads):读取到其他事务未提交的数据修改。
事务A修改数据Y但未提交 事务B读取数据Y(未提交)
-
幻读(Phantom Reads):在同一事务中多次执行相同的查询,但结果集的行数发生变化。
事务A查询满足条件的记录数 事务B插入或删除满足条件的记录 事务A再次查询满足条件的记录数
读取现象的示例
不可重复读示例
事务A: BEGIN
事务A: SELECT balance FROM accounts WHERE user_id = 1
事务B: BEGIN
事务B: UPDATE accounts SET balance = 1000 WHERE user_id = 1
事务B: COMMIT
事务A: SELECT balance FROM accounts WHERE user_id = 1 -- 结果不同
脏读示例
事务A: BEGIN
事务A: UPDATE accounts SET balance = 500 WHERE user_id = 2
事务B: BEGIN
事务B: SELECT balance FROM accounts WHERE user_id = 2 -- 读取未提交的500
事务A: ROLLBACK
事务B: COMMIT
幻读示例
事务A: BEGIN
事务A: SELECT COUNT(*) FROM orders WHERE user_id = 3
事务B: BEGIN
事务B: INSERT INTO orders (user_id, amount) VALUES (3, 150)
事务B: COMMIT
事务A: SELECT COUNT(*) FROM orders WHERE user_id = 3 -- 结果增加
总结
通过深入理解索引和事务这两个关系型数据库的核心概念,开发人员和数据库管理员可以更有效地设计和优化数据库系统。索引不仅提升了数据检索的效率,还能显著改善系统的整体性能,而事务则确保了数据操作的可靠性和一致性。掌握这些知识,能够在实际工作中更好地应对数据管理和系统优化的挑战,构建高效、稳定、可靠的数据库应用。