搜索引擎之索引建立原理 -

linkyou66

浏览: 235176 次
性别:
来自: 杭州

最近访客更多访客>>

wkq777

hejianhua66

dagf113225

amadis_chen

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (266)

社区版块

存档分类

搜索引擎之索引建立原理

我们假设有这样一张商业信息数据表，我们用什么样的算法和结构（索引技术）可以快速方便实现搜索功能呢？


<table class="MsoNormalTable" style="margin: auto auto auto 5.4pt; border-collapse: collapse;" border="1" cellspacing="0" cellpadding="0"><tbody>
<tr style="height: 15pt;">
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="36" valign="top">
Sid
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 108pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="144" valign="top">
Subject
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="48" valign="top">
Type
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="48" valign="top">
Price
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="36" valign="top">
id
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="168" valign="top">
Description
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="72" valign="top">
PostTime
</td>
</tr>
<tr style="height: 15pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="36" valign="top">
0
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 108pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="144" valign="top">
Sell apple
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="48" valign="top">
Sale
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="48" valign="top">
50
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="36" valign="top">
101
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="168" valign="top">
We are one of the largest …
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="72" valign="top">
2002-10-02
</td>
</tr>
<tr style="height: 14.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="36" valign="top">
1
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 108pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="144" valign="top">
Buy Digital Camera
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="48" valign="top">
Buy
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="48" valign="top">
200
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="36" valign="top">
102
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="168" valign="top">
Our company mobile-point is situated in the …
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="72" valign="top">
2003-02-10
</td>
</tr>
<tr style="height: 13.5pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="36" valign="top">
2
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 108pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="144" valign="top">
Sell dog shoes
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="48" valign="top">
Sale
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="48" valign="top">
45
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="36" valign="top">
103
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="168" valign="top">
Dog Shoes Model Number: 02GLPS074 Place of …
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="72" valign="top">
2003-12-18
</td>
</tr>
<tr style="height: 17.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="36" valign="top">
3
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 108pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="144" valign="top">
Buy Toys And Jewelry
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="48" valign="top">
Buy
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 36pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="48" valign="top">
1000
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="36" valign="top">
104
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="168" valign="top">
I am interested in items that can be ordered in small …
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="72" valign="top">
2003-08-20
</td>
</tr>
</tbody></table>
（商业信息数据表）
一般我们需要的查询的需求分为下面两类：
a． 希望通过某个关键字找到所需信息（根据关键字来搜索）
b． 希望能够根据type, price, PostTime, id等字段进行检索（单字段信息检索）
1．建立索引 
对于a需求：
我们使用 hashtable来达到快速检索的目的，既将可能用于查询的关键字作为hashtable的key(主键)，跟该key有关的记录信息（我们称为TokenInfo）作为key对应的值。主键key来源于用于关键字查询的字段的文本（这些字段一般都要求是文本类型），一般一段文本可以分解出许多key，我们把分解的过程称为分词，分解出来的key称为Token。每一个Token是用于关键字查询的最小单位。TokenInfo一般会记录该Token的所在的文档ID(Doc Number), 所在文本的位置(Prox)，在文本中出现的次数（Freq），所在的字段等等。详细结构如下：



<table class="MsoNormalTable" style="margin: auto auto auto 5.4pt; width: 576px; border-collapse: collapse;" border="1" cellspacing="0" cellpadding="0"><tbody>
<tr style="height: 15.45pt;">
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; width: 91.35pt; padding-top: 0cm; height: 15.45pt; background-color: transparent;" colspan="2" width="122" valign="top">
Token Size
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 34.65pt; padding-top: 0cm; border-bottom: #ece9d8; height: 15.45pt; background-color: transparent;" rowspan="2" width="46" valign="top">

</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 45pt; padding-top: 0cm; height: 15.45pt; background-color: transparent;" width="60" valign="top">
Token
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 15.45pt; background-color: transparent;" colspan="2" width="72" valign="top">
DocFreq
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 81pt; padding-top: 0cm; height: 15.45pt; background-color: transparent;" colspan="2" width="108" valign="top">
DocList(链表)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 126.2pt; padding-top: 0cm; height: 15.45pt; background-color: transparent;" colspan="2" width="168" valign="top">
ProxDelta(文件位置指针)
</td>
</tr>
<tr style="height: 12pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 36.95pt; padding-top: 0cm; height: 12pt; background-color: transparent;" width="49" valign="top">
Token
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54.4pt; padding-top: 0cm; height: 12pt; background-color: transparent;" width="73" valign="top">
TokenInfo
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 306.2pt; padding-top: 0cm; height: 12pt; background-color: transparent;" colspan="7" width="408" valign="top">
（TokenInfo）
</td>
</tr>
<tr style="height: 18.75pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 36.95pt; padding-top: 0cm; height: 18.75pt; background-color: transparent;" width="49" valign="top">
Token
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54.4pt; padding-top: 0cm; height: 18.75pt; background-color: transparent;" width="73" valign="top">
TokenInfo
</td>
<td style="background-color: transparent; border: #ece9d8; padding: 0cm;" colspan="8" width="454">

