(P22-23)数据库系统下-散列索引
2021/11/12 2:13:52
本文主要是介绍(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)数据库系统下-散列索引的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)