手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

【天天新要闻】读改变未来的九大算法笔记02_数据库

2023-06-03 07:06:03 来源：博客园

(资料图)

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.数据库能提前计算出需要翻多少“块”页，并能记录每“块”开始和结束的页首