CN103425802B

CN103425802B - 一种磁盘文件的快速检索方法

Info

Publication number: CN103425802B
Application number: CN201310409275.6A
Authority: CN
Inventors: 焦瑞莉; 汪安春; 李廷廷; 赵长青
Original assignee: BEIJING AOMI FEIKE TECHNOLOGY Co Ltd; Beijing Information Science and Technology University
Current assignee: Beijing Keluofeite Technology Co ltd
Priority date: 2013-09-10
Filing date: 2013-09-10
Publication date: 2017-01-25
Anticipated expiration: 2033-09-10
Also published as: CN103425802A

Abstract

本发明提供了一种磁盘文件的快速检索方法，包括如下步骤：步骤1、申请N个用于存储磁盘中所包含文件信息的内存块；步骤2、将该磁盘目录下所有文件信息存入到N个内存块中；步骤3、将步骤2中遍历得到的每一个文件作为跳表结构中一列中的节点依次插入跳表结构中，建立跳表；步骤4、在跳表中查找磁盘文件：确定比对节点，当比对节点的后向指针指向的节点为空节点或查找节点的值小于比对节点的后向指针指向的节点的值时，将比对节点的下向指针指向的节点更新为比对节点，并与查找节点继续比较；当查找节点的值大于比对节点的后向指针指向的节点的值时，此时将比对节点更新为其后向指针指向的节点，并与查找节点继续比较。

Description

一种磁盘文件的快速检索方法

技术领域

本发明涉及计算机技术领域，具体涉及一种磁盘文件的快速检索方法。

背景技术

由于计算机科学技术的高速发展，软件日益丰富，磁盘空间越来越大，这使得大量的文件存储在磁盘中成为可能。在系统研发的过程，判断某个文件是否存在于磁盘中，甚至存放在哪个目录中就变得非常困难，有时还需要对目录和目录下所有的子目录以及文件进行枚举，以找到该文件。在现有的方案中，采用了比较简单的数据结构。当文件和目录数量很大的时候，导致程序性能严重下降，并且保存和恢复的时间很长，这将降低用户体验。同时，当一个目录或者文件被从硬盘上删掉的时候，也很难快速将其记录从目录列表中清除掉。

发明内容

有鉴于此，本发明提供了一种磁盘文件的快速检索方法，能够实现对磁盘中大数据量文件的快速检索。

有益效果：

本发明通过在检索磁盘文件之前建立跳表，由于在跳表中查找代表文件的节点时采用了下向指针和后向指针，与现有技术中逐个比较文件名大小进行文件查找相比，本发明的采用的方法大大节省了时间成本，实现了快速检索的目的；

同时，本发明通过采用断点恢复，如果在遍历文件过程中非正常退出，则可以在再次启动时，从上一次断点位置恢复遍历过程，而避免重复遍历已经搜索到的文件，因此，可以进一步节省时间。

附图说明

图1为本发明中跳表的结构示意图。

图2为本发明中的节点查找的原理图。

具体实施方式

下面结合附图并举实施例，对本发明进行详细描述。

本发明提供了一种磁盘文件的快速检索方法，包括如下步骤：

步骤1、申请N个内存块，其中每个内存块包括4字节共32比特的位图和32个数据块，对每一个内存块里的32个数据块，均采用虚拟指针，即该数据块的虚拟指针为所在内存块的块号和在该内存块中的位置，即偏移量；每个数据块中记录磁盘中一个文件信息，该信息包括文件的序号、存储路径、文件名、文件大小以及文件的最后一次访问时间；每一个数据块依次对应位图中的相应位，为1表示该位所对应的数据块被占用，为0则表示空闲；

步骤2、遍历用户需要监测的磁盘目录，将该磁盘目录下所有文件信息按顺序依次存入到步骤1建立的内存块的数据块中，当一个内存块中的全部数据块被占用后，再将该内存块中的最后一个文件信息中的路径和文件名存储到磁盘文件currentdir.dat中，将该内存块中的所有数据追加保存到磁盘文件memsave.bin中；

步骤3、建立跳表:

S301、跳表结构的创建：

在内存中申请M个内存块用来存放跳表结构；

然后创建一个具有行数为MAXLEVEL的跳表结构，该跳表结构的第一列中设置MAXLEVEL个头节点，最后一列设置有MAXLEVEL个空节点；由于在跳表中查找某一特定节点所需的时间和跳表的节点总数之间成线性关系，当跳表中节点个数增加时，查找节点的时间也随之增加。本发明的采用跳表技术是试图在跳表的查找上加上折半查找的特性，跳表的行数就是把折半查找的次数减1，例如，假如跳表的行数为1，则折半查找的次数为0，查找的效率等于跳表的查找效率；假如跳表的行数为2，则折半查找的次数为1，在跳表中查找的效率相当于在“节点总数为跳表中总节点数的1/2的跳表”的查找效率。跳表的行数越多则查找的效率越高，同时所需要的内存空间也就越大，因此，本发明中考虑到在保证查找效率同时节省空间，跳表行数MAXLEVEL取为lg(N)，N为步骤2中遍历得到文件的文件个数，即为跳表的列数。

