数据库--线性散列

线性散列散列表定义：散列又叫哈希，它是根据哈希函数和冲突处理的方法将一组关键字影射到一个有限的连续地址集上，并以关键字在地址集中的“象”作为存储位置。优势：跟一般的查找方法(如线性表、树等)相比。它在定位过程中不用进行关键字的比较，查找效率不依赖查找过程所进行的比较次数，记录存储位置和关键值存在着一个确定的对应关系，通过关键值就可以影射到其存储地址。因此具有较高的查找效率。静态散列桶的数目B固定，从来不改变的。可以存在溢出桶。静态散列表索引的缺点：当数据库数据增加，初始的Bucket太小，需要建立溢出块。如果一个索引中大部分的桶都有溢出块，将影响查找效率。因此引入了动态散列表索引：可扩展散列表，线性散列表。动态散列动态散列表允许B的改变，使B近似于记录总数除以块中能容纳的记录数所得到的商；也就是说，每个桶大约有一个存储块。动态散列表可以分为两种：可扩展散列线性散列可扩展散列表它在简单的静态散列表结构上主要增加了：为桶引入了一个简接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶。指针数组能增长，它的长度总是2的幂，因而数组每增长一次，桶的数目就翻倍。并非每个桶都有一个数据块；如果某些桶中的所有记录都可以放在一个块中，那么这些桶可能共享一个块。可扩展散列表这种方法是认为B太小时即将其加倍，最然是可以动态的增加桶的数目，但是也有些自身的缺点：当桶的数组需要翻倍时，要做大量的工作。这些工作会阻碍对数据文件的访问，或是使某些插入看来花费很长的时间。当桶数翻倍后，它在主存中可能就装不下了，或者把其他的一些我们需要保存的数据挤出去。其结果是，一个运行良好的系统可能突然之间每个操作所需的从盘I/O开始大增，并且出现明显的性能下降。线性散列表正是由于可扩展散列表的一些缺点，我们引入了另一种策略：线性散列表，其中桶的增长较为缓慢。在线性散列中出现了一些新的要点：桶数n的选择总是使存储块的平均记录数保持与存储块所能容纳的记录总数成一个固定的比例，如80%。由于存储块并不是可以分裂，所以允许有溢出块，尽管每个桶的平均溢出块数远小于1。线性散列表用来做桶数组项序号二进制位数是[]，其中n是当前的桶数。这些位总是从散列函数得到的位序列的右（低位）端开始取。假定散列函数值的i位正在用来给桶数组项编号，且有一个键值为K的记录想要插入到编为的桶中；即是的后i位。那么，把当作二进制整数，设它为m。如果mn，那么编号为m的桶存在并把记录存入该桶中。如果nm,那么桶m还不存在，因此我们把记录存入桶m，就是当我们把（它肯定是1）改为0时对应的桶。2logn12...iaaahK2i12i1a12...iaaa12...iaaa线性散列表的基本组织结构例题1.图1所示为一个n=2的线散列表。并用散列值的一位来确定记录所属的桶(i=1)。并假定散列函数产生四位，用将散列函数作用到记录的查找键上所产生的值来表示记录。i=1n=2r=300001010111101图1线性散列表现在我们来详细的分析下这个线性散列的大致结构，提出一些注意事项帮助大家的学习。一．我们在图1中看到两个桶，每个桶包含一个存储块，标号分别为0和1。并且散列值的最后一位为0的放入第0号桶中，最后一位为1的放入第1号个桶中。二．参数i（当前被使用的散列函数值的位数）、n（当前的桶数）和r（当前散列表中的记录总数），这些参数和数据共同构成了线性散列表。三．比率r/n将受到限制，使一般的桶都只需要约一个磁盘存储块。在选择桶数n时，要注意的策略是使文件中的记录个数不超过1.7n，即r=1.7n。线性散列表的插入在进行插入时注意的细节问题：插入一个新记录时，我们计算，其中K是记录的键，并确定序列后面用做桶号的正确位数。并将记录放入该桶，或者（在桶号大于等于n时）放入把第一个二进制由1改为0后确定的桶中。如果桶没有空间，那么我们创建一个溢出块，连接在那个桶上，并将记录存入该溢出块中。每次插入，必须用当前的记录总数r于阀值r/n比较，若比率太大，就增加下一个桶到线性散列表中。一个重要的细节就是：当n超过时的情况。这时参数i就递增1。hK2ihK线性散列表的插入例题2我们考虑在例题1的散列表中，插入键值散列为0101的记录。因为其最后一位为1，记录应插入到第二个桶中，即第1号桶。桶中有空间，不需要创建溢出块。i=1n=2r=3000010101111010101大家想想这样对吗？存在的问题：首先，现在2个桶里有四个记录，不能保证r=1.7n，超出比率，因此，我们必须把n提高到3。其次，当n=3时，=2，应考虑把参数i调整为2，即使用的散列函数值的位数为2。最后，就是根据最后两位的值分对桶进行的分裂。2log3对其进行修正将提高n，使其等于3；并将i改为2。考虑把桶0和1改为桶00和01，并且增加下一个桶到散列表中，该桶编号为10。分裂桶00，在分裂时，键值散列为0000的记录保留在00桶中，因为以00结尾；键值散列为1010的记录存入桶10。如图示：i=2n=3r=4i=1n=2r=3000010101111010000010111111010011000例题3我们现在增加一个键值散列为0001的纪录。记录最后2位是01，且01的桶存在，那么将记录放入该桶中。这时问题出现了，该桶块已经被装满了，怎么办？我们增加一个溢出块，将三个纪录分配到这个桶中的两个块中；按散列键的值顺序保存。不要忘记检查纪录与桶的比率r/n。题中5/3小于1.7，故我们不需要创建新桶。i=2n=3r=500000001010110100110001111例题4我们将考虑插入散列值为0111的记录。该记录最后两位11，但是桶11不存在，我们将记录存放在哪个地方呢？我们回顾下前面注意事项的④由此可知，因为=3，此时n=m,我们把第一位1变为0，即记录将被存在第01号桶中该记录将被存入该桶的溢出块中？10112ii=2n=3r=6000000010101101001100001111111这样对吗？会不会出现什么问题？还记得我们前面讲的比率r/n吗？她将一直伴随我们，最后必须检查。上题中r=6,n=3，r/n=2。该散列表的记录与桶的比率已超过1.7。因此，我们必须创建一个编号为11的新桶，该桶碰巧是新记录所需的桶。分裂桶01中的四个记录，散列值为0001和0101的记录保留，散列值为0111和1111的记录存入新的第11号桶。现在01桶中只有两个值，所以删除其溢出块。i=2n=4r=60000000101011010011000011111110111111111线性散列表的查找线性散列表的查找依照我们所描述的选择插入记录所属桶的过程。以例题3的情形，其中i=2且n=3。首先，假设查找的散列值为1010的记录。由于i=2，我们查看最后两位10，把它们解释为二进制数，即m=2。因为mn，则标号为10的桶存在，所以我们将在该桶中查找。其次，考虑查找的散列值为1011的记录。现在需要查找标号为11的桶，但是由于m=3，且m=n，所以桶11不存在。必须把第一位的1改为0后重新定位到桶01中。由题可01桶中不存在键值散列为1011的记录，所以查找失败。0000010111111010011000i=2n=3r=4