散列索引：

内存数据可以采用散列确定存储页，主文件可以采用散列确定存储块，索引亦可采用散列确定索引项的存储块。

散列索引的插入比较容易理解。插入的时候有情况需要考虑，就是当插入的时候空间满了怎么做？一般是申请一个溢出桶，将该桶链接在后面。那么在删除的时候，我们也需要考虑删除后是否进行合并溢出桶。

散列索引的目标：最好没有溢出桶，每一个散列值仅有一个桶，我们希望散列的分布尽量的均匀。当溢出桶多的时候，我们的查询性能会下降，削弱了散列索引的作用。

根据上述问题，我们提出以下策略： 1.如果桶的数目是一个固定的值----静态散列索引 如果桶的数目不变：M过大，则浪费；M过小，会产生更多的溢出桶，增加查询时间

2.桶的数目随着键值增多而动态增加----动态散列索引 h（K）是和桶的数目M相关的，M的变化时候会影响原来的存储内容呢？

可扩展散列索引：是一种动态散列索引

*为桶引入一间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶

*指针数组能够增长，其长度是2的幂。因而数组每增长一次，桶的数目就翻倍。不过，并非每个桶都有一个数据块；如果某些桶中的所有记录可以放在一个块中，则这些桶可能共享一个块。

*散列函数h为每个键计算出一个K位二进制序列，该K足够大，比如32.但是桶的数目总是使用从序列的第一位或者最后一位算起的若干位，此位数小于K，比如说i位，也就是说，当i是使用的位数时，桶数组将有2^i个项

具体过程是：目前使用的是K位中的前i位确定索引块。如果未满就存入，如果已满则需要扩展散列桶，进行分裂：暂时i可能无需增加，重新散列该块的数据到两个块中，其他不变。

可扩展散列索引的问题： 1.当桶数组需要翻倍的时候，需要做大量的工作

2.当桶树翻倍后，其在主存中可能装不下，或者需要更大的空间

3.可扩展散列的最坏情况在于：我们的每块的记录树很好，但是开了很多的空间。（*）

线性散列索引

为了解决可扩展散列索引中桶的数目增长过快，但是其利用率很低的问题。

线性散列索引： 1.桶的数目n的选择总是是存储块的平均记录保持与存储快所能容纳的记录总数成一个固定的比例，例如0.8.超过这个比例，则桶的数目增长1块，分裂----线性增长，每次增1.

2.存储快并不总是可以分裂，索引允许有溢出块，尽管每个桶的平均溢出块数远小于1

3.用来做桶数组项序号的二进制位数是log2n的向上取整，其中n是当前的桶树。这些位数总是从散列函数得到的位序列的右端（即低位）开始取。

4.假设散列函数值的i位正在用来给桶数组项编号，且有一个键值为K的记录想要插进到编号位a1a2...ai的桶中，即a1a2...ai是h(K)的后i位。把a1a2...ai当做二进制数，设它为m。

如果m<n，则编号为m的桶存在并把记录存入该桶中

如果n<=m<2^i，那么该桶不存在，因此我们吧记录存入桶m-2^（i-1），也就是说我们吧a1（最高位此时，他肯定为1）改为0时对应的桶