狠狠撸

LOGO
Index （索引）
邬勇 18/10/2010

内容
索引介绍与用途1
各种索引结构2
Lemur 中的索引结构3
所看论文和以后的工作方向4
相关问题5

1. 索引介绍与用途
? 索引 (index) 最早出现在在文献系统中，从这个意义上讲，索引是
指文献集合中包含的事项或从文献集合中引出的概念的一种系统指
南。这些事项或引出的概念是由按已知的或已说明了的可检顺序排
列的款目表达出来的。 ( 如书中的目录就是一种索引 )
? 数据库检索中建立索引所需要的信息都是结构化数据 ( 数据表 ) ，常采
用 B+ 树结构。
? 在信息检索中的索引不同于数据库中的索引，因为建立索引所需的信息
是无结构或者是半结构数据 ( 文档信息 ) ，常采用倒排索引结构
(inverted index) 。但是他们的作用相同。
? 索引的研究和实现主要目标是减少外存存取次数，使得在大数据
集中定位到小数据集就能检索到所需要的信息，从而加快查找检
索。

数据库中的索引简单示例
最
大
关
键
字
物
理
块
号
48 2
50 3
98 4
最大关键字物理块号
17 11
38 12
46 13
关键字物理记录号
02 104
05 103
17 110
29 101
31 108
38 105
43 109
。。
48 112
物理记录号职工号姓名职务其他
101 29 张三程序员。
103 05 李四维修员。
104 02 王五程序员。
105 38 刘七打字员。
108 31 。。。
109 43 。。。
110 17 。。。
112 48 。。。
。。。。。
。。。
。。。
。。。
查找以职工号为关键字，职工号为 38 的记录。
查找表
查找表
索引表
结构数据文件（职工表）

信息检索中的倒排索引简单示例
I did enact Julius
Caesar I was killed
i' the Capitol;
Brutus killed me.
Doc 1
So let it be with
Caesar. The noble
Brutus hath told you
Caesar was ambitious
Doc 2
Term Doc #
I 1
did 1
enact 1
julius 1
caesar 1
I 1
was 1
killed 1
i' 1
the 1
capitol 1
brutus 1
killed 1
me 1
so 2
let 2
it 2
be 2
with 2
caesar 2
the 2
noble 2
brutus 2
hath 2
told 2
you 2
caesar 2
was 2
ambitious 2
Term Doc #
ambitious 2
be 2
brutus 1
brutus 2
capitol 1
caesar 1
caesar 2
caesar 2
did 1
enact 1
hath 1
I 1
I 1
i' 1
it 2
julius 1
killed 1
killed 1
let 2
me 1
noble 2
so 2
the 1
the 2
told 2
you 2
was 1
was 2
with 2
Caesar
Query 1
简单介绍一个单词查询的过程：
如果进行短语查询，需要位置信息。
字典文件：二分查找或 B 树索
引

2. 各种索引结构
?顺序索引：顺序查找，二分查找，分块查找
?Hash 索引
?树索引
?倒排索引

顺序索引
? 顺序查找：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给
定值 K 相比较。若当前扫描到的结点关键字与 K 相等，则查找成功；若扫描结
束后，仍未找到关键字等于 K 的结点，则查找失败。顺序查找方法既适用于线
性表的顺序存储结构，也适用于线性表的链式存储结构 ( 使用单链表作存储结构
时，扫描必须从第一个结点开始 )
? 二分查找：对一有序表，首先确定该表区间中的中点位置，然后将待查的 K 值
与中点值比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，
继续二分查找。 ( 只适应于有序表，且限于顺序存储结构 )
? 分块查找：分块查找是一种介于顺序查找和二分查找之间的查找方法。首先查找
索引表，索引表是有序表，索引表的查找可以采用二分或者顺序查找；然后在确
定的块中进行顺序查找。

Hash 索引
? HASH 索引采用散列的方法，散列方法不同于顺序查找、二分查找、
二叉排序树及 B 树上的查找。它不以关键字的比较为基本操作，采用
直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字
，查找的期望时间为 O(1) 。
? 在 HASH 索引中有一个哈希函数，它以查找键为参数计算出一个介于
0 到 n-1 的整数，其中 n 是桶的数目。桶数组，即一个序号从 0 到 n-
1 的数组中包含 n 个链表的头，每一个对应于数组中的一个桶。如果
记录的查找键为 K ，那么通过将该记录链接到桶号为 h(K) 的桶列表
中来存储它，其中 h 是哈希函数。常用的哈希函数产生方法有平方取
中法、除余法、相乘取整法、随机数法和直接定址法。
? 避免冲突的方法，设计理想的哈希函数，但是不能避免冲突，常处理
冲突的方法是开放定址法和链地址法。

