redo log, undo log中的"do" 都是idempotent的. 所谓的redo, 就是把数据改成log entry所记录的新值；不管故障发生时数据是不是已经为新值，在恢复时把数据设成新值总是无害的，因为“设为新值”这个操作是idempotent的。 undo也一样，即把数据改成旧值。 脑子里要建立这个意识，redo/undo其实都是赋值操作，而不能是“增1”、“减1”这种non-idempotent操作。
数据库的数据故障可以分为两类： 1. system failure. 比如断电导致内存中的数据未及写入硬盘，造成数据的不一致。这类故障可以通过数据日志来恢复(redo log或undo log) 2. media failure. 数据硬盘坏了，日志也放在硬盘里，数据和日志都丢失了。这类问题一般通过数据备份(archiving)来解决。即把数据dump到其他硬盘或磁带中，当故障发生时，恢复数据。还有一种做法是把数据实时同步到备库，当主库出现故障时将系统切换到备库。
数据库的读写过程会经历三个地址空间。 1. disk 2. buffer 3. 当前查询或事务自己的地址空间。 所有输入数据都要先流经buffer才能到达disk。反之亦然：所有输出数据都要先从disk进入buffer，才会到达客户端。 也就是说，可以 3=>2=>1或1=>2=>3, 不能直接1=>3或3=>1. 不仅数据读写如此，redo log和undo log的写入也要先经buffer，才能进入disk. 有个专门的buffer manager来管理buffer, 比如在什么时机将数据flush至disk, 就是由它来决定的。
Transaction会在数据库log中留下entry，如 引用 Start Transaction T … … Commit T (或Abort T) 根据log恢复数据时，transaction在log文件中留下的起止标识非常重要，它决定了对某一个transaction要不要做相应的恢复操作。 具体请看本人其他相关博客。
undo logging机制的基本原理是： 进行数据恢复时，对于Committed Transaction不做处理，对于Incomplete Transaction，则将相关数据写回成Transaction开始前的旧值。 记录log 引用 Start Transaction T … 记录：X被修改前的值是A 记录：Y被修改前的值是B 记录：X被修改前的值是C … Commit Transaction T 根据log恢复 1. 从下往上扫log文件 2. 遇到有Start无Commit的Transaction时，依次将…, X的值改回为C, Y的值改回为B, X的值的改回为A. 可靠性如何保证？ 1. Undo logging要求所有数据改动都已经写入disk了，才能将Commit Transaction这种log entry写入disk，这就保证commited transaction相关的数据改动已经真的持久化了。 2. Undo Logging还要求先在log文件中记录数据的旧值，再将数据改动持久化。当发生断电时，数据改动可能已经持久化，也可能还没有； 进行数据恢复时不必管有没有，一律把数据恢复成旧值即可，有可能是多余的，也有可能不是，总之对数据一致性是无害的。 Undo Logging的缺点 必须先将数据改动写入disk, 才能标识一个Transaction的结束； 也就是说，要完成一个Transaction, 必须将数据改动写入disk, 不能再在buffer里放着。缺点就是，数据改动可能没有累积到一定的量，就要从buffer中flush中去，所以I/O读写可能会比较频繁。
redo logging机制的基本原理是： 进行数据恢复时，对Incompleted Transaction不做处理；而对Committed Transaction，把记录了的数据改动再重现做一遍。 记录log 引用 Start Transaction T … 记录：X被修改后的值是A 记录：Y被修改后的值是B 记录：X被修改后的值是C … Commit Transaction T 根据log恢复 1. 从上往下扫log文件 2. 遇到Commit Transaction时，依次…, 将X的值改回为A, Y的值的改会为B, X的值改为C… 可靠性如何保证？ Redo logging要求一个transaction的所有log entry都已经写入disk了，才能把数据改动写入disk. 进行数据恢复时，根据这个规则, 对于Incomplete Transaction我们可以断定数据改动还没写入disk, 所以可以直接忽略； 而对于Commited Transaction, 数据改动可能已经写入disk，也可能未写入, 这时只须根据log把数据改动做一遍，可能白做，但绝对无害。 Redo Logging的缺点 在把一个transaction的所有log entry flush to disk之前，还不能flush数据改动； 也就是说，要有足够大的buffer, 容纳这些数据改动，直到transaction结束. 所以，redo logging可能比较占用内存。
这里说的小表，是指所有数据基本上可以被内存容纳的表 1. 选择、投影操作 所需内存空间：1个block大小对应的内存（称为1个内存单位，下同）；这里可以使用iterator模式，即找到一条block就立即返回一个block，所以只须1个内存单位 磁盘I/O次数： 该表记录所占的block数，因为你需要全部扫描一遍。（不考虑使用索引的情况，下同） 2. Count/Max-Min/Sum/Select Distinct 所需内存空间：表记录占了多少个block，就需要多少个内存单位。对于这类操作，你无法使用iterator模式； 你必须把所有记录加载到内存中，才能得出最终结论。所以你需要N个内存单位 。 磁盘I/O次数：该表记录所占的block数，因为你需要全部扫描一遍 3. 连接操作 所需内存空间： min(A表的block数，B表的block数). 因为你需要把其中较小的一个表全部加载到内存中，再与另外一张表连接。 磁盘I/O次数：A表记录所占的block数 + B表记录所占的block数。 两张表你都需要扫描。
关系数据库中的索引一般使用B+树结构（或其变体） 有几点值得一说： 1. B是”Balanced”的意思，意即从树根到所有树叶的路径都一样长 2. 图中每个结点都是一个磁盘block 3. 叶结点中向下的箭头指向数据记录 4. 增删记录时可能会导致结点的递归分裂或合并 5. 每个叶节点的最右边有一个指针指向下一个更大的索引项所在的叶结点 性能： 1. 增、删、查（单条记录）的I/O次数约等于树的层高 2. 树的层数取决于记录数和每个block可以存放的索引项的数目（这个数目也决定了一个结点可以有多少个子结点）。如果block大小=4k, 索引字段类型是整型，那么一个3层的B-树可以索引1500多万的记录数(具体算法参见hector garcia-molina《数据库系统实现)。 也就是说，大部分情况下，三层就够了。 3. 每个叶节点的最右边的指针可以使Range Query成为可能(即范围查询, key between 100 and 200 这种)。
可以用Hash Table做数据库索引结构，一个bucket是一个block链表。 性能: 1. 如果每个bucket都只有一个block, 那么增、删、查都只有一两次block读写(增、删需要先读再写)，即一两次磁盘i/o. 这比其他各种索引都好的多。 2. 如果某个bucket有很多block, 不用说，发生在这个bucket上读写性能会很差。 3. 另外，这种索引对Range Query没有支持。
稠密、非唯一索引可能导致索引文件在存储空间上的浪费。举个例子，key=’中华民国是华人骄傲’ (多达9个字符)的记录有多少条，为它建立的索引项就有多少条。 有个解决办法是在索引项中为每条相应的记录开辟一个指针。这样key=’中华民国是华人骄傲’的索引项只须维护一份，原大量索引项所占的空间变成大量指针所占的空间。一般来说指针所占空间比较小，所以可以节省不少空间。 但是索引项中增加大量指针会使索引项本身的大小过于膨胀，这会影响索引扫描时的I/O速度(需要读更多block)。为了解决这个问题，我们可以专门使用一块空间集中存放所有索引项的指针集合。 这个在索引和数据之间的指针大集合称为 “bucket” (桶). 搜索引擎中常用的inverted index(倒排索引)，由于key的重复率特别高，就会经常使用bucket这种机制.