第十章索引与散列 静态索引结构 动态索引结构 散列
1 ◼ 静态索引结构 ◼ 动态索引结构 ◼ 散列
静态索引结构 当数据对象个数n很大时,可采用索引方法 来实现存储和搜索。 线性索引( Linear index list) 示例:有一个存放职工信息的数据表,每 个职工对象有近1字节的信息,正好占据一 个页块的存储空间。 假设内存工作区仅能容纳64k字节的数据, 在某一时刻内存最多可容纳64个对象以供 搜索
2 静态索引结构 ◼ 示例：有一个存放职工信息的数据表, 每一 个职工对象有近 1k 字节的信息, 正好占据一 个页块的存储空间。 ◼ 假设内存工作区仅能容纳64k 字节的数据, 在某一时刻内存最多可容纳 64 个对象以供 搜索。 当数据对象个数 n 很大时, 可采用索引方法 来实现存储和搜索。 线性索引 (Linear Index List)
索引表 数据表 kevladd 职工号姓名性别职务婚否 032k 083张删女教师已婚 08k1k08李斯男教师已婚 k2k03王鲁男槨务员己婚 244kN,3k95刘琪女实验员未婚 475k 424岳跋男教师已婚 517kN5k47周斌男教师已婚 830X'6k17胡江男实验员未婚 953k 7ks1林青女教师未婚
3 0 1k 2k 3k 4k 5k 6k 7k key addr 03 2k 08 1k 17 6k 24 4k 47 5k 51 7k 83 0 95 3k 职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 … 08 李斯 男 教师 已婚 ... 03 王鲁 男 教务员 已婚 ... 95 刘琪 女 实验员 未婚 ... 24 岳跋 男 教师 已婚 ... 47 周斌 男 教师 已婚 ... 17 胡江 男 实验员 未婚 ... 51 林青 女 教师 未婚 ... 索引表 数据表
如果对象总数有14400个,不可能把所有对 象的数据一次都读入内存。无论是顺序搜 索或折半搜索,都需要多次读取外存记录。 如果在索引表中每一个索引项占4个字节, 索引项给出一个职工对象的关键码及其存 储地址,用以索引一个职工对象,则14400 个索引项需要56.25k字节,在内存中可以容 纳所有的索引项。 这样只需从外存中把索引表读入内存,经过 搜索索引后确定了职工对象的存储地址,再 经过1次读取对象操作就可以完成搜索
4 ◼ 如果对象总数有 14400 个, 不可能把所有对 象的数据一次都读入内存。无论是顺序搜 索或折半搜索, 都需要多次读取外存记录。 ◼ 如果在索引表中每一个索引项占4 个字节, 索引项给出一个职工对象的关键码及其存 储地址，用以索引一个职工对象, 则 14400 个索引项需要 56.25k 字节, 在内存中可以容 纳所有的索引项。 ◼ 这样只需从外存中把索引表读入内存, 经过 搜索索引后确定了职工对象的存储地址, 再 经过 1 次读取对象操作就可以完成搜索
稠密索引:一个索引项对应数据表中一个对 象的索引结构。当对象在外存中按加入顺序 存放而不是按关键码有序存放时必须采用稠 密索引结构,这时的索引结构叫做索引非顺 序结构。 稀疏索引:当对象在外存中有序存放时,可 以把所有n个对象分为b个子表(块存放 一个索引项对应数据表中一组对象(子表) 第i个索引项是第i个子表的索引项,i=0, 1,…n-1。这种索引结构叫做索引顺序结构
5 ◼ 稠密索引：一个索引项对应数据表中一个对 象的索引结构。当对象在外存中按加入顺序 存放而不是按关键码有序存放时必须采用稠 密索引结构，这时的索引结构叫做索引非顺 序结构。 ◼ 稀疏索引：当对象在外存中有序存放时，可 以把所有 n 个对象分为 b 个子表(块)存放， 一个索引项对应数据表中一组对象(子表)。 ◼ 第 i 个索引项是第 i 个子表的索引项, i = 0, 1, …, n-1。这种索引结构叫做索引顺序结构