数据库页面动态管理(1)

数据库页面和一个可以动态调整的收纳盒相似，其中的隔板可以组装成存放袜子的格子，也可以组装成存放内裤的格子，还可以组装成存放其它什么物体的格子。只不过收纳盒存放的是物体，而数据库的页面存放的则是数据。

数据库页面的管理是数据库中最核心的功能，数据库所有的数据也都存储在页面上，数据库中通常称其为PAGE，页面的大小一般都是操作系统页面块的整数倍。操作系统页面块大小各不相同，有的2K、有的4K、甚至有的是16K，但一般都是2的n次方K，操作系统页面块大小也会导致数据库的页面大小随之变化。各种数据库的页面管理也有很大差异，但如果抽象一下就会发现页面上存在很多基本的操作，这也是软件开发最重要的方法，通过抽象以后可以编写很少的代码实现复杂的功能。各数据库的页面结构千差万别，但最基本的组件都是共有的，例如都有页头、项目录、数据区、空闲区和校验信息等。对这些组件的操作，构成了操作页面的所有功能，对一些功能做一下抽象以后，就发现很多功能都有共同点。数据库会把用户插入的记录存储在页面上，页面上存放的一条记录数据库内部通常叫SLOT，一个SLOT一般和用户的一条记录对应；但如果用户的记录较大，无法存储在一个页面上，则数据库会用多个页面来存储一条用户记录。页面空间的管理借鉴了操作系统堆栈管理的方法，数据和项目录从两个方向向中间增长，当数据和项目录相遇的时候说明空间全部用完。有的数据库把项目录存储在页面头的后面，数据存储在页面末尾，像Oracle、sqlserver；有些数据库将项目录存储在页面末尾，数据存储在页面头的后面，像DB2和ToprowDB。

为了详细的介绍数据库的页面动态管理方法，我今天先简化问题，不考虑锁、事务和日志相关的事情，只是考虑最基本的页面操作。

数据库的页面涉及到的最基本操作

我们使用收纳盒时，如果买了一些新袜子会存放到收纳盒里边，发现一些袜子款式太老会把它从收纳盒拿走扔掉，也有可能想把存放的袜子的位置换成存放内裤，当然使用收纳盒除了觉得整齐之外还有一个目的是需要找什么的时候能快速找到它们。数据库对页面的操作和我们对收纳盒的操作非常类似，可以归纳为增删改查几个基本操作，其它操作都可以用这几个操作组合而成。当然对页面的操作比这要复杂的多，其中我就增加了重整一个页面的操作，还增加校验一个页面的操作，这些操作其实在收纳盒上也经常存在。

1. 在页面上插入一条数据

2. 删除页面上的一条数据

3. 更新页面上的一条数据

4. 遍历页面的数据

5. 重整一个页面的数据
   

6. 校验一个页面的数据

但是要明白一点，这些数据和用户的行之间还有一些差异，毕竟用户的数据行有可能会很长，根本在一个页面上存不下，也有可能页面上的空间不足，无法完全存储一个数据行。这就涉及到页面相关的另外两个概念，链接行和迁移行。为了方便介绍这两个概念，我不得不先介绍ROWID这个概念，ROWID是数据库中定位一个SLOT的物理地址，物理地址就是根据这个地址可以直接找到这条数据在物理文件上的位置。我们邮寄包裹的时候一般都写的是物理地址，根据这个地址就可以直接定位到我们的收件地点；我们指路的时候常常会说再往前走100米，右转看见两间红色的房子，还有三栋白色的大楼，中间那栋就是你要找的地方，这个定位就不是直接能定位的，与当时所处的位置息息相关，如果你在任何一个地方这样找肯定找不到你想找的位置。ROWID中记录了数据所在FILE号、PAGE号和SLOT号，根据FILE号可以找的对应的物理文件，根据PAGE号可以直接确定文件上的偏移，根据ROWID可以直接定位到页面上对应的数据。知道了ROWID，我们再来看链接行和迁移行这两个概念：

• 链接行：所谓的链接行，一般指一行用户数据无法存入一个页面，这时候就会将用户的数据拆分成多个SLOT，存储在多个页面上；这多个SLOT之间通过一些辅助的方法联系在一起，这联系在一起的多个SLOT就叫一个链接行。链接行就相当于你买了一连排别墅，这几栋楼都是你的，全部可以存放你的东西。