Hash 索引应用
? 简单的应用：统计一个文件中单词出现
的次数，并返回出现频率最多的前 20
个单词。（理想情况下，设计一个不产
生冲突的哈希函数，每个桶中存放一个
单词信息）
? 直接存取文件（散列文件）：根据文件
中关键字的特点设计一种哈希函数和处
理冲突的方法将记录散列到存储设备上。
处理冲突的方法主要采用链地址法。
（这里的桶是磁盘上若干个记录组成的
一个存储单元）
? 示例中有 18 个记录，桶的容量为 3 ，
桶数为 7 ，哈希函数 H(key)=key MOD
7 。

树索引
?二叉排序树 (BST)
?平衡二叉树 (AVL 树 )
?B~ 树
?B+ 树
?其他树结构（ B 树的变型，应用在不同的场合，
如：前缀 B+ 树，位树， R 树， 2-4 树）

二叉排序树 (BST)
?二叉排序树的性质如下：
(1) 若它的左子树不空，则左子树上所有结点的
值均小于它的根结点的值
(2) 若它的右子树不空，则右子树上所有结点的
值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树
?缺点：同样一组数据集合，不同的添加顺序会导
致查找树的结构完全不一样，直接影响了查找效
率 , 时间复杂度为 O(N) 。（可由平衡二叉树
(AVL 树 ) 解决）

平衡二叉树（ AVL 树）
?平衡二叉查找树，又称 AVL 树。它除了具备
二叉查找树的基本特征之外，还具有一个非常重
要的特点：它的左子树和右子树都是平衡二叉树
，且左子树和右子树的深度之差的绝对值（平衡
因子）不超过 1 。也就是说 AVL 树每个节点的
平衡因子只可能是 -1 、 0 和 1 （左子树高度减去
右子树高度）。
?缺点：
? 在大数据量 ( 几 G) 查找环境下，数据是存储在硬盘中
，存在过多的硬盘 I/O 操作 ( 块是操作的基本单位 ) ，
降低了检索效率。 ( 可由平衡多路查找树（ B~ 树）
解决 )

B~ 树
? B~ 树又叫平衡多路查找树。
一棵 m 阶的 B~ 树 (m 叉树 ) 的特性如下：
1) 树中每个结点至多有 m 个孩子；
2) 除根结点和叶子结点外，其它每个结点至少有 [m/2] 个孩子；
3) 若根结点不是叶子结点，则至少有 2 个孩子；
4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
( 可以看做是外部接点或查询失败的接点，实际上这些结点不存在
，指向这些结点的指针都为 null) ；
5) 每个非终端结点中包含有 n 个关键字信息：
(n ， P0 ， K1 ， P1 ， K2 ， P2 ， ...... ， Kn ， Pn) 。其中，
a) Ki (i=1...n) 为关键字，且关键字按顺序排序 Ki < K(i+1) 。
b) Pi 为指向子树根的接点，且指针 P(i-1) 指向子树中所有结点
的关键字均小于 Ki ，但都大于 K(i-1) 。
c) 关键字的个数 n 必须满足：? [m/2]-1 <= n <= m-1

B~ 树查找过程
????? 介绍查找文件 29 的过程
：
Struct BTNode{
/* 文件数 */
int file_num;
/* 文件名 (key)*/
char * file_name[max_file_num];
/* 指向子节点的指针 */
BTNode * BTptr[max_file_num+1];
/* 文件在硬盘中的存储位置 */
FILE_HARD_ADDR offset[max_file_num];
}

B+ 树
? B+ 树：是应文件系统所需而产生的一种 B~ 树的变形
树。
一棵 m 阶的 B+ 树和 m 阶的 B~ 树的差异在于：
1. 有 n 棵子树的结点中含有 n 个关键字；? (B~ 树是 n 棵子树有 n-1 个关键字 )
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的
指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B~ 树的叶子
节点并没有包括全部需要查找的信息 )
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大
（或最小）关键字。 (B~ 树的非终节点也包含需要查找的有效信息 )

