索引顺序表

【说明】博客内容选自课件内容

目录

静态索引结构

1. 索引顺序表

索引顺序表的查找

查找成功时的平均查找长度

2. m 叉静态搜索树

当数据表中的记录个数 n 很大时, 由于内存容量的限制，不能全部存入内存。因此，在查找过程中需要反复与外存交换信息，此时前面介绍的各种算法的效率都很低。

   折半查找：记录必须全部在内存。

   静态查找树表：记录必须全部在内存。  

   二叉平衡树：记录必须全部在内存。

   顺序查找：记录不必全部在内存，但搜索效率极低。

采用索引方法来实现记录的存储和搜索

1. 索引顺序表  2. m 叉静态搜索树

后面要讨论的B树和键树是动态索引结构

例：有一个存放职工信息的数据表. 每一个职工数据10M字节,假设有10000个职工，则数据表共占100G。假设内存只有2G。

采用索引表，每个索引项可索引一个职工记录，且占8个字节,则10000个索引项需要80K个字节。

稠密索引：一个索引项对应数据表中一个记录的索引结构。

稀疏索引：当记录在外存中有序(块)存放时，可以把所有n 个记录分为b 个子表(块)存放，一个索引项对应数据表中一组记录(子表)。

在子表中,  记录可以按关键码有序地存放,也可以无序地存放。但所有这些子表必须分块有序,即：后一个子表中所有记录的关键码均大于前一个子表中所有记录的关键码。

一般分为两级搜索:

①先在索引表中搜索给定值 K, 查找确定满足范围ID[i-1].max_key < K