S302、将步骤2中遍历得到的每一个文件作为跳表结构中一列中的节点依次插入跳表结构中，得到跳表，具体方法如下：

A、A、令跳表结构中每个节点均采用虚拟指针，每个节点的虚拟指针包括后向指针和下向指针，其中任一个节点的后向指针指向跳表结构中该节点所在行向后相邻的节点，任一个节点的下向指针指向跳表结构中该节点所在列向下相邻的节点；则跳表结构中，每一个头节点的后向指针的指向均为该行的空节点，每个头节下向指针的指向为其下一行的头节点，最后一行头节点的下向指针为空；

B、从步骤2中的数据块中依次取出文件信息，并将一个文件信息对应一列中的n个节点作为插入的节点，其中n在1和MAXLEVEL之间随机选择；

C、当要向跳表结构中插入第一列节点时，将该列节点插入到头节点的后一列，其中n个节点的排列方式为从该列的最后一行依次向上排列；

根据插入节点后的跳表结构，更新每个节点的虚拟指针；即，修改每一个头节点的后向指针以及增加每一个插入节点的后向指针和下向指针，使插入节点的指针指向头节点的后向指针所指的节点，并依次把头节点的后向指针都指向插入列的对应行节点；

D、从插入第二列节点开始，针对每一列要插入的节点，首先找到跳表结构中的最后一行的第二个节点，作为对比节点，判断对比节点的值与插入节点的值的大小：

如果插入节点的值比对比节点的值小，则将该列插入节点插入对比节点所在列的前一列；

如果插入节点的值比对比节点的值大，将对比节点更新为其后向指针所指向的节点，并与插入节点继续比较，直到插入节点的值小于对比节点的值，则将该列插入节点插入对比节点所在列的前一列；

根据插入节点后的跳表结构，更新跳表结构中每个节点的虚拟指针；

其中，节点的值定义为：该节点所代表文件的文件名对应的字符串的ASCII码值；

E、对每一个插入的节点信息进行描述：步骤2中该节点所代表的文件信息所在的内存块的编号、步骤2中该节点所代表的文件信息所在的数据块的偏移量、该节点在跳表内存块中的编号以及该节点的虚拟指针；把每个节点的描述信息存储到对应的数据块中；

F、按照上述方法，将步骤2中的遍历到的每一个文件作为一个节点插入到跳表结构中，生成跳表；

G、将跳表存入磁盘文件slsave.bin中；

步骤4、在跳表中查找磁盘文件：

将要查找的每一个文件作为一个查找节点，在跳表中，除头节点外，将跳表的第一列第一行的节点作为比对节点，判断查找节点的值与比对节点的值的大小：

a、如果查找节点的值小于跳表中第一列第一行的比对节点的值，则跳表中找不到该查找节点；

b、当比对节点的后向指针指向的节点为空节点或查找节点的值小于比对节点的后向指针指向的节点的值时，将比对节点的下向指针指向的节点更新为比对节点，并与查找节点继续比较；

当查找节点的值大于比对节点的后向指针指向的节点的值时，此时将比对节点更新为其后向指针指向的节点，并与查找节点继续比较；

c、重复执行步骤b，直到找到与查找节点值相同的节点，返回该节点的描述信息；如果查找节点的值大于跳表中最后一列节点的值，则跳表中找不到该查找节点；

根据查找节点的描述信息到磁盘文件currentdir.dat和memsave.bin中调取该文件。

本发明中，由于在插入节点过程中随机确定每一列的节点个数，则跳表结构中某一个节点x的后向指针所指向的节点就未必是其后一列的节点，有可能是相隔几列的节点，因此，在查找节点时，当查找节点的值大于节点x的值时，根据本发明的技术方案可知，此时将节点x后向指针指向的节点y更新为比对节点，与查找节点继续比较，如果查找节点的值仍大于节点y的值，继续查找。从查找的方式来看，对比与传统的查找方式，即将查找节点的值逐个与每一个节点进行比较来说，本发明的方法跳过了节点x与节点y之间相隔的几列节点的比较过程，因此在查找过程中可大大节省时间成本。

本发明中，当删除文件的时候，为了降低成本，提高系统的整体性能，还采用了内存压缩，即，将前面和后面的内存块的合并过程。4字节的位图共32位，每位用0和1表示，0表示对应的内存块空闲，1表示内存块被占用，例如当位图bitmap=0xFFFFFFFF时，表示所有数据块均被占用，位图bitmap=0x00000000时表示所有数据块均未占用，此时将其释放即可达到内存压缩功能。因此，首先将每个内存块的位图与0x00000000进行比较，如果两者相等就将此内存块从链表中删除并释放，并将其后的内存块的编号向前移1；若位图与0x00000000不相等，则保留，继续比较下一个内存块的位图值。

