[数据库之十三] 数据库索引之散列索引

一、什么是散列

  顺序文件组织的一个缺点是我们必须访问索引结构来定位数据，这将导致过多的 I/O 操作。基于散列（hashing）技术的文件组织使我们能够避免访问索引结构，散列也提供了一种构造索引的方法。

  桶（bucket）：表示能存储一条或多条记录的一个存储单位，通常一个桶就是一个磁盘块，也可能小于或大于一个磁盘块。

散列函数

h(K) → B

K 表示所有搜索码值的集合

B 表示所有桶地址的集合

h 是一个从 K 到 B 的函数，即散列函数

二、散列的作用

• 散列文件组织：即数据按照散列计算的地址存储，通过计算所需记录搜索码值上的一个函数直接获得包含该记录的磁盘块地址。

• 散列索引组织：把搜索码以及与它们相关联的指针组织成一个散列文件结构。

三、静态散列

1、散列函数的要求

  理想的散列函数把存储的码均匀地分布到所有桶中，使每个桶含有相同数目的记录，因此我们希望选择一个把搜索码值分配到桶中并且具有下列分布特性的散列函数：

• 分布是均匀的。即散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值。
• 分布是随机的。即在一般情况下，不管搜索码值实际怎样分布，每个桶应分配到的搜索码值数目几乎相同。散列值不应与搜索码的任何外部可见的排序相关，例如按字母的顺序或按搜索码长度的顺序，散列函数应该表现为随机的。

  一般情况下，散列函数就是要根据搜索码的值计算出一个很大的整数，然后对桶的数量求模，得到对应的记录应该放在哪个桶里面，所以这个很大的整数只要具有数据无关的随机性，就能保证数据分布在所有桶中是均匀和随机的。

2、桶溢出

  桶允许存储的数据的空间是有限的，当插入记录所映射到的桶的空间不足时，称为桶溢出。
  桶溢出可能的原因有：

• 桶不足。比如一共有 8 个桶，每个桶能存储 20 条记录，那么即使分布均匀，也无法插入第 161 条记录。

• 桶偏斜。某些桶分配到的记录比其他桶多，虽然其他桶仍有空间，但是新插入的记录映射到的是已满的桶。

桶偏斜发生的原因有：

• 数据问题。多条记录可能具有相同的搜索码，不管是什么散列函数，都会映射到同一个桶，因此对区分度不高的搜索码，不适合使用散列。
• 散列函数的问题。搜索码区分度高，但散列函数不够均匀和随机。

  解决桶溢出的方法：

• 空间冗余。即本来分配每个桶存储记录上限是 50 条，现在分配能存储 60 条记录的空间，多出来的空间可能被浪费，但减少了溢出的可能性。

• 溢出链。即使按照空间冗余的办法，还是有可能出现桶溢出的情况，则为已满的桶分配一个溢出桶，并将数据放到这个溢出桶中，如果溢出桶也满了，则提供另外一个溢出桶，不断循环，一个给定桶的所有溢出桶用一个链接列表链接在一起，就形成了一个溢出链。

3、缺陷

  桶的个数和每个桶的容量不好规划，如果小了，容易造成桶溢出；如果为了以后的数据增长设计得比较大，就会浪费当前的空间。

4、散列索引

  散列可用于索引结构的创建，即散列索引，将搜索码及其相应的指针组织成散列文件结构。散列索引是一种辅助索引，不需要作为聚集索引结构来使用。

下图展示了为搜索码 ID 建立的散列索引，散列函数为对 ID 对 8 取模，每个桶的大小为 2，若有超过两条数据的桶，则需使用溢出桶。

四、动态散列

  使用静态散列时，要求固定桶地址集合（即要使用多少个桶，每个桶大小是固定的），有三种选择：

