数据库

http://blog.jobbole.com/100349/ 重点是本篇博客

时间复杂度：算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。用大O表示

理解数据库的3个部分：

底层和上层的数据库组件概况

查询优化过程的概况

事务和缓冲池管理概况

3中数据结构： 矩阵，树，哈希表

树和索引，B+树需要自我整理和自我平衡，插入和删除操作时O(log(N))的复杂度。使用太多的索引，会减慢快速插入/更新/删除表中的一个行的操作，因为数据库需要一代价高昂的索引运算来更新表的索引。另外，增加索引会给事务管理器带来更多的负荷。

哈希表是一个重要的数据结构，当想快熟查值时，哈希表史哥不错的选择，这个数据结构被数据库用来保存一些内部的东西，比如锁表或者缓冲池。

1.关键字的哈希函数 元素的关键字所计算出来的哈希值确定了改元素的位置（哈希桶）。

2.关键字的比较函数 一旦正确找到了哈希桶，必须用比较函数在桶内找到你要找的元素。

一个好的哈希函数是让哈希桶里包含的元素尽量少，时间复杂度是O(1)

举证 VS 哈希表

一个哈希表可只装载一半到内存，剩下的哈希桶可以留在硬盘上。

矩阵的话，就需要一个连续的内存空间，如果加载一个大表，很难分配足够的连续内存空间。

全局概览

数据库是个易于访问和修改的信息集合。一堆文件也能达到这个效果，不过它允许：使用事务来确保数据的安全和一致性，快速处理百万条以上的数据。

组成数据库的核心组件有：

进程管理器（process manager）：db需要一个管理 进程/线程池，实现纳秒级操作。

网络管理器（network manager）：网络I/O是个大问题，所以一些db有自己的网络管理器。

文件系统管理器（file system manager）:磁盘I/O是db 的首要瓶颈。具备一个文件系统管理器来完美处理OS文件系统。

内存管理器（memory manager）：为避免磁盘I/O带来的性能损失，需要大量的内存。但是如果要处理大容量内存你需要高兴的内存管理器，尤其是在很多查询同时使用内存的时候。

安全管理器（security manager）:用于对用户的验证和授权

客户端管理器（client manager）：管理客户端连接

.......

工具：

备份管理器（backup manager）：用于保存和恢复数据

复原管理器（recovery manager）：用于崩溃后重启数据库到一个 一致性状态。

监控管理器（Monitor manager）：记录数据库活动信息和提供监控数据库的工具。

......

查询管理器：

查询解析器（query parser）:检查查询是否合法

查询重写器（query rewriter）:预优化查询

查询优化器（query optimizer）:插叙优化

查询执行器（query executor）:用于编译和执行查询

数据管理器：

事务管理器（transaction manager）:用于处理事务

缓存管理器（cache manager）:数据被使用之前置于内存，或者数据写入磁盘之前置于内存。

数据访问管理器（Data access manager）:访问磁盘中的数据。

缓冲区保存的是页（最小的数据单位）而不是行（人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没写入磁盘，就是脏页。很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联。

现代数据库不会使用纯粹的隔离作为默认模式，因为它会带来巨大的性能消耗。Sql 一般定义4个隔离级别：

串行化：100%隔离

可重复读：事务之间在新数据方面突破隔离，对已存在数据仍旧隔离。（幻读）

读取已提交：（不可重复读）

读取未提交：最低的级别的隔离。（脏读）

多种数据库添加了自定义的隔离级别（PostgreSQL,Oracle,SQL Server的快照隔离），而且并没有实现SQL规范的所有级别（尤其是读取未提交级别）。

并发控制：

确保隔离性，一致性和原子性的真正问题是对相同数据的写操作（增删改）：

如果事务只是读取数据，他们可以同时工作，不会更改另一个事务的行为

如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。

这个问题叫 并发控制

解决这个问题的理想办法是每次一个事务的创建或取消时：

·监控所有的事务的所有操作；

·检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突

·重新编排冲突事务中的操作来减少冲突部分

·考虑事务可能被取消

