《数据库--线性散列》由会员分享，可在线阅读，更多相关《数据库--线性散列（18页珍藏版）》请在金锄头文库上搜索。
1、线性散列散列表n定义：散列又叫哈希，它是根据哈希函数和冲突处 理的方法将一组关键字影射到一个有限的连续地址 集上，并以关键字在地址集中的“象”作为存储位置 。n优势：跟一般的查找方法(如线性表、树等)相比。 它在定位过程中不用进行关键字的比较，查找效率 不依赖查找过程所进行的比较次数，记录存储位置 和关键值存在着一个确定的对应关系，通过关键值 就可以影射到其存储地址。因此具有较高的查找效 率。静态散列n桶的数目B固定，从来不改变的。可以存在 溢出桶。n静态散列表索引的缺点：当数据库数据增加 ，初始的Bucket太小， 需要建立溢出块。 如果一个索引中大部分的桶都有溢出块，将 影响查找效率。n因
2、此引入了动态散列表索引：可扩展散列表 ，线性散列表。 动态散列n动态散列表允许B的改变，使B近似于记录 总数除以块中能容纳的记录数所得到的商； 也就是说，每个桶大约有一个存储块。n动态散列表可以分为两种： 可扩展散列 线性散列 可扩展散列表n它在简单的静态散列表结构上主要增加了：为桶引入了一个简接层，即用一个指向块的指针数组 来表示桶，而不是用数据块本身组成的数组来表示桶 。指针数组能增长，它的长度总是2的幂，因而数组每增长一次，桶的数目就翻倍。并非每个桶都有一个数据块；如果某些桶中的所有记 录都可以放在一个块中，那么这些桶可能共享一个块 。可扩展散列表n这种方法是认为B太小时即将其加倍，最然
3、是可以 动态的增加桶的数目，但是也有些自身的缺点：当桶的数组需要翻倍时，要做大量的工作。这些工作 会阻碍对数据文件的访问，或是使某些插入看来花费 很长的时间。当桶数翻倍后，它在主存中可能就装不下了，或者把 其他的一些我们需要保存的数据挤出去。其结果是， 一个运行良好的系统可能突然之间每个操作所需的从 盘I/O开始大增，并且出现明显的性能下降。线性散列表n正是由于可扩展散列表的一些缺点，我们引入了另 一种策略：线性散列表，其中桶的增长较为缓慢。 在线性散列中出现了一些新的要点：桶数n的选择总是使存储块的平均记录数保持与存 储块所能容纳的记录总数成一个固定的比例，如 80%。由于存储块并不是可以分裂，所以允许有溢出块， 尽管每个桶的平均溢出块数远小于1。线性散列表 用来做桶数组项序号二进制位数是 ，其中 n是当前的桶数。这些位总是从散列函数得到的 位序列的右（低位）端开始取。 假定散列函数值的i位正在用来给桶数组项编号 ，且有一个键值为K的记录想要插入到编为 的桶中；即 是 的后i位。那么，把 当作二进制整数，设它为m。如果m=n，所以桶11不存在。 必须把第一位的1改为0后重新 定位到桶01中。由题可01桶中 不存在键值散列为1011的记录 ，所以查找失败。00000101 1111 1010011000i=2n= 3 r=4
