深入学习数据库——索引结构（多维）-爱上极客

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

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

类散列表方法

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

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

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

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

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

优点：数据分布比较均匀

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

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

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

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

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