位图索引

这是一种建立在单个键上的特殊类型的索引。但是，它被设计用来快速查询多个键。在应用位图索引之前，我们需要按顺序排列记录。这使得从块中获取特定记录变得简单。此外，在文件块中分配它们也变得容易。

位图索引结构

“位图”一词由“位”和“图”组成。“位”是计算机系统中最小的数据单位。“图”意味着组织事物。因此，位图就是以数组形式映射位。在一个关系中，每个属性都为其值携带一个位图。位图有足够的位数来为块中的每个记录编号。

例如，考虑一个关系 *Student_record*，我们希望找出英语成绩大于 40 的女性和男性学生。性别对应的位图如下所示：

如果记录 i 的值为 Mr，则表示位图中的第 i 位将设置为 1。Mr 在位图中的所有其他位都将设置为 0。类似地，在女学生的情况下，相同的步骤继续进行。如果对于某个记录 j，其值设置为 Ms，则表示位图中的第 j 位将设置为 1。Ms 的所有其他位都将设置为 0。现在，如果用户希望检索女性或男性学生（即值为 Mr 或 Ms）的单个或所有记录，则只需要读取关系的全部记录。读取后，选择 Mr 或 Ms 的所需记录。

然而，位图索引不允许快速选择记录。但它允许用户读取并只选择所需的记录。如上例所示，用户只选择了女性或男性学生的所需记录。

位图索引的用途

包括上面示例中的一个，位图索引有以下用途：

• 它使用户能够仅从关系中读取和选择所需的记录或数据。
• 它对于基于多个键进行选择很有用。
• 位图索引有助于计算满足选择要求的记录数量。这意味着它便于计算符合用户选择标准的元组。
• 位图索引在执行数据分析查询方面既有用又有必要。
• 单个位图的大小小于 1%。因此，其大小小于关系。例如，关系中的一条记录为 100 字节，关系占内存空间的 1%。因此，单个位图占关系占用空间的 1/8。

记录的删除和插入

• 从关系中删除记录会扰乱记录的顺序。被删除的记录会在其他记录之间产生空格。
• 通过移动其他记录来填充这些空格是可能的，但这是一项昂贵的任务。
• 存在位图是解决此问题的一种方法。通过存储存在位图，我们可以识别已删除的记录。
• 在存在位图中，如果记录不存在，则其位值为 0，否则为 1。
• 记录的插入具有成本效益。这是因为插入记录不会影响其他记录的顺序。
• 用户可以通过简单地替换被删除的记录或将记录追加到 EOF（文件末尾）来插入记录。

位图操作的实现

高效实现位图操作更好。

• 交集操作

两个位图的交集可以通过使用 for 循环来实现。循环的第 i 次迭代执行两个位图中第 i 位的 AND 运算。为了加速交集操作，请使用按位 AND 指令。这是因为一个字由 32 或 64 位组成，具体取决于计算机体系结构。因此，使用单个按位 AND 一次执行 32 或 64 位的交集很容易。

• 并集操作

位图并集用于计算两个位图的 OR。为了执行并集操作，我们一次对 32 或 64 位使用按位 OR 指令。

• 取反操作

补集操作用于执行取反操作。这是通过对位图的每个位取补集来完成的。但是，如果某些记录已被删除，则位图的补集是不够的。发生这种情况是因为，在原始位图中，对应于这些不存在记录的位将为 0。但在补集中将变为 1。为此，请执行补集位图与存在位图的交集，以确保对应于已删除记录的位必须关闭为 0。相同的问题也发生在空值上。因此，执行补集位图与空值位图的补集的交集操作。

注意：我们可以将位图与 B+ 树一起用作 B+ 树叶节点上频繁出现的值的压缩存储机制。