当前位置:首页 >> 建筑/土木 >>

文件的索引结构2


文件索引结构与倒排表

2007/05/14

本讲主要内容:
? ? ? ?

平衡二叉树 文件的索引结构 倒排表与倒排索引 类型无关的软件平台架构

2

字典的二分查找
?
? ?

二分查找(binary search)


要求:
查找表为有序表,即表中 结点按关键字有序排列,并且采用顺序存储结构。

? 1. 2.

基本思想:
确定搜索区间的中点位置: 然后将待查的key值与range[mid].key比较:若相等, 则查找成功并返回此位置,否则确定新的查找区间, 继续二分查找.

3

动态查找表结构
—— 二叉排序树(又称二叉搜索树)
?

以关键码值为结点的二叉树
?

20

如果任一结点的左子树非空, 则左子树中的所有结点的关键 码都小于根结点的关键码; 如果任一结点的右子树非空, 则右子树中的所有结点的关键 码都大于根结点的关键码。
2 8 6 10 40

?

15 15

30

25

4

二叉排序树的插入与构造
? ?

如果二叉排序树为空,则新结点作为根结点。 如果二叉排序树非空,则将新结点的关键码与根结点 的关键码比较,
?

?

若相等表示该结点已在二叉排序树中;若小于根结点的关键 码,则将新结点插入到根结点的左子树中; 否则,插入到右子树中。

?

子树中的插入过程和树中的插入过程相同,如此进行 下去,直到找到该结点,或者直到左或右子树为空二 叉树,新结点插入成为叶子结点为止。

5

最佳二叉排序树的构造
(1) 先将字典元素关键码排序。 (2) 对每个关键码按二分法在排序关键码序列中 执行检索,将检索中遇到的还未在二叉排序树 中的关键码插入二叉排序树中。 —— 按二分查找中所遇到的节点依次插 入二叉排序树。

6

举例(记录二分查找的过程)
?

对于K={27,73,10,5,18,41,99,51,25},构造最佳二叉排序树 的过程如下:
首先将它们排序为:5,10,18,25,27,41,51,73,99, 然后从空二叉树出发,在排序的关键码序列中用二分法检索5, 检索中遇到的结点为27,10,5,将这三个结点插入二叉排序树。 再检索第二个结点10,遇到的结点为27,10,二叉排序树中已经 有这两个结点。 再检索第三个结点18,…。

? ?

?

?

?

得到的插入次序为27,10,5,18,25,51,41,73,99。

7

静态查找表索引结构

sco re

stude ntID

name

assign ment

finial exam

45 46 47 48 49

23 16 2 29 17

周夏司 李景文 叶佩霖 郭舒文 杜文杰

50 10 50 60 60

39 43 35 51 52

50
51 52 53 55 57 59 61 62

9
3 21 13 4 28 14 27 11

阮萃茵
龙国才 陈俊珊 李欣怡 刘星 郭凌典 李敏妍 唐慰夷 吴宇翔

70
0 45 75 50 25 90 30 0

29
35 45 55 29 48 74 49 47

71
78

10
30

何英华
梁迪欣

0
80

51
69

8

索引
?

?

索引是索引项的集合,一个索引项是由一个结 点的关键码和该结点的存储位置组成的关联。 索引的实质还是字典,而且是元素类型相同的 等长结点的字典。所有关于字典的讨论都适合 于索引;所有字典的实现也可以用来组织索引。

9

文件与索引结构 —— 打开一个文件

10

从文本文件中读入数据集合

11

将数据集转换为记录集

12

通过记录的某一项属性值反过来查找到这个记录的存放地址, 或者记录对应的关键码。我们称这种索引为倒排索引 (inverted index)。

13

倒排索引的建立

14

利用函数指针实现 倒排索引的建立

15

包含数据逻辑层的软件架构
数据源1 数据源2 … 数据源n

数据结构及类型

数据逻辑层
类型化计算 数据对象

数据处理层

XML 文档
+

数据呈现 数据交换

Style sheet

16

动态查找表 —— 平衡二叉排序树
?

以上的“最佳”二叉排序树,不仅构造的时间代价很 大,而且很难动态的保持。通常用于表示一旦构造后 就不改动的静态字典;

?

对于动态字典,为了能够在进行元素的插入和删除操 作时,较快地对二叉排序树进行调整,通常不要求二 叉排序树总是保持“最佳的”检索效率,而是希望达 到一种比较容易调整的“较佳”的状态。

17

平衡二叉排序树,
?

又称AVL树,要求从整体上看,在动态插入或 删除后,每个结点的左右子树能够基本保持平 衡。不会出现过分倾斜的现象,从而使得平均 检索长度保持比较短。 结点右子树高度与左子树高度之差称为该结点 的平衡因子,平衡二叉排序树中每个结点的平 衡因子只能是1、0或-1。

