Java教程

(P22-23)数据库系统下-散列索引

本文主要是介绍(P22-23)数据库系统下-散列索引,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

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

1.散列

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

  • 目标:选择一个合适的散列函数,将一个Record集合(每个Record都包含一个关键字k)均匀地映射到M个桶中。即:对于集合中任一个关键字,经散列函数映射到地址集合中任何一个地址的概率是近乎相等的。
    在这里插入图片描述

2.散列索引

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

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

  • eg:假设 1存储块可存放2个键值及其指针,M=4;1个桶为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过大,则浪费; M过小,则将产生更多的溢出桶,增加散列索引检索的时间

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

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

4.动态散列索引

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

这篇关于(P22-23)数据库系统下-散列索引的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!