• 迁移行：行迁移一般是更新操作引起的，如果一行数据所在的页面已经很满，但我们把该页面上的某一个SLOT还想更新的更长的时候就无法继续保存在这个页面上，这个更新操作就导致产生了迁移行。迁移行就相当于你先买了个小户型，现在不够住了换一个大房子，你在搬家之前给原地址留张字条，上面写上你新房子的地址，当有人找你的时候看了你留的字条就知道你的新家在那里了，根据新家的地址就能顺利找的你新家的位置。数据库为什么要迁移行，而不是移动行呢？因为数据库的数据也有可能会被别人找，这个别人一般都是索引，索引上记录了数据的ROWID，但如果更新数据的时候更新所有索引的ROWID，这个代价将非常昂贵，于是大神们就想了这个办法，只是将数据迁移走，在原来存储数据的地方存放一个新数据存储的位置，这就导致产生了迁移行。

说到这里你应该非常明确了，链接行是在插入数据的时候产生的，而迁移行是在更新数据的时候产生的，但其处理逻辑应该差不多相同。不是所有的数据库都如此，但大部分应该都是这样处理的。

在页面上插入一条数据

我们往收纳盒中存放物体，一般都是先找的一个收纳盒，看看里边有没有能存放这个物体的位置，然后决定是要换一个收纳盒还是将这个物体就存放在这个收纳盒中。页面插入一条数据和把物体存放到收纳盒中类似，也需要经过步骤，这些步骤主要有：

1. 查找一个能存放该数据的页面

2. 判断该页面能否完全插入当前数据

3. 在SLOT表中增加一个SLOT，修改页头的SLOT相关的信息

4. 在页面上查找空闲空间，让SLOT指向该空闲空间

5. 把数据拷贝到找到的页面的空闲空间上，设置SLOT指向的空闲空间的大小
   

6. 修改页头其它信息，例如修改空闲空间大小，修改空闲空间起始位置等信息

7. 更新页面的状态，标志页面为脏页

这里除了正确的维护页面的管理信息之外，更新页面状态信息，标志页面为脏页面也非常重要，只有这样缓冲区刷新操作才能发现该页面已经发生了改变，保证数据页面被正确的写入磁盘。

插入操作最复杂的莫过于查找空闲空间，这一步涉及到很多情况的处理：

1. 页面的空闲空间不足

2. 页面的空闲空间足够，空闲空间也足以存储要插入的记录

3. 页面的空闲空间足够，但空闲空间不足存储要插入的记录

4. 页面的空闲空间足够，但空闲空间是被未提交的删除操作释放的

5. 页面的空闲空间足够，但空闲空间是被未提交的更新操作释放的

6. 页面的空闲空间足够，空闲空间是被已经提交的删除操作释放的

7. 页面的空闲空间足够，空闲空间是被已经提交的更新操作释放的

8. 页面整个都是空闲的，但这条数据太大，根本无法全部存储在当前页面
   

是不是大家已经晕了，这都是什么情况啊，这些情况以后介绍动态变化的时候我会详细的说明。这里只是让大家有一个了解，计算空闲空间不是一个非常简单的过程，涉及到页面当前的状态和当前的页面上的所有操作。这也和我们往一个收纳盒装东西一样，一开始空着的收纳盒你可以随便装，但装装取取会把收纳盒弄的很乱，以后再装东西的时候除非你找的了一个非常合适的地方，否则你就得花时间先整理一下这个收纳盒，这样才能把你要放的东西放到收纳盒中。有时候一个东西太大了，我们需要把它分到多个收纳盒收纳，现实当中我们很多东西都是无法拆分的，例如衣服你总不能剪成两半存在收纳盒中，但可喜的是计算机中的数据没有无法拆分的情况，所以都可以拆了以后存在多个页面上。有的时候你的同一类东西过多，无法全部存入一个收纳盒，例如你有1000双袜子，你还有很多收纳盒，你为了查找方便，对收纳和做了归类，这样你只要能找到第一个存放袜子的收纳盒，就可以根据第一个存放袜子的收纳盒中的信息，找的剩下的存放袜子的收纳盒的位置，这样就能找到所有的袜子。

删除页面上的一条数据

要扔掉一个不喜欢的物体非常容易，我们什么时候碰见它都可以把它拿出来扔掉。但删除数据库中的一个数据却没有那么简单，因为看见它的时候往往处于扫描阶段，这个阶段不应该做删除操作，不过以前我接触过的一个数据库一开始确实是这么干的，这样做导致非常多的问题，一些严重的问题很难处理，最终还是放弃了这个实现方法。删除页面的一条数据比起插入来说还是要简单很多，因为它主要实现三个动作就可以完成这个任务：

1. 查找到删除记录所在的页面

2. 将该页面要删除的记录标记成删除

3. 更新该页面的状态，标记该页面为脏页面

