静态散列（Static Hashing）
顺序组织文件的一个缺点是我们必须访问索引结构来定位数据，或者必须使用二分法搜索，这将导致过多的I/O操作。基于散列（hashing）技术的文件组织使我们能够避免访问索引结构。
在对散列的描述中，我们将使用术语桶（bucket）来表示能存储一条或多条记录的一个储存单位，通常一个桶就是一个磁盘块，但也可能小于或大于一个磁盘块。
令$K$表示所有搜索码值的集合，令$B$表示所有桶地址的集合，散列函数（hashing function）$h$是一个从$K$到$B$的函数。
不同搜索码值可能被存储到同一个桶中，因此，我们必须检查桶中每条记录的搜索码值，以确定该记录是否是我们要查找的记录。
散列函数
最坏的可能是散列函数把所有搜索码值映射到同一桶中。
具有下列分布特性的散列函数是我们理想中想建成的：
- 分布是均匀的。即散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值
- 分布是随机的。即在一般情况下，不管搜索码值实际怎样分布，每个桶应分配到的搜索码值数目几乎相同。散列函数应该表现为随机的。
通常散列函数在搜索码中字符的内部二进制机器表示上执行计算。这种类型的一个简单函数是先计算码中字符的二进制表示的总和，然后返回该总和取桶数目的模。
桶溢出处理（bucket overflow）
如果桶没有足够的空间，就会发生桶溢出，桶溢出的发生可能有以下几个原因：
- 桶不足
- 偏斜偏斜发生的原因可能有两个：1）多条记录可能具有相同的搜索码。2）所选的散列函数可能会造成搜索码的分布不均。
尽管分配的桶比所需的桶多一些，但是桶溢出还是可能发生。我们用溢出桶（overflow bucket）来处理桶溢出问题。如果一条记录必须插入桶$b$中，而桶$b$已满，系统会为桶$b$提供一个溢出桶，并将此记录插入到这个溢出桶中。如果溢出桶也满了，系统会提供另一个溢出桶。
一个给定桶的所有溢出桶用一个链接列表链接在一起，使用这种链接列表的溢出处理称为溢出链（overflow chaining）。
散列索引（Hash Indices）
散列不仅可以用于文件组织，还可以用于索引结构的创建。散列索引将搜索码及其相应的指针组织成散列文件结构。
我们将散列函数作用于搜索码以确定对应的桶，然后将此搜索码以及响应指针存入此桶（或溢出桶）中。
严格地说，散列索引只是一种辅助索引结构。如果一个文件自身是按 散列组织的，就不必在其上另外建立一个独立的索引结构。
我们用术语散列索引来表示散列文件结构和辅助散列索引。
静态散列的缺点
如果我们为会随时间变大的数据库使用静态散列时会有三种选择：
- 根据当前文件大小选择散列函数。这种选择会使性能随数据库的增大而下降
- 根据将来某个时刻文件的预计大小选择散列函数。尽管这样可以避免性能下降，但是初始会造成相当大的空间浪费。
- 随着文件增大，周期性地对散列结构进行重组。但重组是一个规模大、耗时的操作，而且重组期间必须禁止对文件的访问。
动态散列
几种动态散列技术允许散列函数动态改变，以适应数据库增大或缩小的需要。这里介绍的是可扩充散列（extendable hashing）。
数据结构
使用可扩散序列时，我们选择一个具有均匀性和随机特性的散列函数$h$。但是，此散列函数产生的值范围相对较大，是$b$位二进制整数。一个典型的$b$值是32.
开始时，我们并不使用散列值的全部$b$，任意时刻我们使用的位数$i$满足$0 \leq i \leq b$。这个的$i$个位用作附加的桶地址表中的偏移量。$i$的值随着数据库大小的变化而增大或减小。
几个连续的表项可能指向同一个桶。所有这样的表项有一个共同的散列前缀，但这个前缀的长度可能小于$i$。因此，我们给每一个桶附加一个整数值，用来表明共同的散列前缀长度，桶地址中指向桶的表项编号为
查询和更新
查询
为了确定含有搜索码$K_l$的痛的位置，系统取得$h(K_l)$的前$i$个高位，然后为这个位串查找对应的表项，再根据表项中的指针得到桶的位置。
插入
要插入一条搜索码值为$k_l$的记录，系统按上述相同过程进行查找，最终定位到某个桶$j$，如果该桶中有剩余空间，系统将该记录插入该桶即可；若桶$j$已满，系统必须分裂该桶，系统需首先根据散列值确定是否需要增加所使用的位数
- 如果$i = i_j$，那么在桶地址中只有一个表项 指向桶$j$。所以系统需要增加桶地址表的大小，系统考虑多引入散列值的一位。系统将$i$的值加1，从而使桶地址表的大小加倍。
*如果桶$j$中所有记录搜索码值相同，那么分裂多少次也不能解决问题。在这种情况下，采用溢出桶来储存记录，就像在静态散列中那样。 - 如果$i > i_j$，那么在桶地址中表中有多个表项指向桶$j$。因此，系统不需要扩大桶地址表就能分裂桶j。
删除
要删除一条搜索码值为$K_l$的记录，系统可以按照前面的查找过程找到相应的桶$j$，系统不仅要把搜索码从桶中删除，还要把记录从文件中删除。如果此时桶为空，那么桶也要删除。注意⚠️，此时某些桶可能合并，桶地址表的大小也可能减半。
静态散列和动态散列的比较
可扩充散列最主要的优点：
- 其性能不随文件的增长而降低
- 其空间开销是最小的
可扩充散列的缺点：
- 查找涉及一个附加的简介层
- 桶地址表可能会变得十分巨大
- 改变桶地址表的大小是非常昂贵的操作
顺序索引和散列的比较
文件可以被组织为
- $B^+$树组织或索引顺序组织将记录文件组织成顺序文件
- 散列
- 堆文件
要对关系的文件组织和索引技术做出明智的选择，实现者或数据者必须考虑以下问题：
- 索引或散列组织的周期性重组代价是否可以接受？
- 插入和删除的相对频率如何？
- 是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间？
- 用户可能提出哪些类型的查询？
散列文件组织和散列索引的区别？