2-2. 关系操作的基础算法(1)在线视频

我们首先来讲基于排序的实现算法

那么排序是我们这个计算机领域里面非常重要的一个算法

大家都知道排序呢，我们使用的是归并算法进行排序

那么归并算法的框架是什么样的呢，我在这给大家进行了一个总结

归并算法一般来说呢，我们把它分成两个阶段

那么第一个阶段我们要生成归并段，那么生成归并段怎么去生成呢

这个一般来说呢，要根据我内存的使用情况

也就是我内存缓冲区能够有多大，能支持我读入多少数据

所以后面我们要把缓冲区的这个大小我们可能要用缓冲区的块数来进行表达

那么我们用一个例子来说，比如说，我这样的一张关系表

比如说它一块是由两个元组构成

那么像这样一个关系表，大概就是三个磁盘块

如果说我的缓冲区只有两个磁盘块用来进行数据输入的话

那么我们对它来进行归并的话，我们就需要两次读入数据

比如第一次我把前两个块读进来，生成一个归并段

然后呢，第二次我把下一个块读进来，生成一个归并段

这就是生成一个归并段这样的一个过程

第二个过程就是讲归并段进行最终的一个归并过程

我们比如这个例子，我们已经生成了两个归并段

我们也把它叫做有序子表，然后呢，在最后一个过程当中呢

我们把两个有序子表进行最后一次归并

这就是排序算法的一个基本框架

我们把这种算法也叫作二路归并算法

当然了，有些情况下，如果数据量特别大的话

我们用两次的这种归并可能并不能成功

比如说这个例子，那么我们的假设仍然是这样

比如说这个数据量，数据呢，仍然是两个记录占一个磁盘块的话

它大概占了六个磁盘块

如果我们的内存仍然只有两个缓冲块用来进行数据读入的话

这样的话，我们对这个数据表来归并的话

可能我们用两次归并，并不能完成

这个时候我们就要采用多路归并

也就是说，我需要第一次呢，把它归并成三个有序子表

第二次再把它归并成两个有序子表

然后，在最后一次把它归并成最终的一个有序子表

这就是多路归并的这样的一种算法

那么多路归并算法呢，它的代价是怎么样子的呢

我们来看一下，如果我们用Br来代表

这个关系它的大小，它所占用磁盘块的数量的话

那么M是内存中用来进行数据读取的磁盘块的数量的话

那么多路归并的算法，实际上可以用这个公式来进行表达

那么其中这个M呢，我们刚才说了

是我们用于进行这个读入数据的这个缓冲区的数量

然后这个括弧里面的logMBr，它代表的就是归并的趟数

乘以一个2呢，表示的是我每次归并都要读入一次数据，写出一次数据

那个Br正好是四方块的数量，所以呢，归并的代价就可以用它进行表达

我们前面这个例子，如果我们令缓冲区的块数等于2的话

每一块只容纳两个记录的话

前面这个例子它一共需要的数据块的传送次数是36次

我们刚才给大家说的是归并排序算法的框架

现在大家就考虑就说归并排序算法是这样的

我们基于排序的关系运算的算法是什么样子的

基于排序的关系运算，实际上就在这个归并算法的框架里面来进行实现

也就说它实际上也只需要两步，第一步就是我采用归并算法

然后对整个数据来进行一个生成一个若干个有序子表

当然呢，这些有序子表的数量一定用与内存缓冲区的数量是相符合的

也就是说你不能多于内存缓冲区的数量

否则的话，后面我们没有办法进行操作，这是第一步

第二步呢，就是我或者是把所有的有序子表进行归并

生成一个有序子表，然后进行关系运算

或者是在对有序子表进行归并的过程当中来进行关系运算

我们下面就用例子来进行说明，比如说

我现在呢，要对选择运算

比如说我基于排序的这样的一种框架，对它进行实现的话

它的这个过程是怎么样的呢

好，它基本是这样的，也就是说

我们要用基于排序的算法对选择运算来进行实现的时候

一定是作用在非码属性上，这个，大家要知道

