Hash索引(数据库)
时间：2022-12-25 22:30:01 | 来源：信息时代
时间：2022-12-25 22:30:01 来源：信息时代
Hash索引 : 也称散列,其基本思想是利用Hash函数把检索字段的值映射到桶号,从而找到待查数据项所在的页。
Hash索引按照搜索键对数据项进行Hash,如图1所示。
图1 静态Hash
Hash索引将搜索键及相应指针组织成Hash文件结构。Hash索引的构造如下,将Hash函数作用于搜索键以确定对应的桶,然后将此搜索键及相应指针存入此桶(或溢出桶,如果对应的主桶页面已经放满)中。Hash索引既可用来组织文件结构也可用于索引结构。严格地说,Hash索引应该只表示辅助索引结构,而不能作为主索引结构,因为Hash索引不能保证索引键值之间的顺序关系。
由于函数本身所具有的性质,不同的索引键值可能被Hash到相同的值,即同一个桶中,这种现象称为Hash冲突。解决Hash冲突的一个自然的办法是使用如图1所示的溢出页面链来保存发生冲突的索引记录。一个Hash索引的查询性能的好坏取决于溢出页面链的长度,因此在溢出页面链的查找时间是线性的。溢出页面链的长度实际上取决于Hash函数的散列能力,因为Hash函数的散列能力越强,索引记录就越能均匀地散列到各个主桶页中,这样溢出页面链的长度就短。
在Hash索引上的随机查询过程非常简单。首先使用相同的Hash函数将查询键值进行Hash,得到该查询键值所在的桶号,然后在对应的主桶页中进行查找,如果找到就返回结果,如果找不到就顺着对应的溢出页面链查找,直到找到或到达溢出页面链末端为止。
在线咨询
