索引技术-数据结构与算法-课件-北京工业大学-11

以人工或者自动的方式从记录中抽取关键词
第三步，建立正文倒排表、倒排文件
得到各个关键词的集合 对于每一个关键词得到其倒排表 然后把所有的倒排表存入文件
37 38
对关键词的检索过程
第一步，在倒排文件中检索关键词。 第二步，如果找到了关键词，就获取了文 件中对应的倒排表及倒排表中的记录。 通常使用另一个索引结构（字典）进一步 对关键词表进行有序索引。
可以对每一个字符建立索引，从而 使查询词不再限于关键词 需要更大的空间
34
倒排文件的全文本索引
词索引使用最广泛 一个已经排过序的关键词列表
其中每个关键词指向倒排表，
指向该关键词出现的文档集合 以及具体位置
35
36
6
2011/12/25
简化的正文倒排文件
建立正文倒排文件
第一步，对文档集中的所有文件进行分割处理， 把正文分成多条记录文档。 第二步，给每条记录赋一组关键词。
30
5
2011/12/25
10.3.2 对正文文件的倒排
优点：能够对于基于属性的检索进行
较高效率的处理 缺点： 花费了保存倒排表的存储代价 降低了更新运算的效率 正文索引(Text Indexing)处理的就 是“建立一个数据结构以提供对文本 内容的快速检索”。 方法
词索引(word index) 全文索引(full-text index)
基本概念——稀疏索引
对一组记录建立一个索引项，这种索引称 之为稀疏索引 适用场合：记录在磁盘中按照关键码的顺 序存放；可以把记录分成多个组（块） 稀疏索引的索引项指针指向这一组记录在 磁盘中的起始位置
7 8
11.1 线性索引
基本概念 线性索引的优点 线性索引的问题
线性索引文件的基本概念
二级线性索引检索
在检索时，线性索引文件并不被读入内 存，被读入内存的是二级线性索引文件。 由于二级索引往往存储内存，通常只需 要访问两次磁盘即可：一次读入线性索 引文件，一次读入数据库记录。
15 16
例如，检索关键码为2555的记录 首先在内存中的二级线性索引文件中找到关键码 的值小于等于2555的最大关键码所在的记录—关 键码为2003的记录 根据记录中的指针找到对应的线性索引文件的磁 盘块，并把该块读入内存 按照二分法对该块进行检索，找到所需要的记录 在磁盘上的位置 最后把所需记录读入，完成检索操作
43 44
B树的结点结构
B树的一个包含j个关键码， j+1个指针的结点的 一般形式为：
B树的查找
读入根结点，在根结点所包含的关键码K1，…，Kj 中查找给定的关键码值(当结点包含的关键码不多时， 用顺序检索；当结点包含的关键码数目较多时，用 二分检索)， 找到则检索成功。
其中Ki是关键码值，K1<K2<…<Kj， Pi指向包括Ki～Ki+1之间的关键码子树的指针。
(DEPT=“Toy”AND(AGE≥50 OR SAL≥100))
与80之间的倒排表，每个倒排表中含有一
个指针集合。 对这些集合进行并的运算，其结果集合中 包含的指针所指的各记录即为所求。
29
先采用类似（1）、（2）的方法，分别找 出满足条件DEPT=“Toy”，AGE≥50和 SAL≥100的指针集合，然后对后两个指针 集合求并，并且将结果集合与第一个指针 集合求交，最后的结果集合中包含的指针 所指的各记录即为所求。
2011/12/25
第11章 索引技术
11.1 线性索引 11.2 静态索引 11.3 倒排索引 11.4 动态索引 11.5 位索引技术 11.6 红黑树
1
基本概念——输入顺序文件
所谓输入顺序文件是指按照记录进入 系统的顺序存储记录。它的特点是： 输入顺序文件的结构相当于一个磁盘 中未排序的线性表，因此不支持高效 率的检索。
11.2 静态索引
索引结构在文件创建、初始装入记录时 生成 一旦生成就固定下来，在系统运行(例 如插入和删除记录)过程中索引结构并 不改变 只有文件再组织时才允许改变索引结构
17
18
3
2011/12/25
多分树
组织索引一般不用二叉树而采用多分树 大大减少访问外存的次数
如果访问叶结点 查找二叉树需要访 问6次外存 查找多分树需要访 问2次外存
13
二级线性索引
例如，磁盘块的大小是1024字节，每个 关键码／指针记录需要8个字节，则每磁 盘块可以存储128条这样的记录。 假设线性文件索引中包含10000条记录， 该线性索引占用79个磁盘块，二级线性 索引文件中有79项记录。
14
二级线性索引的实例
关键码与磁盘块中第一条记录的关键码的值相同 指针指向相应磁盘块的起始位置
5
索引文件并不需要重新排列记录在磁盘 中的顺序（不用重排主文件） 一个数据库可能有多个索引文件 每个索引文件往往支持一个关键码 可以通过索引文件高效地访问记录中这 个关键码值
6
1
2011/12/25
基本概念——稠密索引
对每一个记录建立一个索引项，这样 建立的索引被称为稠密索引 适用场合：数据库文件中的记录不按 照关键码的顺序排列时（例如，按照 加入的顺序排列）
23 24
4
2011/12/25
倒排表 倒排表是基于属性的倒排。在保留原 表的同时，对感兴趣的（即可以用来 作为检索参数的）每个属性的可能取 值都建立一个倒排表，存放与此属性 相对应的所有关键码值。
索引项
一个具体的索引值 一组指针（例如记录的主码）
这些指针分别指向属性项含有具体值的记录
一个倒排表就是一个索引项 倒排文件是倒排表组成的索引文件
对于连续型的索引，往往用B树
22
11.3.1 基于属性的检索
在某百货公司的职工文件中，有如下的记录格式： (EMP#，NAME，DEPT，AGE，SAL) 其含义为职工号，姓名，所在部门，年龄，工资。
查询
对这样的职工文件进行下列类型的查询： （1）简单查询。例如：列出玩具部的所有职工 记录 （2）范围查询。例如：列出工资在40元和80元 之间(即40≤SAL≤80)的所有职工记录 （3）逻辑查询。例如：列出玩具部中年龄在 50岁以上或者工资在100元以上的职工记录 (DEPT=“Toy”AND(AGE≥50 OR SAL≥100))
31 32
词索引
基本思想： 把正文看作由符号和词组成的集合，从正文 中抽取关键词，然后用这些关键词组成一些 适合快速检索的数据结构。 适用于多种文本类型，特别是可以容易解析 成一组词的集合的文本。
适用于英文 不适用于中文等东方文字
33
全文索引
基本思想：
把正文看作一个长的字符串 在数据结构中记录子串的开始位置 查询可以针对正文中的任何子串
“索引区”
多分树的非叶结点区域 存放各子树结点中的最大(或最小)的关键码 如果插入新纪录的结点已满，则将溢出的记录存 放到另开辟的溢出区，而不改变索引的结构
记录送入溢出区的两种方式
保持顺序，把最后一个记录送往溢出区 不保持顺序，把新插入的记录送入溢出区
21
这种属性往往是离散型的
多分树特点
结点更大
以更少的外存访问次数来完成查找 需要较大的缓冲区 读入一个结点也需较多时间
一个结点最好能放在一个磁盘块中
19
20
“数据基本区”
多分树的叶结点区域，用于存放数据记录
11.3 倒排索引
倒排索引—按属性值建立索引
（属性值，具有该属性值的各记录的地 址列表） 不是根据关键码来确定属性值，而是根 据属性值来确定记录的位置，因而称为 倒排索引(inverted index)
3
基本概念——索引
索引( indexing )是把一个关键码与 它对应的数据记录的位置关联起来的 过程。索引技术是组织大型数据库的 一种重要技术。由于数据库组织将大 量的记录存储在外存上，所以高效率 的检索和有效的插入、更新、删除十 分关键。
4
基本概念——索引文件
索引文件(index file)是用于记录这 种联系（关键码与它对应的数据记录 的位置）的文件组织结构。 索引文件的记录 （关键码/指针）对 将每个关键码和一个指针关联 指针指向主要数据库文件（也称为 “主文件”）中的完整记录
41
Байду номын сангаас
42
7
2011/12/25
11.4.1 B 树
B树(Balanced Tree)是一种平衡的多分树。 定义：一个 m 阶的 B 树满足下列条件： (1) 每个结点至多有m个子结点；
m (2) 除根结点和叶结点外，其它每个结点至少有 2
个子结点； (3) 如果根结点不是叶子结点，至少有两个子结点； (4) 所有的叶结点在同一层； (5) 有k个子结点的非根结点恰好包含k-1个关键码。 3阶B树
线性索引(linear index)的索引文件被组织成一 组简单的关键码(key)/指针(pointer)对的序列。 线性索引文件按照关键码的顺序进行排序；文件 中的指针指向存储在磁盘上的文件记录起始位置 或者主索引中主码的起始位置。
二级线性索引
9
10
根据线性索引的文件大小和内存的空间 限制，可以将索引文件存储在内存中， 这样可以大大提高检索速度；也可以存 储在磁盘中。 优点： 可以便捷地访问变长记录； 可以进行高效检索与随机访问 可以进行顺序处理
11
线性索引存在的问题
线性索引太大，很难存储在内存中
在一次检索过程中有可能多次访问磁盘， 从而影响检索的效率 解决办法：使用二级线性索引
在数据库中插入或者删除记录时需要
更新线性索引
12
2
2011/12/25