B+ 树的优势
? 为什么说 B+ 树比 B~ 树更适合实际应用中操作系统的文件索引和数据库
索引？
? B+ 树的磁盘读写代价更低
B+ 树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B~
树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能
容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。
相对来说 IO 读写次数也就降低了。
? 举个例子，假设磁盘中的一个盘块容纳 16bytes ，而一个关键字 2bytes ，一个
关键字具体信息指针 2bytes 。一棵 9 阶 B~ 树 ( 一个结点最多 8 个关键字 ) 的
内部结点需要 2 个盘快。而 B+ 树内部结点只需要 1 个盘快。当需要把内部结
点读入内存中的时候， B~ 树就比 B+ 数多一次盘块查找时间 ( 在磁盘中就是盘
片旋转的时间 ) 。
? B+ 树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索
引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字
查询的路径长度相同，导致每一个数据的查询效率相当。

B+ 树的应用
?VSAM( 虚拟存储存取方法 ) 文件
来源论文 the ubiquitous B tree 作者： D COMER - 1979

倒排索引 (inverted index)
倒排索引 (Inverted index) ，也常被称为反向索引、置入
档案或反向档案，是一种索引方法，被用来存储在全文
搜索下某个单词在一个文档或者一组文档中的存储位置的
映射。它是文档检索系统中最常用的数据结构。
有两种不同的反向索引形式：
文档水平 (Document-level) 反向索引（或者反向档案
索引）包含每个引用单词的文档的列表。
单词水平 (word-level) 反向索引（或者完全反向索
引）又包含每个单词在一个文档中的位置。
后者的形式提供了更多的兼容性（比如短语搜索），
但是需要更多的时间和空间来创建。

倒排索引 (inverted index) 结构
? 倒排索引由字典文件 (dictionary) 和记录文件 (postings file) 两部分组成。
? 字典 (dictionary) 主要是由 term(term ID), 包含该 term 的文档数目 ft ，以及
指向该记录表 (postings list) 的指针组成。
dictionary: <term,ft,pointer> [postings list]
? 记录 (posting) 主要是记录 term 所在的文档 (docID) ， term 在文档中出现
的次数，以及在文档中的位置，文档长度等信息。
posting: <docID, fd,t,<position1,… positionfd,t>>
下图是简单的倒排索引结构例子 :

Lemur 中的索引结构
? Lemur 中的的索引结构主要目的是方便检索模型中查询和
文档相似度的计算，即 score( 分数 ) 的计算。
? Lemur 中分 2 种索引结构： IndriIndex ， KeyfileIncindex
? Lemur(version4.9) 中的 (keyfileIncindex) 索引文件：
1. Keyfile 文件类型 ( 采用 B 树结构 )
*.did, keyfile 文件类型，保存 documentName->documentID 的映射。
*.didstr, keyfile 文件类型，保存 documentID->documentName 的映射。
*.tid, keyfile 文件类型，保存 termName->termID 的映射。
*.tidstr, keyfile 文件类型，保存 termID->termName 的映射。
*.invlookup, keyfile 文件类型，保存 termID -> TermData 的映射。
(TermData 包括 segment 编号，长度， termID 在 *.ivlN$i 文件中的偏移量等 )
2. *.ivl(firstmergesegment)$i 文件存储 term 对应的文档列表 ( 倒排索
引 ) 。 ( 由 *.ivlN$i(segment) 文件合并而成， N 代表 segment 的数
目， i 代表 segment 编号 , 并且 firstmergesegment 为 0) 。
3. *.dt 文件存储文档对应的 term 列表 ( 前向索引 ) 。
4. *.dtlookup 文件存储文档记录 (record) 信息 (docID 在 *.dt 文件中的偏
移量，文档长度等）

所看论文和以后的工作方向
?所看论文：
? the ubiquitous Btree
-Douglas Comer 1979
? 一高效的倒排索引存种储结构
- 邓攀，刘功申 2008.08
? 一适用于的索引文件种汉语结构
- 王丫蔡建山唐勇 2007.07
? 高效的随机分倒排文件自索引技访问块术 (reading)
- 刘小珠彭智勇陈旭 2010.06
?以后的工作方向：
? 分析 Lemur 中对 B+ 树索引结构的具体操作。
? 查看嵌入式存储中的索引结构论文 (B+ 树结构的变型 ) 。
? 挑战性问题：考虑索引结构的空间效率和时间效率 ( 占用空间少
( 压缩编码 ) 并且提高检索效率 ( 索引结构 )) 。

相关问题
1
对于索引结构研究
的论文相对较少。
是否对其他开源平
台的索引结构进行
研究。
如 :Lucene 。
2
是否针对那种存储
器进行索引结构的
研究（如 FLASH
闪存 ,SDRAM( 同
步动态随机存储
器 ) ）
Another question?
thinking!
3

狠狠撸

an intorducation of Index

More Related Content

an intorducation of Index

Editor's Notes