因为如果是主码的话，那么它自动已经排好序的了

我们只要使用二分查找算法就可以了

但是呢，非码属性则是无序的

所以呢，我们才能用基于归并的这样的排序算法来进行实现

那么它实现呢，基本上它的框架就是这样

就是我首先利用归并算法，按照搜索码的顺序，对数据进行排序

生成一个有序的这样的一个排序表

然后在这个排序表上，再使用二分搜索，这样一种方式来进行查找

那么这样查找的一个代价呢

那实际上就是排序的代价再加上一个二分搜索的代价

那就是二分搜索的代价我们就是知道

它实际上是整个数据库的大小，来除以个2

那么这就是选择运算

选择运算基本上来说就是整个数据排序之后再执行选择运算

这也就是说它是在整个归并算法的框架之后

那么下面我们来看其他的一些运算

我们来看一下消除重复元组，和分组统计

我们拿消除重复元组这样一种运算来进行说明

那么消除重复元组运算呢和选择运算不同

它是在归并算法的框架之内来进行实现的

也就是说首先呢，我们对这个数据表来进行一个归并

生成它的若干个有序子表，也就说第一个生成归并段

然后接下来我对归并段进行最后归并的过程当中

直接执行消除重复元组的运算，如果用一张图来表示呢

基本上就是这样，我拿到一个关系R

那我首先呢，对它进行排序，生成若干个有序子表

接下来我把若干个有序子表全部读在缓冲区里面来，M个缓冲区中

在这个缓冲区里面，我对它进行一些运算

生成多少个有序子表呢，那么这个是需要大家注意的

我生成有序子表的数目一定要跟缓冲区里面

能够使用读取数据的缓冲区的数量一致

我们下面用例子来进行一下说明，比如说，我有这样的一个文件

这个关系只有一列数据，这是为了简单来进行说明

我们仍然假设比如缓冲区里面，能够用来这个读取数据的呢，有3个

三个缓冲区块，那么每一个块呢，比如说只包含两个元组

那么这样的话呢，我对这个数据呢

我就可以首先对它进行归并生成三个有序子表

生成完三个有序子表之后，那么我就可以走第二步

对这三个有序子表进行归并，那么在这个归并的过程当中

我就可以执行消除元组的运算，那么怎么去执行呢

我这样去做，我们把三个有序子表当中每一个子表的第一块读到缓冲区里面

也就是说读到内存里面，然后我们从这每一块里面去选择数据最小的数据

选择完之后呢，我在缓冲区去查

看看有没有最小的数重复的

比如说，在其他的有序子表里面有没有和这个最小数重复的

如果有，那就把这个重复的删除，然后把这个最小数据输出

比如说这是1，那么在第三个有序子表的第一块里面有两个一

我们就把它删除掉，然后把1输出

然后接下来如果说这里面有一个缓冲区块已经空了

比如说第三个有序子表的缓冲区块已经空了

我就在外存上再把第三个有序子表的第二块读进来

然后我仍然在这个内存里面去找最小的值

比如是2，那么找到2之后呢，我把它输出来

再把其他块有重复的2直接删除掉，然后接下来我们

缓冲区如果空的话，我们接下来再把相应有序子表的其他的值给读进来

以此类推，永远都是从内存当中找最小的值

然后输出，然后把重复的删掉，然后接着从外存读入数据，这样一个过程

最后直到所有的数据块全部被读完为止

那么这就是消除元组的这样的一种实现方法

我们这个分组统计和消除元组是完全一样的

所以大家可以参照消除元组这样的一种算法

来对分组统计的算法来进行设计，这是没有问题的

那么刚才来说的，这个消除重复元组的算法代价是什么呢

我们看，刚才已经给大家说了

我们第二步的消除重复元组实际上就是在最后的归并的过程当中实现的

所以说这个算法的代价和排序算法的代价相同的

那么在这个里面，大家要注意的就是我们有序子表生成的数量

这个呢，一定要小于缓冲区用于读取数据的数量

这个是大家需要进行注意的