《数据库系统概念》15-可扩展动态散列

静态散列要求桶的数目始终固定,那么在确定桶数目和选择散列函数时,如果桶数目过小,随着数据量增加,性能会降低;如果留一定余量,又会带来空间的浪费;或者定期重组散列索引结构,但这是一项开销大且耗时的工作。为了应对这些问题,为此提出了几种动态散列(dynamic hashing)技术,可扩展动态散列(extendable hashing)便是其一。

一、可扩展动态散列

A)用一个数组来存储桶指针的目录,数组的位数为2的D次方,桶的容量为2的L次方,D和L分别称为全局位深度和局部位深度。每次发生桶溢出时,溢出桶分裂,容量变为2的L+1次方,其它桶的容量保持不变,同时数据目录的深度变为D+1。扩展容量时,只是调整了局部的桶容量和目录的容量,性能开销比较小。

上图中,目录深度为2,目录项有4个。然后开始插入数据d1和d2,假定h(d1)=13、h(d2)=20,由于13=1101,且全局位深度为2,则根据后两位01确定应插入b桶,b桶有空间,可直接插入。20=10100,应插入a桶,但a桶以及满了,于是开始分裂,a桶的局部位深度变为3,容量扩展为8,如果扩展后的局部位深度超过了全局位深度,则全局位深度等于这个最大的局部位深度,于是全局位深度也随之变为3。

如上图所示,a桶分裂为a1、a2,目录变为三位,对原来a桶中的元素进行重组,由于目录位多了一位,要根据000、100来分别存储到a1、a2桶。虽然目录发生了翻倍,但未进行分裂的桶的局部深度仍然为2,所以会有多个目录项指向这些桶,比如001、101的后两位都是01,都指向b桶。

B)对于查找操作,根据当前的全局位深度,通过目录直接定位到桶地址,随后在桶内部逐一查找。

C)对于删除操作,与查找操作类似,删除元素后,如果发现桶变为空,可与其兄弟桶进行合并,并使局部位深度减一。如果所有的局部位深度都小于全局位深度,则目录数组也进行收缩。

二、静态散列与动态散列对比

与静态散列相比,动态散列的主要优势在于其性能不会随着记录数增长而下降,另外还具有最小的空间占用。缺点在于它会额外增加一次查询定位,因为在查询bucket本身前,需要先查找目录来定位bucket。

另一种动态散列技术-线性散列(linear hashing)可以避免额外的查询定位,但可能这种方式需要更多的溢出桶,日后学习。

三、顺序索引与散列的适用场景

每种索引结构都有其优缺点。如果是select * from a where b=c这样的定值查询,散列比顺序索引跟适合,顺序索引会随着记录数的增加而性能降低,散列则相对稳定。而对于where b>c and b

学习资料:Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan

https://www.cnblogs.com/kegeyang/archive/2012/04/05/2432608.html

欢迎关注公众号【菜鸟程序员成长记】

本文来自企鹅号 - 菜鸟程序员成长记媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏每日一篇技术文章

OpenGL ES _ 高级03_调试工具

921
来自专栏LET

谈谈3D Tiles(2):数据结构

3994
来自专栏Petrichor的专栏

.jpg & .jpeg 区别

1173
来自专栏利炳根的专栏

学习笔记TF063:TensorFlow Debugger

TensorFlow Debugger(tfdbg),TensorFlow专用调试器。用断点、计算机图形化展现实时数据流,可视化运行TensorFlow图形内部...

6290
来自专栏企鹅号快讯

深度学习系列教程(六)tf.data API 使用方法介绍

"玩转TensorFlow与深度学习模型”系列文字教程,本周带来tf.data 使用方法介绍! 大家在学习和实操过程中,有任何疑问都可以通过学院微信交流群进行提...

3477
来自专栏吉浦迅科技

TensorFlow版本号升至1.0,正式版即将到来

2015年11月份,谷歌宣布开源了深度学习框架TensorFlow,一年之后,TensorFlow就已经成长为了GitHub上最受欢迎的深度学习框架,尽管那时候...

3719
来自专栏HansBug's Lab

算法模板——Dinic最小费用最大流

实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

5146
来自专栏腾讯移动品质中心TMQ的专栏

【腾讯TMQ】基于模型的自动化测试工具:GraphWalker

概述GraphWalker就是一个基于测试模型的用例生成工具。它主要应用于FSM, EFSM模型。可以用来它直接读取FSM, EFSM图形模型、json模型、生...

1.1K0
来自专栏和蔼的张星的图像处理专栏

DSP图像处理

最近着手把CSK移植到DSP中,先看一些DSP中图像处理的一些例子,第一件事当然就是怎么把图像数据倒入CCS工程中了,去年倒是用过一点CCS,再拿起来已经忘得差...

2422
来自专栏机器之心

业界 | 谷歌正式发布TensorFlow 1.5:终于支持CUDA 9和cuDNN 7

3446

扫码关注云+社区

领取腾讯云代金券