数据结构第十章 课件

《数据结构第十章 课件》由会员分享，可在线阅读，更多相关《数据结构第十章 课件（161页珍藏版）》请在金锄头文库上搜索。

1、静态索引结构 动态索引结构 散列 可扩充散列,第十章 索引与散列,静态索引结构,示例：有一个存放职工信息的数据表, 每一 个职工对象有近 1k 字节的信息, 正好占据一 个页块的存储空间。,当数据对象个数 n 很大时, 如果用无序表形式的静态搜索结构存储, 采用顺序搜索, 则搜索效率极低。如果采用有序表存储形式的静态搜索结构, 则插入新记录进行排序, 时间开销也很可观。这时可采用索引方法来实现存储和搜索。,线性索引 (Linear Index List),100 140 180 220 260 300 340 380,key addr 03 180 08 140 17 340 24 260 4

2、7 300 51 380 83 100 95 220,职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 08 李斯 男 教师 已婚 . 03 王鲁 男 教务员 已婚 . 95 刘琪 女 实验员 未婚 . 24 岳跋 男 教师 已婚 . 47 周斌 男 教师 已婚 . 17 胡江 男 实验员 未婚 . 51 林青 女 教师 未婚 .,索引表,数据表,假设内存工作区仅能容纳 64k 字节的数据, 在某一时刻内存最多可容纳 64 个对象以供搜索。 如果对象总数有 14400 个, 不可能把所有对象的数据一次都读入内存。无论是顺序搜索或折半搜索, 都需要多次读取外存记录。 如果在索引表中每一

3、个索引项占4个字节, 每个索引项索引一个职工对象, 则 14400 个索引项需要 56.25k 字节, 在内存中可以容纳所有的索引项。,这样只需从外存中把索引表读入内存, 经过搜索索引后确定了职工对象的存储地址, 再经过 1 次读取对象操作就可以完成搜索。 稠密索引：一个索引项对应数据表中一个对象的索引结构。当对象在外存中按加入顺序存放而不是按关键码有序存放时必须采用稠密索引结构，这时的索引结构叫做索引非顺序结构。 稀疏索引：当对象在外存中有序存放时，可以把所有 n 个对象分为 b 个子表(块)存放，一个索引项对应数据表中一组对象(子表)。,在子表中, 所有对象可能按关键码有序地存放, 也可能

4、无序地存放。但所有这些子表必须分块有序, 后一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码。它们都存放在数据区中。 另外建立一个索引表。索引表中每一表目叫做索引项，它记录了子表中最大关键码max _key以及该子表在数据区中的起始位置obj _ addr。 第 i 个索引项是第 i 个子表的索引项, i = 0, 1, , n-1。这样的索引结构叫做索引顺序结构。,对索引顺序结构进行搜索时，一般分为两级搜索: 先在索引表 ID 中搜索给定值 K, 确定满足 IDi-1.max_key K IDi.max_key,22 12 13 30 29 33,36 42 44 48 39 4

5、0,60 74 56 79 80 66,92 82 88 98 94,子表1,子表2,子表3,子表4,数据区,33 48 80 98,索引表,1 2 3 4,max_ max_ key addr,的 i 值, 即待查对象可能在的子表的序号。 然后再在第 i 个子表中按给定值搜索要求的对象。 索引表是按max_key有序的, 且长度也不大,可以折半搜索，也可以顺序搜索。 各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索; 如果不是按对象关键码有序, 只能顺序搜索。,索引顺序搜索的搜索成功时的平均搜索长度 ASLIndexSeq = ASLIndex + ASLSubList

6、其中, ASLIndex 是在索引表中搜索子表位置的平均搜索长度，ASLSubList 是在子表内搜索对象位置的搜索成功的平均搜索长度。 设把长度为 n 的表分成均等的 b 个子表，每个子表 s 个对象，则 b = n/s。又设表中每个对象的搜索概率相等，则每个子表的搜索概率为1/b，子表内各对象的搜索概率为 1/s。 若对索引表和子表都用顺序搜索，则索引顺序搜索的搜索成功时的平均搜索长度为 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1,索引顺序搜索的平均搜索长度与表中的对象个数 n 有关，与每个子表中的对象个数 s 有关。在给定 n 的情况下，s 应选

7、择多大？ 用数学方法可导出, 当 s = 时, ASLIndexSeq取极小值 +1。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，还要受到页块大小的制约。 若采用折半搜索确定对象所在的子表, 则搜索成功时的平均搜索长度为 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2,倒排表 (Inverted Index List),对包含有大量数据对象的数据表或文件进行搜索时，最常用的是针对对象的主关键码建立索引。主关键码可以唯一地标识该对象。用主关键码建立的索引叫做主索引。 主

