读改变未来的九大算法笔记02_数据库.png

1. 基础思想

1.1. 预写日志记录

1.2. 两阶段提交

1.3. 关系数据库

2. 两个事实

2.1. 计算机程序会崩溃

2.1.1. 当一个程序崩溃时，它会丢掉所有正在处理的东西

2.1.2. 只有安放在计算机文件系统中的信息会得到保存

2.1.3. 崩溃相当宽泛：包括任何可能导致计算机停止运行进而损失数据的事

2.1.3.1. 可能的事件包括断电、硬盘出错、其他硬件出错，以及操作系统或应用程序中的漏洞

2.1.4. 即便这些泛指的崩溃极少发生，一些数据库也不能承受崩溃的风险

2.1.4.1. 银行、保险公司和其他数据代表实际金钱的组织，这些组织不能承受任何情况下记录中出现不一致性的风险

2.2. 硬盘和闪存条等计算机存储设备一次只能写入少量数据

2.2.1. 基本上在500个字符左右

2.2.2. 现代设备每秒能执行成千上万次这种500个字符的写入操作

2.2.2.1. 现实是磁盘内容每次只能改变数百个字符

2.2.3. 通常来说，对任何一个大小合理的数据库而言，更改两行的确需要两次单独的磁盘操作

3. 交易处理中的两个主要问题

3.1. 高效性

3.2. 可靠性

4. 一致性

4.1. Consistency

4.2. 数据库中的信息并不自相矛盾

4.3. 存在不一致性非常有害且不能为自动化工具纠正的情况

4.3.1. 银行转账

5. 预写日志记录

5.1. “待办事项表把戏”

5.1.1. To-do List Trick

5.2. 基本思想

5.2.1. 维护一个数据库计划采取的动作日志

5.2.1.1. 日志被存储在硬盘或其他一些永久性存储介质中

5.2.1.1.1. 日志中的信息就能幸免于崩溃和重启

5.2.1.2. 在一项事务的任何动作得到执行前，它们都被记录在日志中，然后再被保存到磁盘里

5.2.1.3. 如果事务成功完成，我们就能删除日志中的待办事项列表，进而节省一些空间

5.2.2. 幂等

5.2.2.1. idempotent

5.2.2.2. 数据库日志中创建的每一项都有相同的效果，不管日志被执行一次、两次，还是更多次

5.2.2.3. 在从崩溃中恢复后，数据库只需重新执行任一完整事务的日志活动即可，而且处理不完整事务也变得很容易了

5.2.2.4. 任何不以“终止事务”项结束的日志活动会按照相反顺序撤销，让数据库恢复事务未开始前的状态

5.3. 能阻止不一致性

5.3.1. 排除了数据损坏，但并未消除数据丢失

6. 事务

6.1. 吉姆·格雷（Jim Gray）

6.1.1. 1992年首次出版

6.1.2. 《事务处理：概念与技术》（Transaction Processing:Concepts and Techniques

6.1.3. “容错”（Fault-tolerance）

6.2. 不管事务是完成还是“回滚”，数据库仍然能保持一致性

6.3. 每一笔事务都是原子态（Atomic）

6.4. 一笔原始态的事务不能被分成更小的操作

6.4.1. 要么整笔事务成功地完成，要么数据库处于其原始状态，就像事务从未开始一般

6.5. 事务能“锁定”单行或单列，或整张表

6.5.1. 一旦该项事务成功完成，就会“解锁”之前被它“锁定”的所有数据

6.5.2. 之后，其他事务就能更改之前被“冻结”的数据

6.6. 事务经常因为不可预料的原因而不能完成

6.6.1. 有时候数据库事务必须被取消，这被称为“回滚”或“放弃”一次事务

6.7. 如果一项事务需要“回滚”，数据库程序只需通过预写日志（比如待办事项列表）逆向操作，就能逆转事务中的每项操作

7. 两阶段提交协议

7.1. “预备提交把戏”

7.1.1. Prepare-thencommit Trick

7.1.2. 在预备阶段，“主管”复制品检查是否所有复制品都能完成事务。

7.1.3. 一旦所有事情都妥当，“主管”复制品就会让所有复制品提交数据

7.1.4. 在预备阶段，其中一个复制品出错了

7.1.5. “撤销”阶段，其中每个复制品都必须“回滚”事务

7.2. 复制是抵御数据丢失的绝佳方法

7.2.1. 将为朝向阻止任何数据丢失的目标做出巨大努力

7.3. 保有两份及以上的数据库拷贝

7.3.1. 每份数据库拷贝都被称为复制品（replica）

7.3.2. 所有拷贝的集合被称为复制数据库（replicated database）

7.3.2.1. 复制数据库能随时保持数据库的所有拷贝同步

7.3.3. 复制品在地理上是分开的

7.3.3.1. 其中一份复制品被一场灾难抹掉，另一份复制品也还在

7.3.3.2. 同一数据库的多份拷贝被存储在不同地点

7.4. 锁定（locking）

7.4.1. 死锁

7.4.1.1. 许多数据库都会定期运行侦测死锁的特殊程序。当发现一个死锁时，死锁的其中一项事务会被取消，以便让另一项事务进行

7.4.1.2. “回滚”能通过对待办事项列表把戏稍做变更来实现

7.4.1.2.1. 预写日志必须包含足够的额外信息才能在必要时撤销每次操作

8. 关系数据库

8.1. 埃德加·科德（E.F.Codd）

8.1.1. 1970年

8.1.2. IBM研究员

8.1.3. 论文《大型共享数据库数据的关系模型》（A Relational Model of Data for Large Shared Data Banks）

8.2. “虚表把戏”

8.2.1. Virtual Table Trick

8.2.2. 尽管所有的数据库信息都能被存储在一张固定大小的表中，数据库也能在需要时生成新的临时表（虚表）

8.3. 基本思想

8.3.1. 每张表都存储不同的信息集，但不同表中的个体通常都以某种方式相连

8.3.1.1. 表策略还有另一个巨大优势。如果表设计无误，对数据库的变更会更容易

8.3.1.2. 大量重复（课程细节）和少量重复（课程号）进行了交换。总体而言，这是笔好交易

8.4. 关键特征

8.4.1. 数据库中的信息有一个预定义结构

8.5. 数据库能提前计算出需要翻多少“块”页，并能记录每“块”开始和结束的页首

8.5.1. 用于快键查找的预计算块集合被称为“B树”（B-tree）

9. 备份

9.1. 某个特定时刻对一些数据的快照

9.2. 并不一定是最新的