深入学习数据库——索引结构(多维)

数据库 yan loading.. 6评论

利用传统的B树或者散列表进行建立单维索引,在处理多维数据时会遇到问题。例如地理信息系统,其中数据是两维的(如经度、维度),因此利用传统索引无法高效的解决问题,所以需要多维索引。

本文主要介绍两类多维索引:类散列表方法类树方法。类散列方法包括:网格文件、分段散列;类树方法包括:多键索引、kd树、四叉树、r树。以及最后会简单介绍位图索引。

类散列表方法

网格文件

一个n维空间,每一维度是每一查找键。对每一维度进行划分,形成可以大小不等的多个空间,使每一个元组落入不同的空间中,可以让每个空间内的数目不同。

被划分后的每个空间可以看做是每个桶,落入该区域的数据放入该桶中,若溢出可以添加溢出块,不同维的值共同决定桶的位置。

优点:对于近邻查询、区域查询比较好

缺点:数据维数多时难以维护

分段散列

为每一维属性设计一个散列函数,通过该函数产生若干个二进制位。最后将这几个属性产生的二进制位拼接。

优点:数据分布比较均匀

缺点:对近邻查询、区域查询无用

类树方法

多建索引

索引的索引,树中每一次结点都是一个属性的索引

KD树

k维搜索树,是一个二叉树。所有维的属性在内结点的层间循环,所以树的不同层上的属性是不同的。

四叉树

将二维空间换分成四个正方形的区域,每个内结点对应于空间内的一个区域。

R树

B树的拓展,利用B树的某些本质特征来处理多维数据对象的数据结构。利用矩形将空间划分并利用层次结构组织多维数据对象。

位图索引

关系R有n个元组,属性F的位图索引是指一个长度为n的二进制数,它的第i位是序号为i的元组的记录值,若相同则为1,否则为0

解释:以字段F为例,共6条记录 所以定义长度为6的二进制数。第1位 代表序号为1的元组(30,foo)所以在30对应的数列中第1位是1,同理第2位是1,同理30对应的数列是11001,同理得出值为40、50的数列,从而得出F的位图索引。

位图索引的压缩

利用分段长度编码来压缩位图索引中数列的“0”。先计算“1”之前“0”的个数i,确定i的二进制表示位数j。则压缩后的表示为:j-1个”1″和一个”0″表示i的位数,后面加上i的二进制数。

例如:数列00010000 “1”前面有3个”0″,需要2位二进制数来表示”0″的个数。(即i=3 j=2) 所以前半部分为10,后半部分为11,压缩后为1011

关注<爱上极客>公众号,定期推送精彩内容!

喜欢 (6)

如未说明则本站原创,转载请注明出处:爱上极客 » 深入学习数据库——索引结构(多维)


0
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(6)个小伙伴在吐槽
  1. 过来学点儿知识,很不错,点赞
    胡杨2016-12-09 15:21 回复
  2. 我只是来看一看,好久没来了~
    尚爱思套图2016-12-14 10:17 回复
  3. 挺好的,祝你快乐
    三五营销2016-12-15 13:58 回复
  4. 让我不觉明厉啊
    特色小镇2016-12-19 15:26 回复
  5. 偶然来访,受益良多!
    三五营销2016-12-21 09:02 回复
  6. 掐指一算,这个博客能风光一百年!
    衣皇后2016-12-25 10:00 回复