这种解决办法是对冲突的调度问题，是个对CPU开销很大的优化问题。

锁管理器

为解决这个问题，多数 数据库使用锁和数据库版本控制

悲观锁：

如果一个事务需要一条数据，它就把数据锁住，如果另一个事务也需要这条数据,它就必须要等第一个事务释放这条数据，这个锁叫排它锁。

共享锁：

如果一个事务只需要读取数据A,它会给数据A加上共享锁并读取，如果第二个事务也需要仅仅读取数据A，它会给数据加上共享锁并读取，如果第三个事务需要修改数据A,它会给数据A加上排它锁，但是必须等待另外两个事务释放它们的共享锁。

同样，如果数据块被加上排它锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。

锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：

被哪个事务加的锁

哪个事务在等待数据解锁

死锁: 2个事务永远在等待一块数据：

死锁发生时，锁管理器要选择取消（回滚）一个事务，以便消除死锁。

要考虑的问题： 杀死数据修改量最少的事务？ 杀死持续时间最短的事务？ 杀死能用更少时间结束的事务？一旦发生回滚，有多少事务会受到回滚的影响？

在作出选择之前，锁管理器需要检查是否有死锁存在。超时设定：如果一个锁在超过时间内没有加上，那事务就进入死锁状态。两端锁：实现纯粹隔离最简单的方法是：事务开始时获取锁，结束时释放锁。就是说，事务开始前必须等待确保自己能加上所有的锁，当事务结束时释放自己持有的锁。理论上行的通，但为了等待所有的锁，大量时间被浪费了。

两段锁协议（two phase locking protocol）： 成长阶段，事务可以获得锁，但不能释放锁。收缩阶段：事务可以释放锁（对于已经处理完而且不会再次处理的数据），但不能获得新锁。

真实的数据库涉及更多的锁：意向锁，intention lock 和更多的粒度（行级锁，页级锁，分区锁，表锁，表空间锁）

数据版本控制：

每个事务可以在相同的时刻修改相同的数据

每个事务有自己的数据拷贝（或者叫版本）

如果2 个事务修改相同的数据，只接受一个修改，另一个将被拒绝，湘桂的事务回滚

除了两个事务写相同的数据时，数据版本控制各个方面都比锁表现的更好，只不过你会发现磁盘空间消耗巨大。

提高隔离级别会增加锁的数量和事务等待加锁的时间，这也是为什么多数数据库默认不会使用最高级别的隔离。

日志管理器

出现的问题：

为了提升性能，数据库把数据保存在内存的缓冲区内，但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。

你可以把所有的数据都写在磁盘上，但如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的原子性

解决办法：

·影子副本/页（shadow copies/pages）:每个事务创建自己的数据库副本（或部分数据库的副本），并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即使用文件系统的一个把戏，把副本替换到数据中，然后删掉『旧』数据。

·事务日志（Transaction log）:事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或者回滚，数据库知道如何移除或完成尚未完成的事务。

WAL（write-Ahead logging protocol）（预写式日志）

影子副本会制造大量的磁盘开销，所以更多的是用事务日志。

wal协议的3个规则：

每个队数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志

日志记录必须按照顺序写入；

当以个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。

如何找到写日志的同时保留良好性能的方法。如果事务日志写的太慢，整体都会慢下来。

ARIES 是 数据库恢复原型算法 这个技术达到一个双重目标：写日志的同时保持良好的性能，快速和可靠的数据恢复。

事务的每个操作（增删改）产生一条日志：

LSN：（log sequence number） 唯一的日志序列号

TransID: 产生操作的事务ID

PageID:被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处的位置。

PrevLSN: 同一个事务产生的上一条日志记录的链接。

.......

日志缓冲区

为防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。

当查询执行器要求做一次修改：

1) 缓存管理器将修改存入自己的缓冲区；

2) 日志管理器将相关的日志存入自己的缓冲区；

3) 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）；

4) 接着（不久以后）日志管理器把日志写入事务日志，什么时候写日志由某算法来决定。

5) 接着（不久以后）缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定。