删除一个页面的数据也涉及到三种情况需要处理：

1. 页面上的SLOT是一个简单的SLOT，直接标记成删除即可

2. 页面上的SLOT是一个链接行，需要继续删除链接行的下一个数据片段

3. 页面上的SLOT是一个迁移行，需要删除迁移以后的数据

更新页面上的一条数据

如果收纳盒中装满了袜子，我们还想把一条内裤存放到收纳盒中，这时候我们在不想新买收纳盒的情况下，最好的办法就是把收纳盒中的旧袜子扔掉几双，用腾出的空间来存放内裤。页面上也存在这种情况，有时候想把一条数据更新成新的数据，这时候可以拆成先删除再插入的方式处理，但这在数据库中实现的时候代价就太大了。首先数据库删除一条记录涉及到数据页面的修改，还涉及到该数据相关的所有索引数据的修改；另外重新插入的代价也不小，既要查找空闲空间，还需要将新数据插入到所有相关的索引中；更重要的是这样做会带来另一个并发问题，这里大家可以想想是什么并发问题？可以留言一起讨论。

数据库为了降低更新操作的代价，会将数据在原数据上进行更新，空间不够就换一下数据的位置，再不行就产生一个迁移行。当然更新操作也会涉及到索引的更新，但这个更新是难免的，必须要做的更新。从这些描述可以看到，页面数据的更新涉及到下面步骤：

1. 查找到要更新的数据所在的页面

2. 定位要更新的数据所在的位置

3. 尝试进行原地更新

4. 尝试在本页面查找空间空间，在页面内进行更新

5. 页面空间不足产生迁移行

6. 更新页面的状态，标记页面为脏页面

7. 更新索引数据
   

经过这些步骤一个页面的更新操作差不多就完成了，当然这是在没有考虑任何并发的情况下，如果同时有很多并发操作在进行，这个更新操作将会变的特别复杂，这里先不讨论这个问题。

遍历页面的数据

我们把数据存储在页面上，最终还是为了方便用户进行查询。所有页面的遍历也非常重要，大部分数据库的遍历过程都是一个顺序的遍历。但这里涉及到几个问题，需要解决：

1. 遍历过程中如果碰到一个链接行，要怎么处理？

2. 遍历过程中如果碰到一个迁移行，要怎么处理？

3. 遍历过程中如果碰到一个被链接行，需要怎么处理？

4. 遍历过程中如果碰到一个被迁移的行，需要怎么处理？

5. 遍历过程中如果碰到一个删除行，这个行怎么处理？

6. 遍历过程中如果碰到一个还没有提交事务删除的行，这个行怎么处理？
   

7. 遍历过程中如果碰到一个还没有提交事务插入的行，这个行怎么处理？

8. 遍历过程中如果碰到一个还没有提交事务更新的行，这个行怎么处理？

可以看到页面上的操作涉及到很多情况，但这些情况都是动态变化过程能产生的情况，今天只介绍存在这些情况，后面慢慢介绍数据库中对这些问题的解决方法。

重整一个页面的数据

我们前面介绍了一个页面上的最基本的增删改查操作，但在增和改过程中都发现了一个种情况，就是虽然整个页面的空闲空间足够存下当前记录，但空间都不是连续的，所以需要对页面做一个整理操作才能存入当前记录，这个操作就是重整操作。

重整页面的操作往往无法原地进行，所以需要一个辅助的空间才能完成整个页面的重整，重整过程中被标记成删除和缩短更新的SLOT所占用的空间都被回收，但如果该删除和更新操作还没有提交，则会预留该部分空间不能新占用。

所以页面重整基本步骤如下：

1. 从头循环遍历页面的每一个SLOT

2. 把每个SLOT的数据重整到另一个页面上

3. 用重整以后的页面覆盖原页面对应的空间

重整操作对有一些重发条件，所以重整操作并不会频繁发生。我不知道其它数据库的处理过程，但Toprow数据库重整过程并不会记录日志，所以重整操作相对来说代价并不高。

校验一个页面的数据

计算机中的磁盘并不可靠，磁盘的破坏很可能会损坏所有的数据。所以在读写磁盘数据的时候需要对数据进行校验，Toprow数据库对数据的校验设计比较简单，并没有挨个字符进行校验，只是校验了前后两个部分是否是同一次写入的内容。如果磁盘上的数据某一个字节发生变化，数据库并不能实时感知。

这是页面动态管理的第一个部分，主要介绍了页面的增删改查等基本操作，后面我会介绍数据库对于动态变化的管理过程，这就涉及到事务相关的很多知识。