一篇带给你索引技术之位图
要点
- 位图基本算法及其应用场景。
- 位图算法的优化实现。
概述
位图算法,是指使用一个bit位来表示数据状态。通常应用于海量数据去重、海量数据计算及判断海量数据中是否存在某个数据的场景中。
以海量数据中是否存在某个数据的应用场景为例,假设用16个bit位,分别表示数字0-15。bit位的值,表示该数字是否存在,0表示不存在,1表示存在。如上图所示,在该数据集合中,存在的元素有1、2、6、10、11和13。
可以发现,在数据比较稠密的情况下,位图算法能够节约存储空间,如图中,使用2个字节便可以表示16个数字,同时可以在O(1)的时间复杂度下,判断是否存在某个数字,大大提高了计算速度。
但是,在数据稀疏时,存储空间会存在一定程度的浪费。由于位图算法中,位图空间的大小是一定的,并不会根据存储数据量的大小而改变。因此,当位图空间中存储的数据量很小时,大量地位图空间是空闲的,存在大量的浪费。
算法实现
位图算法在主流开发语言中,都有对应的实现。基本操作主要有写入、查询、删除、交集、并集等。下面通过一个示例来了解一下,位图算法的实现。
位图结构定义例子使用char类型数组来存储位图信息(通常的实现中,会使用长整型数组),一个char类型有8个bit位。定义结构如下:
// 为了简化问题,LEN必须定义为CHAR_SIZE的倍数
#define LEN 16
#define CHAR_SIZE 8
typedef char BitSet[LEN/CHAR_SIZE];
写入在某个bit位写入数据时,首先通过整除,计算出该bit位在数组的哪个下标,然后,用取余计算出char元素中的哪个bit上。最后通过或运算将对应位设置为1。
// 置bit位
void set(BitSet& bits, int pos) {
// 查找对应数组下标
int unit = pos / CHAR_SIZE;
// 查找在字节中的bit位
int p = pos % CHAR_SIZE;
// 通过与运算实现对应bit位置1
bits[unit] = bits[unit] | (0x1 << p);
查询同写入操作,先计算出bit位置,查找到对应的bit位,然后返回该位置的数值。
// 查询bit位
int get(BitSet& bits, int pos) {
// 查找对应数组下标
int unit = pos / CHAR_SIZE;
// 查找在字节中的bit位
int p = pos % CHAR_SIZE;
// 通过与运算实现对应bit位置1
return (bits[unit] & (0x1 << p)) > 0 ? 1 : 0;
}
删除首先查找到对应的位置,然后通过与运算将该位置清空。
// 清空bit位
void clear(BitSet& bits, int pos) {
// 查找对应数组下标
int unit = pos / CHAR_SIZE;
// 查找在字节中的bit位
int p = pos % CHAR_SIZE;
// 通过与运算实现对应bit位置1
bits[unit] = bits[unit] & (~(0x1 << p));
}
交集对数组逐个元素进行或运算。
// 求位图b1和b2的并集
void unionn(const BitSet& b1, const BitSet& b2, BitSet& res) {
for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
res[i] = b1[i] | b2[i];
}
}
并集对数组逐元素进行与运算。
// 求位图b1和b2的交集
void inter(const BitSet& b1, const BitSet& b2, BitSet& res) {
for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
res[i] = b1[i] & b2[i];
}
}
在生产实现时,可能会进行一些优化:
- 使用CPU指令优化,如SSE等,一次能进行128位的运算,可以提高计算速度。
- 某些业务场景下,一个数据状态可能有大于2个,可以使用多个bit位来表示一个数据状态。
扩展
为了解决位图稀疏时,位图低效率的问题,工业界,有多种位图压缩算法,其中,最经典的是RoaringBitmap。
RoaringBitmap的核心思想是,将整数进行分桶,高16位的值作为其桶的索引,每个桶对应一个容器。如下图所示:
roaring bitmap
容器的结构有三种类型:有序数组、未压缩位图、和行程长度编码。
- 有序数组:当低16位中,元素个数小于4096时,采用有序数组的结构进行存储。在查找元素时,使用二分查找方法。取值4096的原因是,存储4096个16位的整数,所占用的存储空间:。
- 未压缩位图:未压缩位图的存储结果就是本文所描述的位图存储结构,使用一个固定的连续内存块实现。
- 行程长度编码(run-length encoding):行程长度编码是一种无损数据压缩技术,其原理是,将连续出现的数据存储为起始值和计算两部分。比如,数据列表[1,2,3,4,5,6]存储为[1,5],表示以1开始,后面连续递增5个数值。在很多实现中,行程长度编码容器,需要手动调用,才能转换为该容器。
在进行插入和删除操作之后,需要根据元素个数进行容器转换。插入元素时,若元素个数达到4096,则需要转换为未压缩位图进行存储。删除元素时,若元素个数小于4096时,则需要转换为有序数组存储。
参考
- Better bitmap performance with Roaring bitmaps。
- Consistently faster and smaller compressed bitmaps with Roaring。
- https://github.com/RoaringBitmap/CRoaring.git。
相关文章
- 学生数据库管理系统
- SpringDataJpa 用MySQL语句怎么分页,spring全家桶SpringDataJpa 用MySQL语句怎么分页
- Docker创建MySQL容器模板命令
- Elasticsearch对应MySQL的对应关系
- 使用SpringDataJpa保存(save)报错误:SQL Error: 1062, SQLState: 23000 控制台会报:Duplicate entry ‘数‘ for key ‘PRIMA
- Navicat Premium 连接sqlserver数据库时提示安装Client失败,解决方案
- Mysql查询当前用户所有数据库语句(SHOW DATABASES)
- MySQL语句-查看当前数据库有哪些表(SHOW TABLES)
- MySQL5.0版本以上新增的 information_schema 数据库是什么?
- MariaDB数据库备份之逻辑备份
- MariaDB数据库创建用户
- MariaDB数据库给用户授权
- MariaDB数据库刷新权限表命令
- MariaDB数据库删除用户命令
- PhpStudy 2016搭建-sqli-libs靶场
- MySQL手动注入步骤
- Pikachu靶场-SQL注入-数字型注入(post)过关步骤
- Pikachu靶场-SQL注入-字符型注入(get)过关步骤
- 利用SQL注入漏洞实现MySQL数据库读写文件
- Kali-工具-sqlmap常见用法