文章目录

• • 1.散列
  • 2.散列索引
  • 3.散列的问题
  • 4.动态散列索引

1.散列

有M个桶，每个桶是有相同容量的存储地(可以是内存页，也可以是磁盘块)
散列函数 h(k)，可以将键值k映射到 {0,1,…,M-1}中的某一个值
将具有键值k的记录Record(k)存储在对应h(k)编号的桶中

• 目标：选择一个合适的散列函数，将一个Record集合(每个Record都包含一个关键字k)均匀地映射到M个桶中。即：对于集合中任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是近乎相等的。
  

2.散列索引

内存数据可采用散列确定存储页， 主文件可采用散列确定存储块， 索引亦可采用散列确定索引项的存储块

Ｍ个桶。 一个桶可以是一个存储块，亦可是若干个连续的存储块。

• eg：假设 1存储块可存放2个键值及其指针，M=4;1个桶为１个存储块
  h(x)满足：
  h(e)=0； h(b)=h(f)=h(s)=1
  h(g)=2； h(a)=h©=3
  

• 问：如何查询键值 a的索引项？
  计算 h(a)=3
  读取 3号桶，获得键值a的索引项.
  需要1个磁盘块读取

• 问：如何插入键值d的索引项?
  计算h(d)=2
  如2号桶有空间，则将索引项d插入2号桶中

• 问：如何插入键值s的索引项？
  计算 h(s)=1
  1号桶无空间，则申请一溢出桶，插入s
  

• 如何删除键值f.
  计算h(f)=1
  删除1号桶中的键值f
  将溢出桶中的s合并到主桶中，删除溢出桶
  

3.散列的问题

散列索引的目标：

• 最好是没有溢出桶，每一个散列值仅有一个桶。读写每一个键值都只读写一个存储块。

均匀分布如何做到？

• 期望将所有数据分布均匀地存储于M个桶中，使每一个桶的数据成为具有某种特征值h(k)的数据集合。—散列函数的选择。

桶的数目Ｍ如何确定？

• 在键值几倍于桶的数目时，每个散列值都可能多于一个桶，形成一个主桶和多个溢出桶的列表，此时要二次检索：先散列找到主桶号，再依据链表逐一找到每个溢出桶。—桶的数目的确定。
  

桶的数目M是固定值----静态散列索引

• 如果桶的数目M不变： M过大，则浪费； M过小，则将产生更多的溢出桶，增加散列索引检索的时间

桶的数目随键值增多，动态增加----动态散列索引

• h(k)是和桶的数目M相关的。 M的变化会否影响原来存储的内容呢？
• 是否需要将原来已经散列-存储的数据按新的桶数重新进行散列-存储呢？

4.动态散列索引

可扩展散列索引解决动态散列索引