利用传统的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
过来学点儿知识,很不错,点赞
我只是来看一看,好久没来了~
挺好的,祝你快乐
让我不觉明厉啊
偶然来访,受益良多!
掐指一算,这个博客能风光一百年!