本发明中还涉及到快速恢复的设计，即从第二次文件检索开始，每一次文件检索程序前，先执行所述步骤1，然后从磁盘文件memsave.bin中恢复步骤2要得到的数据，再从slsave.bin中恢复步骤3需要的数据，最后执行步骤4，这样可以节省步骤2中遍历文件和步骤3中建立跳表的时间，达到快速恢复的目的。

在遍历目录的过程中，如果用户退出了程序，当下次用户再次启动时，不能再从头开始搜索，而是应该从上一次停止的位置(通过读取currentDir.dat文件中所存内容确定)继续开始搜索，这样可以提高用户体验，节省时间，具体方法为：

在执行步骤2过程中，如果发生非正常退出，则下次启动时，先执行步骤1，完成后，在执行步骤2之前，从currentDir.dat文件中获得上次目录遍历的中断文件名，将memsave.bin恢复到内存，进入该中断文件所在目录，开始遍历该文件后面的子目录和文件，并把文件名写入currentDir.dat文件，文件信息存入memsave.bin中；最后执行步骤3-4。

下面举例说明，在跳表中查找节点（磁盘文件）的过程：

在如图2所示的跳表中查找节点117，具体步骤为：

(1)与21比较，比21大，再与21的后向指针所指的节点37进行比较；

(2)与37比较，比37大，由于37的后向指针为空，则从37的下向指针所指的节点（即下一个节点37）继续查找，再与37的后向指针指向的71继续比较；

(3)与71比较，比71大，向71的后向指针指向的节点（空节点）查找，因为找到空节点，所以从71的下向指针所指向的节点查找；

(4)与85比较，比85大，从85的后向指针指向的节点（117）查找；

(5)与117比较，等于117，找到了节点。

按照本发明提供的文件检索方法对5万个磁盘文件进行检索，则测试记录如下：

*对于改进算法所做的定位任一文件所用时间的测试，分别对深度为2、5、6、9的文件进行测试，测试时间分别为130ms、140ms、190ms、500ms，平均时间为240ms。

对包含5万个文件的目录进行测试的结果表明，快速磁盘文件检索算法能够大大提高文件检索效率，并迅速为文件目录同步、文件传输提供文件列表，使文件传输系统及时响应文件系统的变化，基本达到了设计目标。

综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种磁盘文件的快速检索方法，其特征在于，包括如下步骤：

步骤1、申请N个内存块，其中每个内存块包括4字节共32比特的位图和32个数据块，对每一个内存块里的32个数据块，均采用虚拟指针，即该数据块的虚拟指针为所在内存块的块号和在该内存块中的位置，即偏移量；每个数据块中记录磁盘中一个文件信息，该信息包括文件的序号、存储路径、文件名、文件大小以及文件的最后一次访问时间；

当所述步骤2发生非正常退出时，下次启动时，先执行步骤1，完成后，在执行步骤2之前，从currentDir.dat文件中获得上次目录遍历的中断文件名，将memsave.bin恢复到内存，进入该中断文件所在目录，开始遍历该文件后面的子目录和文件，并把文件名写入currentDir.dat文件，文件信息存入memsave.bin中；最后执行步骤3-4；

步骤3、建立跳表:

S301、跳表结构的创建：

在内存中申请M个内存块用来存放跳表结构；

然后创建一个具有行数为MAXLEVEL的跳表结构，该跳表结构的第一列中设置MAXLEVEL个头节点，最后一列设置有MAXLEVEL个空节点；其中，跳表行数MAXLEVEL取为lg(N)，N为步骤2中遍历得到文件的个数；

A、令跳表结构中每个节点均采用虚拟指针，每个节点的虚拟指针包括后向指针和下向指针，其中任一个节点的后向指针指向跳表结构中该节点所在行向后相邻的节点，任一个节点的下向指针指向跳表结构中该节点所在列向下相邻的节点；

根据插入节点后的跳表结构，更新每个节点的虚拟指针；

G、将跳表存入磁盘文件slsave.bin中；

步骤4、在跳表中查找磁盘文件：

根据查找节点的描述信息到磁盘文件currentdir.dat和memsave.bin中调取该文件；

当删除文件时，采用内存压缩形式，当所述位图表示0X00000000时，将所述内存块进行释放；

当进行快速恢复时，从第二次文件检索开始，每一次文件检索程序前，先执行所述步骤1，然后从磁盘文件memsave.bin中恢复步骤2要得到的数据，再从slsave.bin中恢复步骤3需要的数据，最后执行步骤4。