数据库原理

基础知识

时间复杂度

时间频度用以描述一个算法处理一定量数据需要花多长时间。这里的时间不是常规意义上的时分秒，那依赖于硬件环境，没有意义；这里的时间指的是运算次数，运算次数的多少决定了时间多少的相对值，运算次数多的相对执行时间就长。

数据量不同，运算次数就不同，所以比较绝对运算次数也是没有意义的；实际上比较的是当数据量增加时，运算次数增加的趋势，这就是时间复杂度；好的算法不会随着数据量的增加和翻倍增加运算次数。

下图列出了常见的时间复杂度，展示了当数据量增加时，运算次数增加的趋势。

常见时间复杂度

从低到高解释一下上述算法时间复杂度，以需要处理2000条数据为例：

  • O(1)：只需要执行一次运算；
  • O(log(n))：需要执行7次运算；
  • O(n)：需要执行2000次运算；
  • O(n*log(n))：需要执行14,000次运算；
  • O(n^2)：需要执行4,000,000次运算；
  • O(n!)：溢出了。

以查找为例，查找不同数据的情况所需的运算次数是不一样的；当我们讨论一个算法的时间复杂度时，都以平均情况为例进行讨论。

常见排序和查找方法的时间复杂度

算法 平均时间复杂度 最坏时间复杂度
冒泡排序 O(n^2) O(n^2)
快速排序 O(n^2) O(n*log(n))
二叉树排序 O(n^2) O(n*log(n))
堆排序 O(n*log(n)) O(n*log(n))
顺序查找 O(n)
二分查找 O(log(n))
二叉排序树查找 O(log(n))
哈希表法 O(1)

合并排序

排序树

二叉查找树是带有特殊属性的二叉树，每个节点的关键字必须：

  • 比保存在左子树的任何键值都要大
  • 比保存在右子树的任何键值都要小

B+树

哈希表

数据库

数据库是由多种互相交互的组件构成的。

客户端管理器

客户端管理器是处理客户端通信的。

查询管理器

事务管理器

一个ACID事务是一个工作单元，它要保证4个属性：

  • 原子性（Atomicity）: 事务『要么全部完成，要么全部取消』，即使它持续运行10个小时。如果事务崩溃，状态回到事务之前（事务回滚）。
  • 隔离性（Isolation）: 如果2个事务 A 和 B 同时运行，事务 A 和 B 最终的结果是相同的，不管 A 是结束于 B 之前/之后/运行期间。
  • 持久性（Durability）: 一旦事务提交（也就是成功执行）,不管发生什么（崩溃或者出错），数据要保存在数据库中。
  • 一致性（Consistency）: 只有合法的数据（依照关系约束和函数约束）能写入数据库，一致性与原子性和隔离性有关。

经典的例子是从账户A到账户B的汇款。假设有2个事务：

  • 事务1（T1）从账户A取出100美元给账户B
  • 事务2（T2）从账户A取出50美元给账户B

我们回来看看ACID属性：

  • 原子性确保不管 T1 期间发生什么（服务器崩溃、网络中断…），你不能出现账户A 取走了100美元但没有给账户B 的现象（这就是数据不一致状态）。
  • 隔离性确保如果 T1 和 T2 同时发生，最终A将减少150美元，B将得到150美元，而不是其他结果，比如因为 T2 部分抹除了 T1 的行为，A减少150美元而B只得到50美元（这也是不一致状态）。
  • 持久性确保如果 T1 刚刚提交，数据库就发生崩溃，T1 不会消失得无影无踪。
  • 一致性确保钱不会在系统内生成或灭失。

原子性和一致性太像了？

SQL一般定义4个隔离级别：

  • 串行化(Serializable，SQLite默认模式）：最高级别的隔离。两个同时发生的事务100%隔离，每个事务有自己的『世界』。
  • 可重复读（Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。
    举个例子，如果事务A运行”SELECT count(1) from TABLE_X” ，然后事务B在 TABLE_X 加入一条新数据并提交，当事务A再运行一次 count(1)结果不会是一样的。
    这叫幻读（phantom read）。
  • 读取已提交（Read committed，Oracle、PostgreSQL、SQL Server默认模式）：可重复读+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或删除）是可见的。
    这叫不可重复读（non-repeatable read）。
  • 读取未提交（Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（但并未提交，事务B仍在运行中），事务A再次读取数据D时，数据修改是可见的。如果事务B回滚，那么事务A第二次读取的数据D是无意义的，因为那是事务B所做的从未发生的修改（已经回滚了嘛）。
    这叫脏读（dirty read）。

TODO 结合事务

参考