6.3 索引技术

　　6.3.1 基本概念

　　1、 索引技术：是一种快速文件访问技术，它将一个文件的每个记录在某个或某些域(属性)上的取值与该记录的物理地址直接联系起来，提供了一种根据记录域的取值快速访问文件记录的机制;它的关键是建立取值域到记录的物理地址刘的映射关系，这种映射关系叫索引;

　　2、 索引技术分类：

　　(1) 有序索引技术：利用索引文件实现记录域(查找码)取值到记录物理地址间的映射关系，索引文件由索引记录组成，每个记录中记载一个索引项，索引项记录了某个特定的查找码值和具有该值的数据文件记录的物理地址;

　　(2) 散列技术：利用一个散列函数实现记录域取值到记录物理地址间的直接映射关系;

　　(3) 有序索引：有序索引作为基于索引文件的索引技术，需要考虑两个问题：(1)如何组织索引文件中的索引记录;(2)如何从索引文件出发，访问数据文件中的数据记录;

　　(A) 当需要采用有序索引机制快速访问数据文件时，首先要为该数据文件建立一个索引文件，它是索引记录和索引项的集合;

　　(B) 索引文件建立的方法：首先选定某些记录域作为查找码，然后建立数据记录在查找码上的取值与物理地址间的映射关系，组成索引项。所有索引项作为索引记录存储在索引文件中，索引文件根据某个特定的查找码值的顺序组织为顺序文件;

　　(C) 一个数据文件可以有多个查找码和索引文件;

　　6.3.2 有序索引的分类及特点

　　1、 聚集索引与非聚集索引

　　(1) 对数据文件和它的一个特定的索引文件，如果数据文件中数据记录的排列顺序与索引文件中索引项的排列顺序相一致，则该索引文件称为聚集索引，否则称为非聚集索引;

　　(2) 在一个数据文件上除了建立一个聚集索引外，还可建立多个非聚集索引;

　　2、 稠密索引和稀疏索引

　　如果数据文件中的每个查找码都在索引文件中都对应一个索引记录，称为稠密索引，如果只一部分对应，则称为稀疏索引;

　　3、 主索引和辅索引

　　在数据文件包含主码的属性集上建立索引称为主索引，在非主码属性上建立的索引称为辅索引;

　　4、单层索引和多层索引

　　(1) 单层索引(线性索引)：索引项根据键值在索引文件中顺序排列，组织成一维线性结构，每个索引项直接指向数据文件中的数据记录;

　　(2) 当数据文件很大时，即使采用稀疏索引，建成的索引文件也很大，导致效率低下，为解决该问题，可对索引文件中的索引项本身再建立一级稀疏索引，组成2层索引结构;进一步地，可建立多层树型索引结构来快速定位;

　　6.4 散列技术

　　6.4.1 散列文件

　　1、 散列是一种快速查找技术，它利用定义在文件记录上的查找码，通过计算一个散列函数，以散列函数值作为记录的物理地址，实现对文件记录直接快速访问。

　　2、 首先指定文件记录的一个域作为查找码(散列域)，然后定义一个查找码上的函数(散列函数)，函数的输入为查找码值，输出为物理地址;

　　3、 一般使用桶作为基本的存储单位，一个桶可存放多个文件记录，物理地址可以是记录所在的桶号，散列函数的输出可以是桶号;

　　6.4.2 散列函数

　　1、 散列方法依赖于好的散列函数，它应该尽可能均匀地将查找码分布到各个桶中，具体要满足如下两个条件：

　　(1) 地址的分布是均匀的;

　　(2) 地址的分布是随机的;

　　6.4.3 桶溢出

　　1、 产生桶溢出的两个原因：

　　(1) 文件初始设计时，为文件记录预留的存储空间不足;

　　(2) 散列函数的均匀分布性不好;

　　2、 设计散列函数时，应根据文件大小决定物理空间，一般应有20%余量，再设计合适的桶数目和桶大小，尽可能留有一些空闲桶，降低桶溢出的可能性;

　　3、 桶溢出的现象是难免的，需要DBS采用相应的桶溢出处理机制;

　　4、 散列方法的缺点：为了避免桶溢出。必须选一合适的散列函数，但这比较复杂，而且不象索引文件那样可以据数据记录变化动态调整。