</td>
</tr>
<tr style="height: 14.8pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 36.95pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" width="49" valign="top">
…
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54.4pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" width="73" valign="top">
… …
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 34.65pt; padding-top: 0cm; border-bottom: #ece9d8; height: 14.8pt; background-color: transparent;" rowspan="2" width="46" valign="top">

</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 72pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" colspan="2" width="96" valign="top">
Doc Number
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 63pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" colspan="2" width="84" valign="top">
Token Freq
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" colspan="2" width="72" valign="top">
Field Bit
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 117.2pt; padding-top: 0cm; height: 14.8pt; background-color: transparent;" width="156" valign="top">
下一个节点内容 …
</td>
</tr>
<tr style="height: 15pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 36.95pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="49" valign="top">
Token
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54.4pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="73" valign="top">
TokenInfo
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 306.2pt; padding-top: 0cm; height: 15pt; background-color: transparent;" colspan="7" width="408" valign="top">
(DocList链表)
</td>
</tr>
<tr height="0">
<td style="background-color: transparent; border: #ece9d8;" width="49"></td>
<td style="background-color: transparent; border: #ece9d8;" width="73"></td>
<td style="background-color: transparent; border: #ece9d8;" width="46"></td>
<td style="background-color: transparent; border: #ece9d8;" width="60"></td>
<td style="background-color: transparent; border: #ece9d8;" width="36"></td>
<td style="background-color: transparent; border: #ece9d8;" width="36"></td>
<td style="background-color: transparent; border: #ece9d8;" width="48"></td>
<td style="background-color: transparent; border: #ece9d8;" width="60"></td>
<td style="background-color: transparent; border: #ece9d8;" width="12"></td>
<td style="background-color: transparent; border: #ece9d8;" width="156"></td>
</tr>
</tbody></table>
(Token HashTable)
ProxDelta(文件位置指针)


<table class="MsoNormalTable" style="margin: auto auto auto 5.4pt; width: 576px; border-collapse: collapse;" border="1" cellspacing="0" cellpadding="0"><tbody>
<tr style="height: 13.5pt;">
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; width: 27pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="36" valign="top">
N0
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 38.55pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="51" valign="top">
A(0,0)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 43.95pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="59" valign="top">
A(0,1)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 25.5pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="34" valign="top">
…
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 54pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="72" valign="top">
A(0,n0-1)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="36" valign="top">
N1
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 38.55pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="51" valign="top">
A(1,0)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 45pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="60" valign="top">
A(1,1)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 27.75pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="37" valign="top">
…
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 59.7pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="80" valign="top">
A(1,n1-1)
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 45pt; padding-top: 0cm; height: 13.5pt; background-color: transparent;" width="60" valign="top">
… …
</td>
</tr>
<tr style="height: 17.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 189pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" colspan="5" width="252" valign="top">
第1个doc中该key出现的位置情况
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 198pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" colspan="5" width="264" valign="top">
第2个doc中该key出现的位置情况
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 45pt; padding-top: 0cm; height: 17.25pt; background-color: transparent;" width="60" valign="top">
… …
</td>
</tr>
</tbody></table>
(详细的HashTable结构图)
查询的时候我们会用同样的分词算法把用户输入的关键分解为多个Token,每一个Token都去找这个HashTable, 然后将每一个Token查到的结果集进行合并，返回给用户。

对于b需求：
一般字段有下面几种类型：TEXT, STRING, ENUM, RANGE, NUMBER, BIT, DATE等。一般我们是将TEXT, STRING, NUMBER类型的字段采用上述HashTable的方法建立索引，只不过他们的分词方法是不一样的，其中TEXT类型的字段是要进行分词的，STRING类型的字段是不需要分词的，整体作为一个Token，NUMBER类型的字段是将字段转化为数字作为Token，这样可以节省空间；我们将ENUM, RANGE, BIT类型的字段采用BitMap的方法建立索引，下面具体说明BitMap的索引结构（以Type字段为例）：

<div>
<table class="MsoNormalTable" style="margin: auto auto auto 5.4pt; border-collapse: collapse;" border="1" cellspacing="0" cellpadding="0"><tbody>
<tr style="height: 7.2pt;">
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; width: 63pt; padding-top: 0cm; height: 7.2pt; background-color: transparent;" width="84" valign="top">
Type Value
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 225pt; padding-top: 0cm; height: 7.2pt; background-color: transparent;" width="300" valign="top">
Bit Map
</td>
</tr>
<tr style="height: 15.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 63pt; padding-top: 0cm; height: 15.25pt; background-color: transparent;" width="84" valign="top">
Buy
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 225pt; padding-top: 0cm; height: 15.25pt; background-color: transparent;" width="300" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 1010
</td>
</tr>
<tr style="height: 14.75pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 63pt; padding-top: 0cm; height: 14.75pt; background-color: transparent;" width="84" valign="top">
Sale
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 225pt; padding-top: 0cm; height: 14.75pt; background-color: transparent;" width="300" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 0101
</td>
</tr>
<tr style="height: 15.75pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 63pt; padding-top: 0cm; height: 15.75pt; background-color: transparent;" width="84" valign="top">
…
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 225pt; padding-top: 0cm; height: 15.75pt; background-color: transparent;" width="300" valign="top">
… … … …
</td>
</tr>
</tbody></table>
</div>
 ^doc#16 ^doc#1
