搜索引擎有一个索引数据库_千万级ＦＴＰ搜索引擎数据库索引的设计方法探讨
时间：2018-12-24 03:22:32 来源：雅意学习网 本文已影响 人 
摘 要： 本文介绍了基于LINUX操作系统的千万级FTP搜索引擎(Sparrow Search)的框架结构，着重探讨了数据库索引的设计方法，针对提高索引检索效率和压缩比率的问题，本文提出了具体方案并给出了实验结果。
关键词：FTP 搜索引擎 数据库 索引
引言
FTP搜索引擎是对因特网上FTP服务器的信息资源进行检索和管理的一类检索系统机制［１］，数据的检索过程并不需要搜索整个因特网，只需处理预先整理好的FTP目录信息数据库。FTP搜索引擎的功能是搜集匿名FTP服务器提供的目录列表，对用户提供文件信息的查询服务［２］。与相对众多的WWW搜索引擎相比，功能强大的FTP搜索器并不常见，由此限制了人们对具有大量信息与资源的FTP站点的访问。实现一个高速、海量、功能强大而又基于Web的FTP搜索引擎将为网络用户提供极大方便［３］。
根据搜索引擎的工作原理，可将搜索引擎的实现过程分为三步：在因特网上抓取FTP目录信息 → 建立索引数据库→在索引数据库中搜索排序［４］。本文着重讨论建立索引数据库过程中索引的设计与实现方案。
1. FTP搜索引擎的框架结构
Sparrow Search采用的是独立型搜索引擎，即拥有自己的索引数据库，检索在本地数据库中进行，并根据数据库的内容提供相关信息或站点链接。图1是FTP搜索引擎的框架结构图。
用户在客户端使用网页浏览器进行数据查询，当用户键入查找关键字并提交时，Web服务器通过调用CGI程序在索引数据库中进行搜索。数据采集机器人(spider)自动提取各个FTP站点的文件和目录信息并按照一定格式和策略进行存储，从而生成索引数据库。
2.数据库索引数据库的设计
FTP搜索引擎数据库索引设计由三部分组成：原始索引、压缩索引、整合索引。
2.1 建立原始索引
建立索引的方法采用倒排表技术，即数据库的索引被设计成基于单字符(汉字)的倒排表的形式，字符种类的个数决定有多少倒排表文件。每个倒排表文件以某个字符(英文字母或汉字)命名，保存的是该字符(英文字母或汉字) 在数据库中每次出现的位置信息，由于有些字符无法在操作系统中作为文件名，如星号、冒号等，Sparrow Search中规定了只有汉字和特定字符，如:0－9、a－z、A－Z可以被索引。虽然在支持中文的LINUX 操作系统上汉字可以作为文件名，但考虑到兼容性问题，没有直接用汉字作为文件名，而是把汉字的16位编码转换成为4位16进制无符号数来作为文件名。这样在不支持汉字的LINUX 操作系统上也能够处理汉字的索引问题。
索引结构如图2所示。每条索引由32位(4字节)构成，其中高24位用于表示该字符所在的记录编号ID，低7位用于表示该字符在记录内的位置偏移量，中间一位暂时保留，以备后用。
当用户检索FTP目录信息时，希望得到一类文件，而不是一种文件。如用户希望查找所有图像文件，需要用户输入图像文件的扩展名并不方便，因此可在服务端对文件进行分类，将FTP中的文件名分为为图像、视频、音乐、文档、程序等，将其分别进行索引，有利于提高检索效率。
大多数FTP服务器上文件名（不含扩展名）或目录名会采用过于简单的字符表示，但用户检索时无法从信息量较小的字符中检索希望得到的信息。如目录结构/office2000/a/b.exe，仅仅对a和b.exe做索引没有太大意义。在Sparrow Search中，除了文件名本身以外，对其若干外层目录名也编上索引。但增加索引量又会使数据库索引文件剧烈增大。经过实验，每增加一层目录名的索引量，索引文件的大小会增加60%甚至更多。Sparrow Searc采用的方法是：一旦发现文件名的长度过短就将其外层目录名编入索引。同样，若外层目录名仍过短，再将其外层目录名编入索引，……极端情况下，对文件的全路径编制索引。
2.2 索引的压缩存储
增加索引的字符数量会使索引文件的大小成比例增加，即便是只对文件名本身索引，海量的原始信息量仍对索引文件的存储空间构成了极大的威胁。经过实验，在不压缩并对文件相邻外层目录编入索引的情况下，1千万条记录所生成的索引文件的大小超过600MB。考虑在数据库中的数据有这样的规律：大量名字相仿的文件记录会集中在一起，因为它们都被放在服务器的同一个目录下，这意味着文件名中字符或汉字会重复编入索引。
对比原有索引结构，可以将高16位相同的索引编在一起，用2个字节保存，称为基底Base；再用2字节保存高16位相同的索引的个数，即偏移总数N；用2个字节保存原索引结构中的后两个字节的内容，即偏移。索引压缩方法示例如图3所示。
假设用四个数字表示索引的四个字节，则存储图3左边的索引信息需要32个字节（8*4Bytes=32Bytes）；用上述压缩算法进行存储则只需要24个字节。
从例中不难看出，当索引文件越大，压缩比就越高。当数据库规模超过万条记录时，压缩比一般就能维持在50%以上，在测试中最高达到60%。这样存储一千万条索引记录需要约300MB空间。
2.3 索引的整合存储
出于对检索性能的考虑，把众多的倒排表索引文件整合成一个大的索引文件，再将这个文件放入内存中，这个过程就是索引的整合存储。
整合索引需要解决两个问题：
（1）怎样在整合后的文件中定位某个倒排表文件。针对该问题可以另外设置一张表格，称为索引表头，索引表头中指明了每个字符或汉字对应的索引文件大小和在整合后的文件中的起始位置即偏移。
（2）如何解决索引表头的存储问题。有三种方法：其一是存放在整合后的索引文件头部，其二是存放在整合后的索引文件尾部，第三是另外单独存放在一个文件中。Sparrow Search采用了第三种方法。
Sparrow Search索引文件的表头实际上是一个数组，长度为64K，每个元素由8个字节组成(即两个无符号长整型数)，前4个字节指出该元素代表的索引文件的大小，后4个字节指出其偏移量。所以索引表头永远是512KB大小。
索引字符或汉字编码(最高16位)被用做下标在数组中索引定位，即把数组当成一个无冲突的哈希（HASH）表。虽然所有字符或汉字不会都被索引并且会造成存储空间浪费，但却可极大地提高索引访问速度。
3. 缓冲区技术
数据库索引生成器包括索引生成、压缩、整合三部分，程序对于磁盘操作全部采用“预读取+延迟写”的策略，即在程序中开辟读、写缓冲区。缓冲区一旦发生欠载，立即读盘；发生过载，立即写盘。这使得整个数据库的建库、压缩及整合过程的速度比直接写盘的策略提高了几十倍：在未采用缓冲区技术以前，处理7万条记录就要耗费1分钟20秒以上，而采用缓冲区技术以后，7万条记录的处理时间小于3秒钟。
4. 结束语
本文介绍了Sparrow Search引擎数据库索引的生成方法，讨论了遇到的各种问题，并给出了解决方法和实现方式。Sparrow Search已在我校校园网上使用，搜索速度快，准确率较高，范围较广，既方便了校园中广大用户的检索，又节省了费用，是广大师生较喜爱的一种引擎。
参考文献：
［１］印鉴，邹胜.一种分布式搜索引擎设计.计算机科学，2001，28(10):74-77.
［２］陈华，王继民， 韩近强等.互联网上FTP文件的分布特征及启示.计算机工程与应用，2004，1:129-137.
［３］陈华，罗昶，王建勇等.基于Web的百万级FTP搜索引擎的设计与实现. 计算机应用，2000，20(9):68-71.
［４］沈贺丹，潘亚楠，邵良杉.关于搜索引擎的研究综述.计算机技术与发展， 2006，16(4):147-149，152.