?

18

19

插入的影响
?

在平衡二叉排序树中插入新结点时,如果新结点插入 后不影响其父结点为根的子树高度,则不会破坏整个 二叉排序树的平衡;反之,若父结点为根的子树高度 增加了,则可能引起一连串的反映。 其结果又有两种可能,一种是在其祖先的某一层上不 再影响子二叉排序树的高度,则整个二叉排序树仍然 是平衡的;另一种是在其祖先的某一层上破坏了平衡 的要求,使整个二叉排序树不再是AVL树。

?

20

最小不平衡子树
?

?

处理失去平衡的方法为首先找出最小不平衡子 树(指离插入结点最近,且以平衡因子绝对值 大于1的结点为根的子树), 在保证排序树性质的前提下,调整最小不平衡 子树中各结点的连接关系,以达到新的平衡。

21

22

AVL树调整平衡的原则
?
?

调整不破坏节点间的序关系。 调整不增加子树的高度。

LL型调整 ? 破坏平衡的原因是由于在A的左子女(L)的左子树(L) 中插入新结点,使A的平衡因子由 -1变为 -2而失去平衡。

23

LL-调整规则
?

?

将A的左子女B提升为新二叉树的根;原来的根A连同 其右子树γ向右下旋转成为B的右子树;B的原右子树β 作为A的左子树。 调整后仍保持二叉排序树的性质,而且整个(子)二 叉树的高度与插入前相同,因此不会影响包含它的更 大(子)二叉树的平衡。 -1
4 2 -1 1 7

3

0

24

RR型调整
?

破坏平衡的原因是由于在A的右子女(R)的右子树(R)中 插入结点,使A的平衡因子由1变为2而失去平衡。

?

调整规则:与LL型的对称。将A的右子女B提升为新二 叉树的根;原来的根A连同其左子树向左下旋转成为B
的左子树;B的原左子树作为A的右子树。
4

-1

2 -1

7

8

9

0
25

LR型调整
?

破坏平衡的原因是由于在A的左子女(L)的右子 树(R)中插入结点,使A的平衡因子由-1变为 -2而失去平衡。 若α、β、γ、δ全为空树,C就是新插入的结点, 记为LR(0)。否则,新结点可能插在C的左子树 中,也可能插在C的右子树中,分别记为LR(L) 和LR(R)。

?

26

27

LR-调整规则
?

设C为A的左子女的右子女,将A的孙子结点C提升为新二 叉树的根;原C的父结点B连同其左子树α向左下旋转成为 新根C的左子树,原C的左子树β成为B的右子树;原根A 连同其右子树δ向右下旋转成为新根C的右子树,原C的右 子树γ成为A的左子树。
4

-1
2 0 1

4

-1

2 0 1

7

7

3 2.5

3

LR(L)
3.5

LR(R)

28

RL型调整
?

破坏平衡的原因是由于在A的右子女(R)的左子树(L) 中插入结点,使A的平衡因子由1变为2而失去平衡。 调整规则与LR型的对称。设C为A的右子女的左子 女,将A的孙子结点C提升为新二叉树的根,原来 C的父结点B连同其右子树δ向右下旋转成为新根C 的右子树,C的原右子树γ成为B的左子树;原来的 根A连同其左子树α向左下旋转成为新根C的左子 树,原来C的左子树β成为A的右子树。

?

29

30

调整控制在最小不平衡子树内
?

上述所有的调整操作中,A为根的最小不平 衡子树的高度在插入结点之前和调整之后相 同,对A为根的子树之外的其它结点的平衡 性无影响,调整后二叉排序树成为平衡二叉 排序树。

31

元素的删除
与二叉排序树中的结点删除类似,首先找到被删除的 结点,如果它不是叶结点,也需要根据二叉排序树的 要求转换成一个叶结点的删除。不同之处在于:为了 保持删除后的二叉树是平衡的,必须参考插入时的调 整方案设计删除后调整的算法;仅仅从最小不平衡子 树的调整来看,它与插入时的调整类似,但困难的是: 对最小不平衡子树的调整,可能降低它的高度,所以 又可能产生更大的最小不平衡子树。因此可能需要反 复多次调整。

32

索引文件 —— 多分树
?

如果文件很大,索引顺序文件的索引可以采用多级索 引结构以提高检索的效率。 即为主文件建立了索引之后,又针对本级索引所占的 每一个页块建立一个索引项,用这些索引项构成索引 的索引。如果新建的这一级索引仍然占用多个页块, 则再为它建立索引。这样可以得到一种多级索引结 构——多分树。 如果每个内部结点(根除外)有m个子女,则称为m 分树。

?

?

33

多分树与索引文件
?

?

?

