首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

一文读懂比BitMap有更好性能的Roaring Bitmap

1.什么是bitmap?为什么使用bitmap?Roaring bitmap与其他bitmap编码技术相比有哪些优势?2.Roaring bitmap将32位无符号整数按照高16位分容器,即最多可能有216=65536个容器(container),存储数据时,按照数据的高16位找到container(找不到就会新建一个),再将低16位放入container中。高16位又称为共享有效位,它用于索引应该到哪个容器中查找对应的数值,属于roaring bitmap的一级索引。3.Roaring bitmaps以紧凑高效的两级索引数据结构存储32位整数。高密度块使用位图存储;稀疏块使用16位整数的压缩数组。当一个块包含不超过4096个整数时,我们使用一个排好序的16位整数数组。当有超过4096个整数时,我们使用2^16 位的位图。为什么按4096作为阀值呢?仅仅是因为当数据块中的整数数量超过这个值之后,bitmap将比数组的内存使用率更高。

02

《数据库索引设计优化》读书笔记(六)

第10章 多索引访问 练习 10.1 假设多索引访问一节中所描述的拥有位图索引的CIA表包含200000000行数据。请评估(a)位图索引和(b)半宽B树索引所需的磁盘空间。 假设一个字节占8位。请将磁盘空间的差异转化为每月需要支付的美元金额。 书中关于拥有位图索引的CIA表的描述如下:    位图索引的比较优势在于能够很容易地使用多个位图索引来满足单个查询。考虑一个有多个谓词条件的查询,每个谓词上都有一个索引。虽然有些系统可能尝试对多个索引的记录标识进行交集操作,但是传统的数据库可能会只使用其中一个索引。位图索引在此种情况下工作得更好,因为它们更紧凑,而且计算几个位图的交集比计算几个记录集合的交集更快。在最好的情况下,性能的提升与机器的字长成比例,因为同一时间两个位图能够进行一个字长的位的交集计算。最佳的使用场景是,每一个单独谓词的选择性不好,但是所有谓词一起进行索引与后的选择性很好。位图索引考虑如下查询,“找出有棕色头发,戴眼镜,年龄在30岁至40岁之间,蓝眼睛,从事计算机行业并居住在加利福利亚的人”。这意味着对棕色头发位图、佩戴眼镜的位图、年龄在30岁至40岁间的位图等进行交集计算。    在当前的磁盘条件下,只要查询中没有太多的范围谓词,使用一个半宽B树索引是性能最佳的方案,即便对于像CIA那样的应用来说也是如此。对于上文中的例子,一个用HAIRCOLOUR、 GLASSES、EYECOLOUR、INDUSTRY和STATE的任意排序序列作为开头,并以DATE OF BIRTH作为第6列的索引将提供非常出色的性能,因为这使得访问路径将会有6个匹配列:包含目标结果集的索引片将会非常窄。 分析: 位图索引的空间主要跟表的记录数和索引列的键值数有关,题目中只给了表的记录数,所以需要根据实际情况可以确定6个位图索引的键值数如下: 头发颜色 键值数为5 是否戴眼镜 键值数为2 年龄段 键值数为10 眼睛颜色 键值数为10 行业 键值数为100 州 键值数为50 (a)6个位图索引需要的磁盘空间为 (5+2+10+10+100+50) * 200000000 /8/1024/1024/1024 = 4.12G B树索引的空间跟索引字段的长度有关,假设半宽索引的6个字段的总长为50字节 (b)半宽B树索引所需的磁盘空间为 1.5 * 50 * 200000000 /1024/1024/1024 = 13.97G

02
领券