8、索引的每个索引项给出对象的关键码和对象在表或文件中的存放地址。 但在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息： (1) 列出所有教师的名单；,对象关键码 key 对象存放地址 addr,(2) 已婚的女性职工有哪些人？ 这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。 因此，除主关键码外，可以把一些经常搜索的属性设定为次关键码，并针对每一个作为次关键码的属性，建立次索引。 在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性值的对象按存放地址递增的顺序或按主关键码递增的顺序链接在一起。

9、,次索引的索引项由次关键码、链表长度和链表本身等三部分组成。 例如，为了回答上述的查询，我们可以分别建立“性别”、“婚否”和“职务”次索引。,性别次索引,次关键码 男 女 计 数 5 3 地址指针,指针 03 08 17 24 47 51 83 95,婚否次索引,次关键码 已婚 未婚 计 数 5 3 地址指针,指针 03 08 24 47 83 17 51 95,职务次索引,次关键码 教师 教务员 实验员 计 数 5 1 2 地址指针,指针 08 24 47 51 83 03 17 95,(1) 列出所有教师的名单； (2) 已婚的女性职工有哪些人？ 通过顺序访问“职务”次索引中的“教师”链，

10、可以回答上面的查询(1)。 通过对“性别”和“婚否”次索引中的“女性”链和“已婚”链进行求“交”运算，就能够找到所有既是女性又已婚的职工对象，从而回答上面的查询(2)。 倒排表是次索引的一种实现。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的对象。,在次索引中记录对象存放位置的指针可以用主关键码表示: 可通过搜索次索引确定该对象的主关键码, 再通过搜索主索引确定对象的存放地址。 在倒排表中各个属性链表的长度大小不一,管理比较困难。为此引入单元式倒排表。 在单元式倒排表中, 索引项中不存放对象的存储地址, 存放该对象所在硬件区域的标识。 硬件区域可以是磁盘柱

11、面、磁道或一个页块, 以一次 I / O 操作能存取的存储空间作为硬件区域为最好。,为使索引空间最小, 在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数,整个次索引形成一个(二进制数的) 位矩阵。 例如, 对于记录学生信息的文件, 次索引可以是如图所示的结构。二进位的值为 1 的硬件区域包含具有该次关键码的对象。 如果在硬件区域1，中有要求的对象。然后将硬件区域1，等读入内存，在其中进行检索，确定就可取出所需对象。,单元式倒排表结构,m 路静态搜索树,当数据对象数目特别大，索引表本身也很大，在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。 此时, 可以建立索引的索引(二级

12、索引)。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。,如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引(三级索引)。这时，访问外存次数等于读入索引次数再加上1次读取对象。,02 06,11 15,18 23,29 32,38 41,45 49,52 60,77 95,(06, ) (15, ) (23, ),(06, ) (15, ) (23, ),(32, ) (41, ) (49, ),(60, ) (95, ),(23, ) (41, ) (95, ),root,head,必要时, 还可以有4级

13、索引, 5极索引, 。 这种多级索引结构形成一种 m 叉树。树中每一个分支结点表示一个索引块, 它最多存放 m 个索引项, 每个索引项分别给出各子树结点 (低一级索引块) 的最大关键码和结点地址。 树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树。 m路搜索树可能是静态索引结构，即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。,多级索引结构形成 m 路搜索树,m路搜索树还可能是动态索引结构, 即在整个系统运行期间, 树的结构随数据的增删及时调整, 以保持最佳的搜索效率。,数据区,一级索引,二级索引,三级索引,

14、四级索引,动态搜索结构,现在我们所讨论的 m 路搜索树多为可以动态调整的多路搜索树，它的一般定义为： 一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树： 根最多有 m 棵子树, 并具有如下的结构： n, P0, ( K1, P1 ), ( K2, P2 ), , ( Kn, Pn ) 其中, Pi 是指向子树的指针, 0 i n m; Ki 是关键码, 1 i n m。 Ki Ki+1, 1 i n。,动态的 m 路搜索树,在子树 Pi 中所有的关键码都小于 Ki+1, 且大于 Ki，0 i n。 在子树 Pn 中所有的关键码都大于Kn； 在子树 P0 中的所有关键码都小于 K

15、1。 子树 Pi 也是 m 路搜索树，0 i n。,一棵3路搜索树的示例,35,20 40,a,b,c,d,e,25 30,10 15,45 50,m 路搜索树的类定义 template class Mtree /基类 public: Triple ,AVL树是2路搜索树。如果已知 m 路搜索树的度 m 和它的高度 h, 则树中的最大结点数为,(等比级数前 h 项求和),每个结点中最多有 m-1 个关键码，在一棵高度为 h 的 m 路搜索树中关键码的最大个数为 mh+1-1。 高度 h=2 的二叉树, 关键码最大个数为7； 高度 h=3 的3路搜索树, 关键码最大个数为 34-1 = 80。,struct Triple Mnode * r; /结点地址指针 int i; int tag; /结点中关键码序号 i ; /tag=0,搜索成功；tag=1,搜索不成功,标识 m 路搜索树搜索结果的三元组表示,m 路搜索