数据存取_哈希索引.ppt

《数据存取_哈希索引.ppt》由会员分享，可在线阅读，更多相关《数据存取_哈希索引.ppt（23页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据存取数据存取 hash索引索引郗岳学号：2011020884指导老师：陈梅老师hash索引索引lhash索引简介l静态hashl可扩展hashl两个经典问题hash索引简介索引简介lHash：译“散列”，也译“哈希”，一种将任意长度的输入压缩到某一固定长度的输出的方法；lHash函数:将查找键为参数并计算出一个介于0到N-1的整数，其中N是桶的数目；静态哈希静态哈希u桶数组：一个序号从0到N-1的数组中包含N个存储块，每一个对应数组中的一个桶；uH：哈希函数u溢出链静态静态hash的插入与删除的插入与删除静态哈希静态哈希l理想情况下查询只需要一次磁盘I/O，且文件的插入和删除操作也只需要两

2、次I/O（读和写）。l静态哈希的桶数固定。如果一个文件缩减太大，会浪费很多空间；如果文件增长很大，将产生较长的溢出链，导致性能下降。可扩展哈希可解决这一问题可扩展哈希可解决这一问题可扩展哈希可扩展哈希lSituation：考虑静态哈希文件，现在需要向一个满的桶中插入一个查找键为K的新记录。l解决方案1：增加一个溢出页。l解决方案2：重新组织文件，把桶数加倍，并在新的桶集合中重新分配项。l方案2的缺点：为完成重组，不得不读整个文件，并且不得不写回二倍的页数。lIdea：使用一个指向桶的指针目录，仅仅通过目录加倍和分裂溢出桶来实现桶数的加倍。可扩展哈希可扩展哈希可扩展hash表简介：它在静态has

3、h结构中主要增加如下：l引入了一个间接层，用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶；l指针数组可以增长，它的长度总是2的倍数；lHash函数h为每个键计算出一个K位二进制序列，该K值足够大，无论何时桶的数目都是使用从序列末尾开始的若干位。可扩展哈希可扩展哈希-实例实例l目录由4个元素的数值组成。l要定位一个数据项，首先在查找键上应用哈希函数，然后从它的二进制表达中取后两位得到一个0到3之间的数，根据这个数在目录位置上的指针指向期望的桶。定位哈希值为5（二进制101）的数据项，查找目录元素01，然后沿着指针找到数据页（桶B）。可扩展哈希可扩展哈希-插入插入l插入l定位

4、桶，如果桶未满，直接插入；l如果桶满，则需要分裂（分配新的页，重分布）。如有必要，需加倍目录。插入插入h(r)=20的目录项的目录项r之前之前插入插入h(r)=20的目录项的目录项rReview：可扩展哈希：可扩展哈希可扩展hash表简介：它在静态hash结构中主要增加如下：l引入了一个间接层，用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶；l指针数组可以增长，它的长度总是2的倍数；lHash函数h为每个键计算出一个K位二进制序列，该K值足够大，无论何时桶的数目都是使用从序列末尾开始的若干位。全局深度与局部深度全局深度与局部深度l20的二进制是10100。最后2位指明项属

5、于A或A2，最后3位指明属于哪个桶。l全局深度：在初始时，使用哈希值的i位而不是整个b位(0 i 全局深度，目录加倍，并将指针固定到分裂的映像页。DBMS如何跟踪磁盘上的空间如何跟踪磁盘上的空间l磁盘空间管理器：提供上层接口、数据单元为页l磁盘IO请求：块地址l磁盘驱动器最简单的文件组织结构最简单的文件组织结构CBAA：文件B：页C：记录页的集合如何组织成一个文件页的集合如何组织成一个文件l实现：页的链表数据页数据页数据页数据页数据页数据页首页含有空闲空间的页链表满页链表用链表组织的堆文件层次之间的联系层次之间的联系reviewlhash索引简介l静态hashl可扩展hashl两个经典问题谢谢！谢谢！