• 1、根据文件大小选择散列函数。这种选择会使性能随数据库增大而下降。
• 2、根据将来某个时刻文件的预计大小选择散列函数。这样可以避免性能下降，但初始时会造成相当大的空间浪费。
• 3、随着文件增大，周期性地对散列结构进行重组。包括新散列函数的选择，在文件中每条记录上重新计算散列函数，以及分配新的桶。这是一个规模大、耗时长的操作，而且重组期间必须禁止对文件的访问。

而动态散列技术允许散列函数动态改变，以适应数据库增大或缩小的需要，可扩充散列就是一种常见的动态散列技术。

1、数据结构

  使用可扩充散列，首先要选择一个分布均匀和随机的散列函数 h，产生的值是 b 位二进制整数（典型的 b 值是 32）。

  如上图所示，32 位二进制，最多可以产生 2³² 个不同的整数，超过 40 亿个，如果用每个整数来代表一个桶，最多可以有超过 40 亿个桶，一般用不了这么多。当用不了这么多的时候，可以不取整个散列值，而是取 b 位的前 i 位，比如需要 8 个桶，那取前三位就可以表示不同的桶。随着数据库的大小变化，i 也随之增大和减小，如下所示：

  我们把右边叫做桶地址表，指明了使用多少位前缀，表中每条记录存储了散列值及对应指向的桶的地址。随着数据文件的增长，需要使用更多的位来表示不同的桶。事实上，桶和表的初始状态并不为上图所示，如果没必要的话，是不会一开始就创建这么多桶的，因为会造成空间的浪费，所以有可能桶地址表中几个连续的表项指向同一个桶，这多个表项拥有相同的前缀，但前缀长度可能小于 i。

  如上图所示，假设现在要插入一条记录，计算出的散列值对应桶地址表的 0 1 ... ，但是尚未为其单独创建一个桶，而 0 0 ... 对应的桶已经被创建了，并且还有空余的空间，那么就将这条记录插入到桶 0 中。

  每个桶都会记录一个整数，表示桶中所有记录的散列值的共同前缀的位数，设每个桶的编号为 j，这个记录位数为 i_j，则对桶 0 来说，j 为 0，i_j 为 1，如果 i_j = i，则说明这个桶存储的记录的散列值只对应桶地址表的一条记录。

2、查询和更新

  根据搜索码查询数据时，先用散列函数计算出搜索码值的散列值，再从桶地址表找到对应记录，最后找到对应的桶，再从桶中检索；而更新无非是在查询的基础上多了一步对数据进行更新，由于更新的字段可能包含在搜索码中，所以算法如下：

• 1、若更新的字段不是搜索码，则直接更新数据即可。
• 2、若更新的字段是搜索码，则：
  • 2.1 更新后的搜索码的散列值前 i 位跟原来保持不变，则记录不动；
  • 2.2 更新后的搜索码的散列值前 i 位跟原来有变化，则先将记录从当前桶删除，再从桶地址表查找到对应的桶并插入到该桶中，后面执行的算法是插入操作的算法。

3、插入

算法如下：

• 1、根据搜索码 K 计算出散列值，从桶地址表中查找到对应的桶 j，若该桶还未满则直接插入记录，否则执行 2。

• 2、桶 j 已满，需要分裂为两个桶，并将桶中现有记录和要插入的新记录一起重新分配。

  • 2.1、若 i_j < i，说明桶 j 对应桶地址表的多个表项，系统创建一个新的桶 z，将 i_j 和 i_z 置为原来的 i_j + 1，即分裂的桶和裂出来的新桶中的记录记录散列公共前缀位数要增加 1 位，然后重新分配。

    如下图所示，假设一个桶最多存储 4 条记录，标黄块表示该条记录计算出的散列值，标灰块表示该空间还未被使用。

