数据库原理——多维索引和位图索引

在上一篇文章中看到的都是一维索引。也就是说，它们是使用单个查找键，并且按给定的查找键值来检索记录。

大多数支持多维数据查询的数据结构归于以下两类之一：

• 1、类散列表方法；
• 2、类树方法；

下面我们就分别来看看这些数据结构。

一、多维数据的散列结构

一种方法称为“网格文件”，它通常不是按维来“散列”值，而是通过排序该维的值来划分该维；另一种方法是“分段散列”，它确实散列各维，且每一维都影响桶号。

网格文件

在涉及多维数据查询时，作为最简单的数据结构之一的网格文件通常要比单维索引性能要好。

每一维上的网格线把空间分成条状，落在网格线上的点被认为是属于该网格为其 低边界 的条。

• 1、不同网格线的数目可以不同；
• 2、相邻网格线之间可有不同的长度，甚至同一维的线之间也可有不同的区间长度；

下图是年龄和薪水（二维）分布的网格文件：

在这里空间被分为了9个条状矩形。一般来说，一个矩形包括落在其左边界和下边界上的点，但是不包括其右边界和上边界的点。

网格文件的查找

空间划分成的每一个区域可以被看成是散列表的一个桶，落入该区域的每个点的记录都存放在属于该桶的块中。如有必要，溢出块可以用来增加桶的大小。

网格文件使用的桶数组维数和数据文件的维数一样。

关注 “点” 的每一个分量，并且确定该维上点在网格中的位置。 点在每一维的位置一起决定点所属的桶 。

下面是年龄和薪资对应的一个数据集：

我们根据上面的数据集构建一个网格文件：

上图中使用的桶数组维数和网格文件的维数相同，均为2。横向表示年龄，纵向表示薪水。而且在上面的例子中没有桶超过两个记录，因此不需要溢出块。

网格文件的插入

插入操作同样也遵循查找记录的过程（即多个维度来确定桶的位置），并将新记录放到查找到的桶中。当桶中有足够的空间时，直接插入即可；如果桶中没有空间，可以用如下两种方法来解决这个问题：

• 1、按需给桶增加溢出块；
• 2、 通过增加或移动网格线来重组结构；

网格文件在每一维上的条目数量可能非常大，如果那样的话，我们必须为每一维建立一个索引。索引的搜索码是该维分割值的集合。

网格文件的性能

网格文件虽然能够有任意数目的维，

但我们一直以来只考虑二维的情况。

这是因为随着维数的增加，桶的数目成指数级增长。如果网格空间大部分是空，那么将会有许多的空桶。使用网格文件的场景为：

数据分布很好，且数据文件本身又不太大

对于部分匹配和范围查询来说，由于我们需要检查许多的桶，因此磁盘I/O数可能会很大。

分段散列函数

该散列函数，它可以产生若干个二进制位，比如说k个。这k位二进制划分给各个不同的属性，比如属性A占用3位，属性B占用4位，属性C占用 k-3-4 位。

更确切的说，散列函数h实际上是一个散列函数 $(h_{1}, h_{2}, ... , h_{n})$的列表。其中每个 $h_{i}$ 运用到第i个属性，且产生 $k_{i}$位二进制位序列。

我们还是来看个例子：如果我们有一个桶数目为 10位 （注意是10位，不是10个）的散列表（1024个桶）。我们把4位分给属性a（假设属性值为A），剩下的6位分给属性b（假设属性值为B）。如果 $h_{a}(A) = 0101,\ h_{b}(B)=111000$ ，那么对应的桶号为两个二进制序列拼接的 0101111000。

二、多维数据的树结构

下面四种结构对于多维数据范围查询和最邻近查询都有用。这四种结构分别是：

• 1、多键索引；
• 2、kd树；
• 3、四叉树；
• 4、R-树；

前三种用于点集，R-树用来表示区域集合，也可以用来表示点集。

多键索引

为了能够用几个属性来表示我们数据点的不同维度，并且支持范围查询和最近邻查询。那么我们可以一棵树，该树的每一层结点都是一个属性的索引。

每一个属性对应树的一层!!!

换句话说就是“索引的索引”。下图是一个示意图：

