数据存取_哈希索引.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 存取 索引
限制150内