我们再举另外一个例子（用结构体来表示）：
假定我们有两个enum类型的字段，每一个类型有几个可能的值，共20条记录：
 Field:
 Country - China, Hong Kong, Japan, Korea, USA
 Color - Blue ,Red, White
 Records:
 China-blue, Hong Kong-blue, Japan-red, China-red, China-white,
 0-0 1-0 2-1 0-1 0-2
 USA-red, Korea-white, China-white, China-white, USA-blue,
 4-1 3-2 0-2 0-2 4-0
 China-red, USA-red, USA-blue, Hong Kong-white, Japan-Red,
 0-1 4-1 4-0 1-2 2-1
 China-red, China-Red, China-BLUE, China-white, China-RED,
 0-1 0-1 0-0 0-2 0-1
 这些数据就可以用下面的结构体来表示：
 SEnumDesc {
 iNumOfFields = 2;
 pField[0] = "Country", pField[1] = "Color";
 pValues[0] = {
 iNumOfValues = 5;
 pVal[0] = "china", pVal[1] = "hong kong", pVal[2] = "japan",
 pVal[3] = "korea", pVal[4] = "usa";
 },
 pValues[1] = {
 iNumOfValues = 3;
 pVal[0] = "blue", pVal[1] = "red", pVal[2] = "white";
 };
 iNumOfDocs = 20;
 pBitmap[0] {
 pMap[0][0] = xxxx xxxx xxxx 1111 1000 0101 1001 1001; // china
 pMap[1][0] = xxxx xxxx xxxx 0000 0010 0000 0000 0010; // hong kong
 pMap[2][0] = xxxx xxxx xxxx 0000 0100 0000 0000 0100; // japan
 pMap[3][0] = xxxx xxxx xxxx 0000 0000 0000 0100 0000; // korea
 pMap[4][0] = xxxx xxxx xxxx 0000 0001 1010 0010 0000; // usa
 // ^doc#20 ^doc#1
 }
 pBitmap[1] {
 pMap[0][0] = xxxx xxxx xxxx 0010 0001 0010 0000 0011; // blue
 pMap[1][0] = xxxx xxxx xxxx 1001 1100 1100 0010 1100; // red
 pMap[2][0] = xxxx xxxx xxxx 0100 0010 0001 1101 0000; // white
// ^doc#20 ^doc#1
 }
如果一个字段是Range类型的，或者搜索的时候是要根据一个范围来查找的，比如说price字段，每一条记录都一个价格值，但是搜索的时候我们一般是根据一个价格范围来查找，对于这样的字段我们建立索引的时候也是采用BitMap结构，既先自己定义几个范围，一个记录该字段的值属于哪个范围，我们就将位置上设1。以price字段为例。

<div>
<table class="MsoNormalTable" style="margin: auto auto auto 5.4pt; border-collapse: collapse;" border="1" cellspacing="0" cellpadding="0"><tbody>
<tr style="height: 15pt;">
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; width: 54pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="72" valign="top">
Range
</td>
<td style="padding-right: 5.4pt; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 232.45pt; padding-top: 0cm; height: 15pt; background-color: transparent;" width="310" valign="top">
Bit Map
</td>
</tr>
<tr style="height: 6.65pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 54pt; padding-top: 0cm; height: 6.65pt; background-color: transparent;" width="72" valign="top">
<50
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 232.45pt; padding-top: 0cm; height: 6.65pt; background-color: transparent;" width="310" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 0100
</td>
</tr>
<tr style="height: 13.95pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 54pt; padding-top: 0cm; height: 13.95pt; background-color: transparent;" width="72" valign="top">
[50,100)
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 232.45pt; padding-top: 0cm; height: 13.95pt; background-color: transparent;" width="310" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 0001
</td>
</tr>
<tr style="height: 14.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 54pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="72" valign="top">
[100,500)
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 232.45pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="310" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 0010
</td>
</tr>
<tr style="height: 14.25pt;">
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; width: 54pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="72" valign="top">
>=500
</td>
<td style="padding-right: 5.4pt; border-top: #ece9d8; padding-left: 5.4pt; padding-bottom: 0cm; border-left: #ece9d8; width: 232.45pt; padding-top: 0cm; height: 14.25pt; background-color: transparent;" width="310" valign="top">
… … xxxx xxxx xxxx xxxx 0000 0000 0000 1000
</td>
</tr>
</tbody></table>
</div>
 ^doc#16 ^doc#1
 对于Bit类型的字段同样也是采用BitMap的结构，这里就不在阐述了。BitMap结构的好处是节省空间，结果集合逻辑运算简单快速，但并不是所有Enum类型的字段都采用BitMap结构，当枚举值大于32个的时候，采用BitMap就不方便了，这个时候我们会采用HashTable的结构来建立索引。

分享到：