顺序文件组织的一个缺点是我们必须访问索引结构来定位数据，或者使用二分搜索，导致过多的I/O，基于散列的文件组织使我们能够避免访问索引结构，直接定位数据。

      散列技术大体上是依赖散列函数，把搜索码值直接映射到磁盘（桶）上的一系列操作；这是一种文件系统中的文件组织和管理技术。

      桶（bucket）表示能存储一条或多条记录的一个存储单位；通常一个桶就是一个磁盘块。

      散列函数应该具有的性质：

      1.使搜索码分布均匀；

      2.使搜索码随机分布；即在一般情况下，每个桶分配到的搜索码不应该与搜索码值之外的任何可见排序相关，并且分配到每个桶的搜索码数目应该几乎相同。

例如，如果我们把某些商标或名字的首字母映射到对应的26个桶中，这个映射就不符合上述性质，因为很多人倾向于取前几个字母作为名字的首字母，这样就导致数据的分布不均；

一.静态散列

    这种散列技术在数据库设计初期就确定了散列函数和桶的数量；这就是所谓的静态；

    一个紧临的问题就是，如果在数据库壮大的过程中桶或桶内空间不够用了怎么办？这就是牵扯到桶溢出处理，桶溢出的发生可能有一下几个原因；

    1.桶不足：桶的数目小于记录总数/一个桶能存放的记录数；

    2.偏斜：某些桶分配到的记录比其他桶多，所以即使其他同仍有空间，某个通仍可能是溢出的。

为了减少第一种可能，一般多取20%的桶。至于第二种可能，我们用溢出桶解决。溢出桶就是在已满的桶后面链接一个新的桶，从而把这个链上的所有桶看成是一个桶，在插入数据时向后顺延。

     静态散列索引将搜索码及其相应的指针组织成散列文件结构；具体的做法是，将散列函数作用于搜索码以确定对应的桶，然后将此搜索码以及相应的指针存入此桶中。

     一般，使用散列索引来表示散列文件结构。所以，是一种文件结构。

二.动态散列

    这是一种从构建开始就与静态散列不同的散列技术。

    首先来看静态散列存在的一个严重问题就是要固定桶地址集合，但是大多数数据库是随时间变大的，而三种解决方案也不尽人意：1.根据初始文件大小选择散列函数——未来的性能下降；2.根据预计文件大小选择散列函数——前期的空间浪费；3.周期性重组——重组期间数据库几乎不可用；

    动态散列即允许散列函数动态改变，以适应数据库的增大或缩小。可扩展散列是其中一种：

    1.数据结构

 http://s2/mw690/0030wlwZzy6OgTe59eh71&690

    其中散列前缀决定桶地址表的个数和对应位置，如前缀两位，表示桶地址数有2^2=4个，也决定了如下表所示的散列码应该对应到桶地址表的哪个表项中。如第一个Brighton前两位为00，则对应第一个表项；http://s12/mw690/0030wlwZzy6OgTeeKOD8b&690    2.更新过程：①刚开始的时候散列前缀取值为0，及只有一个表项，对应首位为0或1的散列值；

                ②插入Brighton，0开头，指到一个桶；

                ③插入Downtown，桶地址表不够用，前缀+1，表项变成2个(0和1)，1开头，指到另一个桶；

                ④插入Mianus，前缀+1，表项变为4个（00,01,10,11），这时桶要分裂，10指向Downtown，11指向Mianus；

                ⑤以此类推，如果同样开头的散列值个数超过了桶的大小，就以溢出桶的形式继续存储而不分裂桶；

三.总结

    到现在，已经大概可以看出，散列索引是个点位查询（where A=c），二顺序索引适合范围查询（where A>C