• 2.2、若 i_j = i，说明桶 j 只对应桶地址表的一个表项，按照当前的散列前缀的位数分配的桶不够用了，需要增加一位散列前缀的位数，即将 i = i + 1，桶地址表会扩大为原来的两倍，原表中的每个表项都会被两个新的表项所替代。现在两个新的表项都指向桶 j，系统分配一个新的桶 z，新的表项指向桶 z，并且 i_j 、i_z 都为原来的 i_j + 1，最后将桶 j 中的部分数据重新分配到桶 z 中，新插入的数据按照新的 i 找到新的表项对应的桶并插入。

  如图所示，假设当前 i 为 2，每个桶最多存储 4 条记录，桶 j 为 桶 0，其余说明同上。

  扩位之前如图：

扩位后如图：

  如果原来桶 0 的四条记录散列值前 3 位都是 0 0 0 ...，那么为了插入新记录，需要再次扩位到 4 位，一般情况下，只要选用合适的散列函数，是不太可能导致多次扩位桶分裂的。如果桶 0 中所有的记录具有相同的搜索码，并且新记录的搜索码也一样，那不管使用什么散列函数，其散列值必然相同，不管扩位桶分裂多少次，都无法在该桶中插入该记录，这种情况下，应该使用溢出桶。

4、删除

  删除其实就是插入的逆操作，先查询桶，再删除数据，插入桶满分裂，删除则是桶空合并，当然合并需要考虑所有的桶的数据存储情况，合并后的桶不能装不下原来的两个桶的记录。

算法如下：

• 1、根据搜索码 K 计算出散列值，从桶地址表中查找到对应的桶 j，检索到对应的记录并将其从桶中删除。

• 2、删除完记录后桶 j 已空，则需要将桶 j 删除，如果删除后总的记录数比较少、桶的数目也比较少，可以考虑桶合并甚至减少桶地址表。

  • 2.1、若 i_j < i，说明桶 j 对应桶地址表的多个表项，如果散列函数是比较均匀随机的，证明此时总的记录数比较少，可以考虑减少散列前缀使用的位数。散列前缀减少 1 位，桶地址表的大小就会减半，原来两个桶需要合并为一个桶，如果桶数目减少到一定量，并且合并后的两个桶能容纳下原来两个桶的记录，则减小桶地址表的大小才是被允许的和有价值的。

    如图所示，假设当前 i 为 3，每个桶最多存储 4 条记录，桶 j 为 桶 0，其余说明同上。

  缩位之前如图：

  缩位之后如图：

• 2.2、若 i_j = i，说明桶 j 只对应桶地址表的一个表项，这时候若桶合并后的桶记录较少，可以考虑桶合并。

  如图所示，假设当前 i 为 3，每个桶最多存储 4 条记录，桶 j 为 桶 0，其余说明同上。

 桶合并前，桶 1 删除了记录后为空，可以选择跟桶 0 合并，桶记录共同前缀减 1 位。

 桶合并后如图：

五、动态散列和静态散列的比较

可扩充散列的优点：

• 1、性能不随文件增长而降低，通过创建更多的桶来保证检索速度。
• 2、空间开销小，虽然增加了桶地址表，但不用提前为增长的数据分配过大的空间造成浪费。
• 3、可动态分配桶，充分利用存储空间，并且每次对桶进行重新调整时，一次只局部调整一个桶，而不是对所有记录重新计算散列值分配桶的全局调整，每次调整开销较少，对整体使用微乎其微。

六、散列的缺陷

  散列不适用于范围查询，比如 where xxx between c1 and c2、xxx > c 这种操作，因为散列用作索引时是一种辅助索引，而不是顺序索引，顺序索引比较适合用来处理范围查询。

  对顺序索引来说（比如 B+ 树），以 between c1 and c2 为例，只要找到第一个 ≥ c1 的数据所在的页，以及最后一个 ≤ c2 的数据所在的页，这两页中间的所有页中的数据，都是满足查询条件的数据。

  而对于散列来说，满足条件的数据分散在不同的桶中，且桶中的数据不是按照搜索码顺序存储的，这意味着，可能要找到所有的桶，并逐一比较桶中的所有数据才能筛选出满足查询条件的记录，效率低下。