1-4 散列索引在线视频

下面我们来介绍另外一种索引结构，叫做散列索引

那么散列索引呢，和散列文件是一样的

只是它是将搜索码值作为散列函数的参数

然后通过哈希函数将记录分布到若干个桶中

那么查找的时候，我只要给出搜索码值

就可以直接定位到相应的地址空间

所以也叫直接存取，这样的一种索引方式

那么，我们在散列索引中要根据桶的数量是否固定

可以把这个散列索引分为静态散列和动态散列

那么现在呢，随着数据库规模的不断增加

而且数据库里面经常要不断的进行插入和删除元组

所以呢，动态索引一般来说使用的比较多

那么动态索引又被扩展成不同的形式

目前比较常用的有可扩展散列，线性散列和分段散列

我们主要给大家稍微介绍一下可扩展散列技术

其他两种技术同学们可以自己去学习

那么可扩展散列它是一种什么样的散列技术呢

我们看一下它的要求，那么可扩展散列的要求呢，有这样几条

第一条，桶的数量要随着记录的增加而增加

随着记录的减少而减少，但它的总的大小一定是2的幂次方

也就是说，它只能是2,4,8等等这样下去

第二条要求呢，就是多个桶可以共享存储块

第三条要求呢，桶数量的确定

在可扩展散列里面桶的数量的确定是以这样的一种方式

它通过将散列函数的值转化成N个长度的二进制位

然后它使用前i位来进行表示

而这个i就可以随着记录的增加而增加，随着记录的减少而减小

那么下面我们用一个例子来进行说明一下

比如说我们把一个按照图的这个的一个表

我们把一个搜索码值，比如姓名

那么被散列而且二进制化生成一个长度为4的串

如图所示，那么这个4的串就是从0000一直到1111

那么如果使用前i位的话，比如说i=1

也就是说使用这个串的前一位，那就说明有两个桶

一个是零号桶，一个是一号桶

那么这个时候呢，凡是以0为开头的记录就可以放到0号桶中

以1开头的记录就可以放到1号桶中

我们假设一个桶，只有一个磁盘块，每个磁盘块只容纳两条记录

那么我们看一下这个例子，我们就可以把以0开头的放在0号桶中

以1开头的放在1号桶，我们发现1号桶目前已经满了，是吧

这个时候如果我再插入一条新的记录

比如说这个记录经过散列之后，它是1010

那么它要插入到1号桶里面去，但是这个时候这个桶已经满了

那满了怎么办呢，我们就需要对桶进行分裂

也就是说我们需要使用这个二进制的前二位

也就是前两位来表示桶，也就是i等于2

那么当我使用前两位来表示的时候，这个桶就变成了四个

也就变成了00号桶，01号桶，10号桶和11号桶

那么这个时候呢，我们看一下由于我们插入的是以1开头的，是吧

那么不是以0开头的，所以以0开头的记录呢

还是只有一个，它没有增加

那么所以我新生成的以0开头的这个，比如说00和01

这两个桶只有一条记录，是吧

这个时候它就可以共享一个磁盘块

然后我们在后面用一个1来标识

说明这个桶中的记录只用前一位来进行表达

那么对于分裂之后的后两个桶，10和11

因为目前已经插入了新的记录

比如我把1010插入到10号桶中

那么我把原来的1100这条记录移到了11桶里面去

那么这样的话，这两个桶里的记录都是以前两位来进行标识

所以后面用2来表示，那么现在如果我要再插入一条记录

比如说1011，它要插入到10号桶里面

如果这个桶现在我们看已经满了，是吧

那也就是说如果要插入1011，那么这个桶接着还要进行分裂

那么可扩展散列实际就是这样一个分裂过程

以此类推的这样一个分裂过程

那么我们从可扩展散列的这样一个分裂过程我们可以看到

那么可扩展散列实际上它是有优点的

它的优点就是它可以直接寻址，支持随机查找

也就是说只要我给出一条记录

通过哈希函数散列之后，我就可以直接定位到这条记录所在的地址

也就是它的桶地址

那么到此为止呢，我们关于数据文件的组织和数据的索引结构

我们就给大家介绍完了

那么这一章的重点呢，大家要掌握数据文件的组织方法

尤其是掌握顺序文件和散列文件的组织方法

另外一个呢，大家要重点掌握顺序文件索引和B+树索引

它的结构，它的这个维护过程，以及它的使用领域

那么后面的作业就是大家要自学一下

一些分段散列以及目前在数据库领域里面人们讨论的比较热烈的一些

比如像α树索引，kd树索引，四叉树索引等等这样一些索引技术