如果文件很大,索引顺序文件的索引可以采用多 级索引结构以提高检索的效率。 即为主文件建立了索引之后,又针对本级索引所 占的每一个页块建立一个索引项,用这些索引项 构成索引的索引。如果新建的这一级索引仍然占 用多个页块,则再为它建立索引。这样可以得到 一种多级索引结构——多分树。 如果每个内部结点(根除外)有m个子女,则称 为m分树。

34

表示方法
?

?

? ?

多分树的每个结点分配一个页块,结点上的信息是许 多二元组(k,p)的序列,它们在结点内按关键码 k的值排序。 第i个二元组中的p是本结点的第i个子结点(页块) 的地址,k是这个子结点上的最小(或者最大)关键 码。 多分树的叶结点就是主文件的最底层索引。 主文件的每个页块可以看成是多分树的外部结点。

35

36

索引检索
要检索一个关键码为K的记录,则读入根结点 的页块,在这个页块上找到最后一个满足k≤ K的索引项(k,p),读入p所指的下一级 索引的页块。这样一级一级地进行,直到读入 主文件页块,在其上查找关键码为k的记录。

37

索引插入
在这种文件上插入记录是不太方便的。为了使主文件 的记录保持关键码递增的次序,需要把插入位置之后 的每个记录向后移动,从而导致增加新的索引项和索 引页块,需要对外存上的页块进行大量的调整。

多分树主要实用于静态的索引顺序文件,对于经常需 要插入和删除的动态索引顺序文件,需要采用动态索 引结构,即下面要讨论的B树和B+树

38

B树
一棵m阶的B树满足下列条件∶ 1,每个结点至多有m棵子树。 2,除根结点外,其它每个分支结点至少有 ?m / 2? 棵子树。

3,根结点至少有两棵子树(除非B树只包含一个结 点)。
4,所有叶结点在同一层上。B树的叶结点可以看成 一种外部结点,不包含任何信息。 5,有j个孩子的非叶结点恰好有j-1个关键码,关键 码按递增次序排列。
39

B树的类型和结点类型定义:
#define m 1024 struct BTNode; typedef struct BTNode * PBTNode;

struct BTNode {
int keyNum; /* 实际关键字个数,keyNum<m */ PBTNode parent; PBTNode *ptr; /* 指向父结点 */ /* 子树指针向量: ptr[0]…ptr[keyNum] */

KeyType *key;
}

/* 关键字向量: key [0]…key [keyNum-1] */

typedef struct BTNode *BTree;

typedef BTree * PBTree;

40

B树的运算
? ? ?

检索 插入 删除

41

检索 ——在B树中检索关键码key的思路
根据要查找的关键码key,在根结点的关键码集 合中进行顺序或二分法检索,若key=ki,则检索 成功;否则,key一定在某ki和ki+1之间,取指针pi 所指结点继续查找,重复上述检索过程,直到检 索成功,或指针pi为空,检索失败。

42

在以下B树中检索关键码为400的结点

43

在B树中插入关键码key的思路
对高度为h的m阶B树,新结点一般是插在第h层。通过检索可 以确定关键码应插入的结点位置。然后分两种情况讨论: 1,若该结点中关键码个数小于m-1,则直接插入即可。 2,若该结点中关键码个数等于m-1,则将引起结点的分裂。 以中间关键码为界将结点一分为二,产生一个新结点,并把 中间关键码插入到父结点(h-1层)中; 重复上述工作,最坏情况一直分裂到根结点,建立一个新的 根结点,整个B树增加一层。

44

?

在以下B树中插入关键码200、460

45

46

47

在B树中删除关键码key的思路

48

7.6.3 B+树
一个m阶的B+树满足下列条件∶ 1、每个结点至多有m棵子树。 2、除根结点外,其它每个分支至少有 ?m / 2? 棵子树 3、非叶结点的根结点至少有两棵子树。 4、叶结点都在同一层中。

49

说明
(1)有j棵子树的结点有j个关键码,它们按照递增 次序排列。

(2) 每个叶结点中至少包含 ?m / 2? 个关键码。所 有主文件记录的索引项都存放在B+树的叶结点中。
(3) 所有分支结点可看成是索引的索引。结点中 仅包含它的各个子结点中最大(或最小)关键码的 分界值及指向子结点的指针。

50

B+树和B树的差异:
(1)B+树有n棵子树的结点中含有n个关键码;而B树 有n棵子树的结点中含有n-1个关键码。 (2)B+树所有的叶子结点中包含了完整的索引的信息, 而B树中非叶结点的关键码与叶结点的关键码均不重 复,它们共同构成全部索引信息。 (3)B+树所有的非叶结点可以看成是高层索引,结点 中仅含有其子树中最大(或最小)关键码.

51

