读书频道 > 网站 > 网页设计 > 大数据 : 互联网大规模数据挖掘与分布式处理 : 第2版
1.3.3 索引
15-07-08    下载编辑
收藏    我要投稿   
本书由斯坦福大学Web 挖掘课程的内容总结而成,主要关注极大规模数据的挖掘。主要内容包括分布式文件系统、相似性搜索、搜索引擎技术、频繁项集挖掘、聚类算法、广告管理及推荐系统、社会网络图挖掘和大规模机器立即去当当网订购

给定某种对象的一个或多个元素值,索引是一种能够支持对象高效查找的数据结构。最常见的一种情况是对象都是记录,而索引按照记录中的某个字段来建立。给定该字段的值v,基于索引能够快速返回该字段值等于v的所有记录。例如,假定有一个由一系列三元组<姓名, 地址, 电话号码>组成的档案记录表以及基于电话号码字段建立的索引。当给定一个电话号码时,基于索引就能快速找到包含该号码的一条或者多条记录。

实现索引的方法有很多,这里并不打算给出全面的介绍。参考文献部分给出了扩展阅读的建议。但是,哈希表是一种简单的索引构建方法。哈希函数的输入键是用于建立索引的一个或者多个字段。对于某条记录来说,哈希函数会基于其中哈希键的值进行计算,然后将整条记录分配到某个桶中,而桶的号码取决于哈希函数的结果。举例来说,这里的桶可以是内存或磁盘块中的一个记录表[ 由于多条记录可能会哈希到同一个桶中,因此每个桶通常由多条记录所组成的表构成。——译者注]。

于是,给定一个哈希键值,我们可以先求哈希函数的值,然后根据该值寻找相应的桶,最后只须在该桶中寻找包含给定哈希键值的记录即可。如果我们选取的桶数目B和档案中所有记录的数目大体相当,那么分配到每个桶的记录数目都会较小,这样在桶内部的搜索速度就会很快。

例1.5 图1-2给出了包含姓名(name)、地址(address)和电话号码(phone)字段的记录的内存索引结构的大概样子。这里,索引基于电话号码字段构建,而桶采用链表结构。图中展示电话号码800-555-1212所对应的哈希到桶号码为17。对于桶头(bucket header)构成的数组,其第i个元素实际上是第i个桶对应链表的头指针。图中展开了链表中的一个元素,它包含姓名、地址和电话号码字段的一条记录。事实上,该元素对应记录包含的电话号码正好是800-555-1212,但是该桶中的其他记录可能包含也可能不包含这个电话号码,我们只知道这些记录中的电话号码经过哈希变换之后结果都是17。


 



点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.3 功能
下一篇:1.5 小结
相关文章
图文推荐
JavaScript网页动画设
1.9 响应式
1.8 登陆页式
1.7 主题式
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做最好的IT技术学习网站