数据结构知识 09年自考《数据结构》各章要点二[12]

09年自考《数据结构》各章要点二[12]  

　　顺序文件的插入 删除和修改只能通过复制整个文件实现

　　索引文件的组织方式 通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系 它和主文件一起构成索引文件

　　索引非顺序文件中的索引表为稠密索引 索引顺序文件中的索引表为稀疏索引

　　若记录很大使得索引表也很大时 可对索引表再建立索引 称为查找表 是一种静态索引

　　索引顺序文件常用的有两种

　　·ISAM索引顺序存取方法 是专为磁盘存取文件设计的 采用静态索引结构

　　·VSAM虚拟存储存取方法 采用B+树作为动态索引结构 由索引集 顺序集 数据集组成

　　散列文件是利用散列存储方式组织的文件 亦称为直接存取文件

　　散列文件

　　·优点是 文件随机存放 记录不需要排序;插入删除方便;存取速度快;不需要索引区 节省存储空间

　　·缺点是 不能进行顺序存取 只能按关键字随机存取 且询问方式限地简单询问 需要重新组织文件

　　多重表文件 对需要查询的次关键字建立相应的索引 对相同次关键字的记录建一个链表并将链表头指针 长度 次关键字作为索引表的索引项

　　倒排表 次关键字索引表称倒排表 主文件和倒排表构成倒排文件