CHEN Jian's Java Blog

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读写可能会比较频繁。

Transaction会在数据库log中留下entry，如 引用 Start Transaction T … … Commit T (或Abort T) 根据log恢复数据时，transaction在log文件中留下的起止标识非常重要，它决定了对某一个transaction要不要做相应的恢复操作。 具体请看本人其他相关博客。

数据库的读写过程会经历三个地址空间。 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, 就是由它来决定的。

数据库的数据故障可以分为两类： 1. system failure. 比如断电导致内存中的数据未及写入硬盘，造成数据的不一致。这类故障可以通过数据日志来恢复(redo log或undo log) 2. media failure.  数据硬盘坏了，日志也放在硬盘里，数据和日志都丢失了。这类问题一般通过数据备份(archiving)来解决。即把数据dump到其他硬盘或磁带中，当故障发生时，恢复数据。还有一种做法是把数据实时同步到备库，当主库出现故障时将系统切换到备库。

这里说的小表，是指所有数据基本上可以被内存容纳的表 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数。 两张表你都需要扫描。

可以用Hash Table做数据库索引结构，一个bucket是一个block链表。 性能: 1. 如果每个bucket都只有一个block, 那么增、删、查都只有一两次block读写(增、删需要先读再写)，即一两次磁盘i/o. 这比其他各种索引都好的多。 2. 如果某个bucket有很多block, 不用说，发生在这个bucket上读写性能会很差。 3. 另外，这种索引对Range Query没有支持。

关系数据库中的索引一般使用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 这种)。

稠密、非唯一索引可能导致索引文件在存储空间上的浪费。举个例子，key=’中华民国是华人骄傲’ (多达9个字符)的记录有多少条，为它建立的索引项就有多少条。 有个解决办法是在索引项中为每条相应的记录开辟一个指针。这样key=’中华民国是华人骄傲’的索引项只须维护一份，原大量索引项所占的空间变成大量指针所占的空间。一般来说指针所占空间比较小，所以可以节省不少空间。 但是索引项中增加大量指针会使索引项本身的大小过于膨胀，这会影响索引扫描时的I/O速度(需要读更多block)。为了解决这个问题，我们可以专门使用一块空间集中存放所有索引项的指针集合。 这个在索引和数据之间的指针大集合称为 “bucket” (桶). 搜索引擎中常用的inverted index(倒排索引)，由于key的重复率特别高，就会经常使用bucket这种机制.

1. 索引文件是有序的，查找时可以用二分法或其他基于树型结构的查找法; 而记录文件不一定有序，时间复杂度可能等于记录数。 2. 索引文件存储字段较少，占用的block数比数据文件少，在索引文件中遍历，所需的I/O时间会短很多。 3. 索引文件如果足够小，可以直接放内存里，这样遍历起来就更快了。

data file一般是顺序文件(sequential file), 也就是说在磁盘中这个文件内部是按某个key排序的。 primary index(主索引)的key就是顺序文件的key.  主索引文件的排序方式与数据文件的排序方式相同. 如果要根据primary index查找key=6的记录，由于排序方式相同，你会发现所有key=6的记录都在一个block中或者几个连续的block中。 而secondary index(副索引)没有这个特性，它的key不是顺序文件的排序key, 也就是说副索引文件的排序方式与数据文件的排序方式并不一致。如果根据secondary index查找key=6的记录，由于排序方式不同，你会发现所有key=6的记录未必在同一个block中，也未必在几个连续的block中。 可以看出，使用secondary index对非唯一性字段进行查找时，由于目标记录不在同一个block中，也不在连续的几个block中，磁盘I/O的时间比起基于primary index的查找过程会多很多。 同理可知，对于范围查找如 key between 7 and 10,  secondary index 也有相同的劣势。