“树根”表示第一个属性，他可以使任何类型的索引。该索引包含的内容有：索引键值，指向另一个索引的指针。在下面的例子中体现更加明显。现在我们来看一个例子，下面是各个不同的记录：

现在我们根据年龄和薪资两个不同属性来构建一个多级索引：

kd树

kd树是把二叉搜索树推广到 多维度数据 的一种 主存数据结构 。

kd树是一个二叉树。对于表示的多维度数据而言，所有维度的属性 在层间交替出现，因此不同层上的属性是不同的。

举个例子，比如用kd树来表示前面多级索引中年龄-薪资，那么第一层用来表示薪资、第二层用来表示年龄、第三层用来表示薪资、第四层用来表示年龄… 这样依次交替的出现在每一层。

kd树结点的两个特性：

• 1、 内部结点：只表示一个属性，基于该属性的划分值（小于该划分值在左子树，大于等于该划分值在右子树），以及指向左子树、右子树的指针；
• 2、 叶子结点：为一个数据块，块中存放尽可能多的记录；

下图的kd树，每一层交叉出现“年龄”和“薪资”属性。而叶子结点是存放两个记录的块。

kd树相关操作

为了实现插入，我们找到一个叶结点：

• 1、如果叶结点的块有空闲空间：我们就把新的数据点放在那里；

• 2、如果叶结点的块空间已满：我们把块分裂成两个，并根据分裂叶结点所在层的相应属性划分叶结点中的内容。最后创建一个新的内部结点：其子节点为分裂得到的新块，并且 给该内部结点一个与分裂相对应的划分值 。

  当无法进行分裂时，我们可以尝试沿另一个维读（属性）进行分裂，或者 可以使用溢出块。

比如针对上图，我们要插入一个（年龄，薪资）的记录（35，500）。从上图我们找到由（25，400）和（45，350）组成的叶结点，但是该叶结点空间已满。从上图得知第4层是根据年龄来分裂的，假如我们用年龄35来进行划分，进行分裂之后得到的kb-树如下：

对于查询操作而言：

• 1、如果当前处于属性已知的二叉树层级时，比如当前我们处于根节点，并且要查询 薪资 大于150的情形时，那么我们可以直接查找右子节点；
• 2、如果当前处于未知属性的二叉树层级时，比如当前我们处于根节点，要查询 年龄 小于50的情形时，我们就需要 查看当前层级的左右子节点 进行比较，然后再进行选择；
• 3、对于范围查询而言，如果范围跨越了结点的划分值，那么我们就必须要考察两个子结点；

四叉树

在一个四叉树中，每个内部结点对应于二维空间中的一个正方形区域。

• 1、如果一个正方形中的点数小于等于一个块能够存放的记录数量，那么我们就将该正方形看作是树的叶结点；
• 2、如果一个正方形中的点数大于一个块能够存放的记录数量，那么我们就把该正方形看作内部结点，它的子节点对应于它的四个象限 ；

下图是四叉树结点的区域分布：

为什么说四叉树，在二维平面上以原点划分4个象限。比如上图的（50，200）点就对应了四个象限，这里我们加入一个数据块只能存放两个记录。也就是当一个象限内的记录多余2个时，我们需要根据记录在空间内的分布情况划分子空间。新找一个原点，比如（25，300），然后同样划分四个象限。

下图是根据上面的记录分布构造的四叉树：

从上图我们可以看到，分裂了两个子象限，其原点分别为（75，100）和（25，300）。结点（75，100）的“东南”指针为空，结点（25，300）的“西南”和“西北”指针为空。这里还只是2维的情况（即从年龄和薪资两个维度），

当维度更大之后，出现空指针的情况会越加明显。

R树

R树表示由二维或者更高维度区域组成的数据，我们把它称为 数据区 。R树的一个内部结点对应于某个内部区域，“区域”可以是任何形状，但实际上大多为矩形或者其他简单地形状。

R树结点的键位置上含有子区域，它表示结点的子结点。子区域之间可以有重叠，但尽量做到重叠区域更小。

根节点关联着整个区域。

R树查询操作

我们从根结点开始，然后确定其子结点区域内包含有目标点：

• 1、如果当前没有区域包含目标点，那么查询失败结束；
• 2、如果有至少一个子结点区域包含目标点，那么我们需要递归地查询子孙结点区域。直到找到一个或者多个叶子结点；

