计算机四级考试数据库原理,2017年计算机四级考试数据库复习笔记：散列技术

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

本文来源：https://www.wddqw.com/IZfI.html