B+树的运算
?

检索 在B+树中检索关键码key的方法与B树的检索 方式相似,但若在分支结点上找到检索的关键 码时,检索并不结束,要继续找到B+树的叶 结点为止。

52

插入
与B树的插入操作相似,总是插在叶结点上。当结 点中原关键码个数等于m时,该结点分裂成两个结 点,分别使关键码个数为 ?(m ? 1) / 2? 和

?(m ? 1) / 2。 ?

删除
仅在叶结点删除关键码。若因删除操作使结点中关 键码数少于 ?m / 2? 时,则从兄弟结点调整或者合并。 合并的过程和B树相似,区别是父结点中作为分界 的关键码,不放入合并后的结点中。
53

B+树在索引顺序文件中的应用
B+树可以表示主文件的密集索引,也可以表示稀疏索引, 以稀疏索引为例: 通常在B+树表示的索引顺序文件中设两个头指针∶一个 指向B+树的根结点,另一个指向主文件中关键码最小 的页块,所有主文件的页块顺序链成单链表。 在索引顺序文件中可以采用两种检索方式∶一种直接从最 小关键码开始顺序检索;另一种从B+树的根结点开始 逐层检索。 当主文件中需要增加或减少一个页块时,只需在B+树中 为之插入或删除一个索引项,问题归结为B+树本身的 运算。
54

55

B+树的主要优点
?

B+树可以比B树更快地实现检索:同样大的字典, 用B+树组织索引的层数比B树的索引层数少。 另外,由于B+树所有的叶子结点中包含了完整的 索引的信息,可以比较方便的表示文件的稀疏索引。 最后,B+树的检索,插入和删除统一在叶结点上 进行,比B树相对简单。

?

?

56

作业:算法设计
?

有重复键值倒排索引的建立、使用(访问)与维 护。假设按特定字段值能访问到记录的id号就算 正确访问到该记录。可以使用网页上提供的 student.txt为例。
?

? ?

数据结构设计。建立算法。插入删除算法。访问算 法。 算法效率分析(最坏情况、平均情况)。 适用范围与应用场景分析。
?

包含对本设计的总体评价。

?

提交:word文档。16号。

57


相关文章:
SQL Server 索引结构及其使用
暂无评价|0人阅读|0次下载|举报文档SQL Server 索引结构及其使用_计算机软件及应用...二、何时使用聚集索引或非聚集索引 下面的表总结了何时使用聚集索引或非聚集索引...
实验2.2 数据表记录的定位、删除与索引
实验2.2 数据表记录的定位、删除与索引_计算机软件及应用_IT/计算机_专业资料。...性别=’女’ 4. 有一个工资表文件, 其表结构及记录如表 2-14 和表 2-...
操作系统课后题答案二
对于索引顺序文件,每个记录分组配置一个索引项,存储开销 为 N ,检索到具有指定关键字的记录,平均需要查找 N /2 次。 8.试说明顺序文件的结构及其优点。 答:第...
第十一章文件答案
(2) 带索引的结构,相应文件为索引文件索引文件包括索引表和数据表,索引表中的索引项 包括数据表中数据的关键字和相应地址,索引表有序,其物理顺序体现了文件的...
实验二答案
用表设计器来为 SB.DBF 建立一个结构复合索引文件,其中包括 3 个索引: (1) 记录以价格降序排列,索引标识为普通索引型。 (2)记录以部门升序排列,部门相同时则...
操作系统第八章 文件复习题(答案)
动态增长的文件物理结构是 ( A ) A.连续分配 B.链接分配 C.索引分配 D.以上都不对 2、 文件系统中若文件的外存分配方式采用连续分配,则文件控制块 ...
操作系统习题(2)
(2)进行优化分布,应如何安排这些记录?计算处理的总时间。 某个文件系统,采用混合索引分配方式为文件分配磁盘空间,FCB 中共有 13 个 地址项,每个盘块的大小为 ...
作业六(文件管理2011)
管理的部分叫做 A、数据库系统 B、文件系统 D、数据存储系统 2.文件系统是指...(不包含文件控制块) (3)某文件 file 有 268 块,请画出该数据块的索引结构...
第六章答案_1
文件系统中若文件的物理结构采用连续结构,则文件控制块(FCB)中有 关文件的物理位置应包括—B— 。(1)首块地址 (2)文件长度(3)索引表地址 A. 只有(3) B....
201309学期操作系统作业2
2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...答案:错误 第 14 题 多重索引结构适合于有大量大文件的系统。 答案:错误 第...
更多相关标签:
文件索引结构 | lucene索引文件结构 | mysql 索引文件 结构 | yii2文件结构 | discuz3.2 文件结构 | struts2文件结构 | ext2文件系统结构 | discuz x3.2 文件结构 |