也就是说：

最终的数据存放于叶子结点中；

R树插入操作

当我们向R树中插入一个新区域时，我们从根开始找到一个适合新区域结点的子区域。如果多余一个子区域可供插入，那么我们就看哪个子区域扩大的尽可能少，以此递归地进行下去；

如果不存在包含新区域的子区域，那么我们就得扩大其中一个子区域用于存放新区域；

最后到达叶结点时，查看该叶结点是否有足够的空间。如果没有足够的空间，我们必须要分裂叶结点，

分裂之后的叶结点必须要覆盖原始叶结点的所有数据区；

这个插入过程和B+树类似，从叶子结点分裂，直到某个父结点有空间则结束分裂；

三、位图索引

位图索引是一个长度为n的位向量集合。它能够表示n个记录。

例如有一个由name、age两个字段组成的记录。此时存在6个记录：

那么对于字段name而言的位图是从左到右生长的，即左边表示第一位：

解释一下foo对应的位图100100，第1位为0表示在上面的表格中下标为1的name为foo，第2位为0表示在上面的表格中下标为2的name不为foo。以此类推下去。

我们也可以看看字段age每一个值对应的位图：

规律和上面的一样。总的来说就是对于字段F（比如上面的”name”字段）的位图索引而言，如果第i个记录的字段F为v（比如上面的”foo”）。那么对应于值v的位向量在位置i上的取值为1；否则该向量的位置i上的取值为0；

位的总数是记录个数和取值数（字段取值）的乘积。

位图索引的优势

位图索引的优势是它们允许我们在许多情况下高效地回答 部分匹配查询 。下面我们来看个例子：

1
2
3

SELECT title 
FROM Movie
WHERE studioName = 'Disney' AND year = 2005;

那么我们针对字段studioName和字段year建立位图索引，那么我们就可以得到Disney对应的位向量A，year对应的位向量B。现在我们对位向量A和B求交集，即两个位向量做按位与的操作得到一个位向量C。然后我们观察位向量C的二进制位，当某一位值为1时就表示该记录满足上诉约束条件的结果；

位图索引也能够帮助回答范围查询。下面来看个例子，还是上面一直用的“薪资-年龄”表格：

我们为字段年龄建立位图索引：

现在为薪水字段建立位图索引

我们以上述为基础，找出年龄在 45~55且薪水范围在100~200之间记录。首先找到范围内的年龄向量，并对它们进行按位或操作得到一个新的向量：

1
2
3
4
5

000110000000
|
000001111000
=
000111111000

就得到符合年龄的记录。
然后找到符合薪水的向量，同样对他们进行按位或操作得到一个新向量：

1
2
3
4
5
6
7
8
9

000000100000
|
000000010000
|
000000000010
|
000000000001
=
000000110011

现在我们对上面的两个新向量进行按位与来求交集：

1
2
3
4
5

000111111000
&
000000110011
=
000000110000

也就得出第7个和第8个记录是符合约束条件的。

使用位图向量求交集时用按位与，并集用按位或！！！

压缩位图

假定我们有n个记录的文件，该文件存在字段F。该字段F在文件内有m个不同的值。现在我们要对字段F建立位图索引，那么就就需要 mn 位的二进制位。随着m或者n的增大会导致位图索引所占的空间变大。

一个常见的压缩方案叫做 分段长度编码 ：段是由 i个0 后跟 1个1 组成的序列。通过对整数i适当地二进制编码来表示一个段。然后把每个段拼接在一起，得到的位序列就是整个位向量的编码。

确定位数、编码

下面我们先来看看如何适当地来表示 i，具体的方案如下：

• 1）、首先需要确定 i 的二进制表示由多少位；位数近似地等于 $j = log_{2}i$ (j表示i的二进制位数)。那么就用j-1个1和一个0来表示i所占的位数。
• 2）、然后我们在后面加上二进制表示；

比如对于 i = 13，那么$log_{2}13 \approx 4$，也就是说j为4.那么前面的位数需要 $4-1=3$ 个1和1个0： 1110。而13的二进制表示为1101。因此最终的编码为：

1

11101101

特殊的情况：

当i=0或者i=1时j为1。那么我们以0开始且0后面为表示 i 的 一位 二进制数；

