第十章索引与散列 静态索引结构 口动态索引结构 散列 可扩充散列
静态索引结构 当数据对象个数m很大时,如果用无序表形 式的静态搜索结构存储,采用顺序搜索,则搜索 效率极低。如果采用有序表存储形式的静态搜 索结构,则插入新记录进行排序,时间开销也很 可观。这时可采用索引方法来实现存储和搜索。 线性索引( Linear Index list) a示例:有一个存放职工信息的数据表,每一 个职工对象有近1k字节的信息,正好占据 个页块的存储空间
索引表 数据表 kevladd 职工号姓名性别职务婚否 0318010083张珊女教师已婚 081414008李斯男」教师已婚 17301003王鲁男教务员已婚 oeO 2420720895刘樊女实验员未婚 4730X2024岳跋男教师已婚 51380入30047周斌男教师已婚 83100×XN34037胡江男实验员未婚」 952203051林青女教师』未婚
100 140 180 220 260 300 340 380 key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220 职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 … 08 李斯 男 教师 已婚 ... 03 王鲁 男 教务员 已婚 ... 95 刘琪 女 实验员 未婚 ... 24 岳跋 男 教师 已婚 ... 47 周斌 男 教师 已婚 ... 17 胡江 男 实验员 未婚 ... 51 林青 女 教师 未婚 ... 索引表 数据表
」假设内存工作区仅能容纳64k字节的数据, 在某一时刻内存最多可容纳64个对象以供 搜索。 如果对象总数有14400个,不可能把所有对 象的数据一次都读入内存。无论是顺序搜索 或折半搜索,都需要多次读取外存记录。 a如果在索引表中每一个索引项占4个字节,每 个索引项索引一个职工对象,则14400个索 引项需要5625k字节,在内存中可以容纳所 有的索引项
这样只需从外存中把索引表读入内存,经过 搜索索引后确定了职工对象的存储地址,再 经过1次读取对象操作就可以完成搜索。 稠密索引:一个索引项对应数据表中一个对 象的索引结构。当对象在外存中按加入顺序 存放而不是按关键码有序存放时必须采用稠 密索引结构,这时的索引结构叫做索引非顺 序结构。 a稀疏索引:当对象在外存中有序存放时,可 以把所有m个对象分为b个子表(块)存放, 个索引项对应数据表中一组对象(子表)