瑺掌觐縈与鹲测 静态索引结构 动态索引结构 Trie树 散列( Hashing)
静态索引结构 动态索引结构 Trie树 散列 (Hashing)
静态索引结构 当数据对象个数n很大时,如果用无序表形式 的静态搜索结枃存储,采用顺序搜索,则搜索效 率极低。如果采用有序表存储形式的静态搜索结 构,则插入新记录进行排序,时间开销也很可观。 这时可采用索引方法来实现存储和搜索。 线性索引( Linear Index List) 0示例:有一个存放职工信息的数据表,每一个 职工对象有近1k字节的信息,正好占据一个页 块的存储空间
静态索引结构 示例：有一个存放职工信息的数据表，每一个 职工对象有近 1k 字节的信息, 正好占据一个页 块的存储空间。 当数据对象个数 n 很大时，如果用无序表形式 的静态搜索结构存储，采用顺序搜索，则搜索效 率极低。如果采用有序表存储形式的静态搜索结 构，则插入新记录进行排序，时间开销也很可观。 这时可采用索引方法来实现存储和搜索。 线性索引 (Linear Index List)
索引表 数据表 关鮭码地址 职工号|姓名性别「职务|婚否其它 3180 ,10(83张珊女「教师「已婚{…… 1008李斯男「教师「已婚{… B3王鲁男|行政助理|已婚|… 24260 20|95刘琪女实验员未婚… 2024岳跋男教师|已婚 51380 3047周惠男教师「已婚 3100 34017胡江男「实验员|未婚 95220 38051林青女教师|未婚……
假设内存工作区仅能容纳64k字节的数据,在 某一时刻内存最多可容纳64个对象以供搜索。 如果对象总数有14400个,不可能把所有对象 的数据一次都读入内存。无论是顺序搜索立对 分搜索,都需要多次读取外存记录。 如果在索引表中每一个索引项占4个字节,每个 索引项索引一个职工对象,则14400个索引项 需要56.25k字节,在内存中可以容纳所有的索 引项。 这样只需从外存中把索引表读入内存,经过搜 索索引后确定了职工对象的存储地址,再经过1 次读取对象操作就可以完成搜索
假设内存工作区仅能容纳64k 字节的数据，在 某一时刻内存最多可容纳64 个对象以供搜索。 如果对象总数有 14400 个, 不可能把所有对象 的数据一次都读入内存。无论是顺序搜索或对 分搜索，都需要多次读取外存记录。 如果在索引表中每一个索引项占4个字节, 每个 索引项索引一个职工对象，则14400 个索引项 需要 56.25k 字节, 在内存中可以容纳所有的索 引项。 这样只需从外存中把索引表读入内存，经过搜 索索引后确定了职工对象的存储地址，再经过1 次读取对象操作就可以完成搜索
稠密索引:一个索引项对应数据表中一个对象 的索引结构。当对象在外存中按加入顺序存放 而不是按关键码有序存放时必须采用稠密索引 结构,这时的索引结构叫做索引非顺序结构。 稀疏索引:当对象在外存中有序存放时,可以 把所有n个对象分为b个子表块)存放,一个 索引项对应数据表中一组对象(子表 在子表中,所有对象可能按关键码有序地存放, 也可能无序地存放。但所有这些子表必须分块 有序,后一个子表中所有对象的关键码均大于 前一个子表中所有对象的关键码。它们都存放 在数据区中。另外建立一个索引表
稠密索引：一个索引项对应数据表中一个对象 的索引结构。当对象在外存中按加入顺序存放 而不是按关键码有序存放时必须采用稠密索引 结构，这时的索引结构叫做索引非顺序结构。 稀疏索引：当对象在外存中有序存放时，可以 把所有 n 个对象分为 b 个子表(块)存放，一个 索引项对应数据表中一组对象(子表)。 在子表中, 所有对象可能按关键码有序地存放, 也可能无序地存放。但所有这些子表必须分块 有序，后一个子表中所有对象的关键码均大于 前一个子表中所有对象的关键码。它们都存放 在数据区中。另外建立一个索引表
索引表中每一表目叫做索引项,它记录了子表 中最大关键码 max keyl以及该子表在数据区中 的起始位置 obi addr 索引表max_ key obj_addr ⅠD 子表12212139302933825 子表2424438344036484739 子表3|605874567279668078 子表4929794828898 各个索引项在索引表中的序号与各个子表的块 号有一一对应的关系:第i个索引项是第i个 子表的索引项,i=0,1,,n-1。这样的索引结 构叫做索引顺序结构
索引表中每一表目叫做索引项，它记录了子表 中最大关键码max_key以及该子表在数据区中 的起始位置obj_addr。 各个索引项在索引表中的序号与各个子表的块 号有一一对应的关系：第i 个索引项是第 i 个 子表的索引项, i = 0, 1, …, n-1。这样的索引结 构叫做索引顺序结构
对索引顺序结构进行搜索时,一般分为两级搜 索。 0先在索引表D中搜索给定值K,确定满足 IDi-1 max key<ksDi. max kej 的i值,即待查对象可能在的子表的序号。 0然后再在第i个子表中按给定值搜索要求的 对象。 索引表是按mxke有序的,且长度也不大 可以对分搜索,也可以顺序搜索。 各子表内各个对象如果也按对象关键码有序 可以采用对分搜索或顺序搜索;如果不是按对 象关键码有序,只能顺序搜索
对索引顺序结构进行搜索时，一般分为两级搜 索。 先在索引表 ID 中搜索给定值 K，确定满足 ID[i-1].max_key < K ID[i].max_key 的 i 值，即待查对象可能在的子表的序号。 然后再在第 i 个子表中按给定值搜索要求的 对象。 索引表是按max_key有序的，且长度也不大， 可以对分搜索，也可以顺序搜索。 各子表内各个对象如果也按对象关键码有序， 可以采用对分搜索或顺序搜索；如果不是按对 象关键码有序，只能顺序搜索
索引顺序搜索的搜索成功时的平均搜索长度 ASLIndexsea= AsLlindex ASL Sublist 其中, ASL是在索引表中搜索子表位置的 平均搜索长度,ASLb是在子表内搜索对象 位置的搜索成功的平均搜索长度。 设把长度为n的表分成均等的b个子表,每个 子表s个对象,则b=「m又设表中每个对 象的搜索概率相等,则每个子表的搜索概率为 1/b,子表内各对象的搜索概率为1/s 若对索引表和子表都用顺序搜索,则索引顺序 搜索的搜索成功时的平均搜索长度为 ASLIndexse=(b+)2+(s+1)2=(b+s)/2+1
索引顺序搜索的搜索成功时的平均搜索长度 ASLIndexSeq = ASLIndex + ASLSubList 其中，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应选择多大? 利用数学方法可以导出,当s=√n时, ASLIndexs取极小值√m+1。这个值比顺序搜 索强,但比对分搜索差。但如果子表存放在外 存时,还要受到页块大小的制约。 若采用对分搜索确定对象所在的子表,则搜索 成功时的平均搜索长度为 ASLInderep s SlIder +ASL Sublist ≈log2(b+1)-1+(s+1)/2 ≈log2(1+n/s)+s/2
索引顺序搜索的平均搜索长度不仅与表中的对 象个数 n 有关，而且与每个子表中的对象个数 s 有关。在给定 n 的情况下，s 应选择多大？ 利用数学方法可以导出，当 s = 时， ASLIndexSeq取极小值 +1。 这个值比顺序搜 索强，但比对分搜索差。但如果子表存放在外 存时，还要受到页块大小的制约。 若采用对分搜索确定对象所在的子表，则搜索 成功时的平均搜索长度为 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2 (1+n / s ) + s/2 n n
倒排表( averted Index list) 对包含有大量数据对象的数据表或文件进行搜 索时,最常用的是针对对泉的主关键码建立索 引。主关键码可以唯一地标识该对象。用主关 键码建立的索引叫做主索引。 主索引的每个索引项给出对象的关键码和对象 在表或文件中的存放地址。 对家关键码keν对隶存放地址adr 但在实际应用中有时需要针对其它属性进行搜 索。例如,查询如下的职工信息 a(1)列出所有教师的名单 (2)已婚的女性职工有哪些人?
倒排表 (Inverted Index List) 对包含有大量数据对象的数据表或文件进行搜 索时，最常用的是针对对象的主关键码建立索 引。主关键码可以唯一地标识该对象。用主关 键码建立的索引叫做主索引。 主索引的每个索引项给出对象的关键码和对象 在表或文件中的存放地址。 但在实际应用中有时需要针对其它属性进行搜 索。例如，查询如下的职工信息： (1) 列出所有教师的名单； (2) 已婚的女性职工有哪些人？ 对象关键码 key 对象存放地址addr