解码

而根据编码来解码整数 i 也是很简单的。当我们处于某个整数 i 编码位序列的开始位置上：

• 1）、向前扫描到第一个0，以此来确定位长度（即 j 的值）；
• 2）、我们查找位序列后的 j 位，这些二进制数就用来表示整数 i ；

比如我们现在有一个二进制位序列：11101101001011。我们从左到右扫描直到遇到第一个0：

• 首先扫描到3个1，那么后续的4个二进制位 1101 用来表示整数13；
• 接着马上看到一个0，即后续的1位二进制 0 表示整数 0；
• 最后扫描到1个1，那么后续的2个二进制位11用来表示整数3；

确定位序列

现在我们解码了整数 i 。那么我们就需要根据上面提到的一句话 由i个0和1个1的位序列来组成段 。那么得到的最重的位向量为：

1
2

/// (13个0，1个1) + (0个0，1个1) + (3个0，1个1)
00000000000001     1              0001

上面讲这么多都是为了能够压缩上面这个位向量的那一系列二进制位。每个这样解码的位向量都以 1 结尾。且任何的尾数0串都不会被恢复。

既然位向量中0表示相应的记录不在所描述的集合中，我们甚至不必知道记录的总数，并且可以忽略这个尾数0串。

例子🌰

下面是2个年龄的原始位向量：

现在我们需要对这个三个位向量进行压缩。

对于年龄45：

1
2

0001           1           0000000
(3个0、1个1) + (0个0、1个1)  全是0直接省略

那么得到的数字序列为 (3,0)，这里i=3、0，那么编码的结果为 1011 00。也就是说位向量 000110000000 被压缩为 1011 00。

对于年龄50：

1
2

000001         1             1             1           000
(5个0、1个1) + (0个0、1个1) + (0个0、1个1) + (0个0、1个1)  全是0直接省略

那么得到的数字序列为5000，这里i=5、0、0、0，那么编码的结果为 110101 00 00 00也就是说位向量 000001111000 被压缩为 110101 00 00 00。

总结：

1、根据原始数据中0的个数来确定需要压缩的位数；

2、根据得到的压缩位数，对这个数字求对数，并进行编码；

位图索引的管理

位图索引相关的三个问题：

• 1、 查找位向量：当想要查找一个给定值的位向量，或者给定范围内的值对应的多个位向量时，我们如何有效地找到它们；

  把位向量看成记录，它们的键是对应于该位向量的字段值。然后任何辅助索引技术都可以使我们有效地按值找到它们的位向量。
  我们存储位向量时，把他们当做可变长记录。这是因为随着数据文件中记录的增加，它们一般会增长。

• 2、 查找记录：当我们已经选择好回答查询查询的记录集时，我们如何有效地检索记录；

  我们可在数据文件上创建辅助索引（稠密索引，无序，桶），它的索引键是记录号。

• 3、 更新位图索引：当出现插入或者删除时，如何调整给定字段的位图索引；

数据文件修改的处理

数据文件的改变需要位图索引也做相应的改变。

对于插入而言，我们保留一个可用记录号，并且把它分派给新纪录。对于每个位图索引，我们必须确定新纪录在相应字段的值，并且在该值的位向量后面加1。而需要向其他位向量后面加0，而对于上面提到的压缩技术而言，加0操作完全可以省略；

当新纪录中有一个索引字段是首次出现的，那么我们就需要给这个字段增加一个新的位向量，然后根据位向量的值插入到索引结构中。

最后是将位图索引字段的值从旧值更改为新值，那么我们就需要修改旧值对应的位向量：即该向量相应位置的1更改为0；同样也需要修改新值对应的位向量：如果新值之前尚未存在过，那么就是上面的插入逻辑；如果新值之前存在，那么就需要将该向量对应位置的0更改为1。

后记

在本篇文章中主要是记录了一下多维索引和位图索引，它们存在目的主要是为了处理范围查询。其中比较重要的多维树形结构包括有多级索引（一层表示一个字段）、kd树（不同属性交替出现）、四叉树和R树。最后就是位图索引，它的主体是某一个字段，然后根据每个记录对应字段值构造不同的位图，即对同一字段在不同记录中查找不同的值。以及根据位图索引的压缩操作和解码操作。