Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux集群 > Architecture > » 正文

思想行动之Tips提示框引擎的索引结构

来源: JJ8582 分享至:

摘要

       对于一个轻量级的引擎来说,索引结构直接决定了其性能的好坏,最近的工作中一直接触到本地搜索,参考一些关于Lucene的思想。本文将陈述几种提示框引擎的索引结构,(下面的都用Tips来取代提示框引擎)只为抛砖引玉,未经验证。欢迎大家拍砖!鉴于Tips返回结果的特殊性:一般只需返回十个结果、因为每敲入一个字即是对引擎的一次请求、用户对引擎的请求十分频繁对性能要求十分的高对性能要求十分的高。因此,文中所述的一些粗略的想法只是针对Tips来开展。

一、暂且叫词倒排索引结构

       这种结构怎么来描述呢?简单来讲就是一个词对应一系列的结果(倒排索引这个东西是讲烂了的)。不妨定义如下:

       [Word]-->[NUM] [WORDID1] [WORDID2] [WORDID3]...

       Word代表是用户输入的词条、NUM是该词条指向的结果数(最多10条)、WORDID1...WORDID2等是结果的ID编号、或者直接是WORD的偏移(这里就假设为编号吧)。eg:[有限]-->[3] [4] [6] [7]。接着找到编号为4、6、7的结果词条输出即可(这里还得2分查找)。这样的时间效率是不是可以是O(LogN)。如果是WORD的偏移位置的话,那么就是O(1)了,数据量不大的时候这个是性能是差不多的。接下来,就会有问题了。诸如此样的索引结构,那索引文件得多大?能行吗?好,我们来分析之:我们假设总共有词条数为N,词条的平均长度为M。

       可以粗略估算一下:N个词条,平均长度为M的话,那么Word的最大个数就可以知道是 N*M,后面的索引单元是多少?我觉得也是N*M就够了。所以总的文件大小是:

SUM <= (sizeof WORD + sizeof num ) * ( N * M ) + sizeof WORDID * N * M;这个多大呢?我们令N=200w,M=5。最大的长度为16个字节。那么SUM <= 240MB。

二、树型结构

      未完,待续!有事,先发表。下次补上二、三。




Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史