位图作为一种简高效使用内存的数据结构,在很多场合都能够用最省的内存表达大量的数据。我对位图最早的印象来自于《编程珠玑》中用位图结构来存储电话号码。感叹其简单、方便。本质上,位图是一个存储单个位的数组,每一个位表示一个数组元素。例如如果我们需要标记100万用户的在线状态,则可以将每个用户对应到一个位,只需要100万个位(约0.125M内存)的位图就可以表示了。如下图所示,在线的用户标记为绿色。其存储则可表示为 {01010011 0011…}。
但是对于某些比较稀疏的位图,其存储效率也会有一些问题。如果100万用户平均只有100个人在线,那另外的999,900个位就浪费掉了。例如在第1位有一个用户,第1,000,000位有个用户,需要1M个位来保存。既浪费了存储空间,也带来大量无用的运算。在前不久我们的应用中就有这种问题。未经压缩的位图保存到数据库中,结果大量的IO操作对数据库的性能造成较大影响。
因为稀疏的位图比较多,比较直接地就想去掉中间的这些空白位,于是就想这样表示:存储第一个位的值(0或1),接着将接下来的所有值相同的位的数目保存为一个整数,再保存接下来另的一类连续位的数目,依此类推。如:{0000 0000 1000 0000 0000 1100 0001 0000 …… } 保存为 0,7,1,11,2,5…。 如果是一百万个位,只有第一个和最后一个是1{10000 …. …. 1},则保存为{1,999998,1}只需要三个整数就可以了!(注:实际上,早有人完整地将这种方法实现了,参考D-Gap Compression)
于是对比较稀疏的位图应用这种方法,由于大部分位图都是比较稀疏,90%以上的位图的体积最终缩小了10倍。在测试过程中,发现最终存储的是大量的小整数(小于1000)。这些小整数其实可以用更短的类型来表示,于是应用变长编码来处理。其原理是每一个字节的高位做标识,其余7位存储值。1标识从这个字节开始是一个新的整数,0表示是上一个字节的延续。则区间[1, 2^7 )中的整数占用一个字节,[2^7, 2^14)中的整数占用两个字节,依次类推。
最终,90%以上的位图体积压缩了30倍以上。
- 大小: 1.2 KB
分享到:
相关推荐
基于双向位图的CSR大规模图存储优化.docx
为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化...
位图连接索引是数据仓库中一种有效的优化表间连接操作性能的索引机制。在大内存分析处理应用场景下,位图连接索引不仅需要权衡索引的内存和CPU开销,还需要进一步考虑处理器平台所带来的性能收益和数据访问延迟。...
咆哮位图将一组32位整数存储在一系列数组和位图中,以空间最小的方式(始终为2 ** 16位或更小)。 此数据结构可用于存储大量整数,例如,用于搜索引擎和数据库使用的倒排索引。 特别是,可以快速计算一系列集合的...
带位图索引的列式内存存储该软件包包含一个高性能、柱状、内存中存储引擎,支持快速查询、更新和迭代,零分配和位图索引。特征优化的、缓存友好的列式数据布局,可最大限度地减少缓存未命中。 针对查询期间的零堆...
也有⼀些设计中,空值位图存储在记录的开头,并且对空属性不存储数据(值或偏移量/长度),这种⽅式是典型的 时间换空间 设计,对于 稀疏型记录⽐较有效。 2、分槽的页结构(slotted-page structure)⼀般⽤于在块...
必要可以采用位图索引 *存在递归查询情况如果关联Table太多对性能会造成较大影响,往往推荐采用临时表转为分步骤操作提高性能 *尽量使用表关联查询而不使用函数,但涉及类似于代码表要重复关联多次取数据问题...
当视图的drawRect方法首次被调用时,层会将描画的结果捕捉到一个位图中,并在随后的重绘时,尽可能使用这个位图,以避免开销太大。CoreAnimation把和视图对象相关联的层存储在层树的层次结构中。 可以在层树中添加...
输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,。... 约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化了。
给出了一种数据仓库版本的形式定义和维度实例的共享存储方式,并在此基础上设计了查询优化算法DWVOQ,通过建立维度实例的版本视图及其与事实实例的连接索引来降低索引空间代价,提高索引查询效率。
存储的文件较小,但是很难表现色彩层次丰富的逼真图像效果。你可以理解成完美的圆型、抛物线等形状。 位图:又叫栅格图、像素图,最小单位由像素构成,缩放、旋转会失真。举个例子来说,位图就好比十字绣,远看时...
§10.11 确定数据库对象存储大小 117 §10.11.1 非簇表的大小计算 117 §10.11.2 索引大小计算 119 §10.11.3 簇表的大小计算 120 §10.11.4 位图索引的大小计算 122 §10.12 应用类型设计考虑要点 122 §10.13 应用...
将自动机全部状态按照字典树结构的层数划分,将访问频率较低的后若干层状态对应的转移表压缩存储,并使用位图提高对被压缩信息的检索速度。经过实验和在实际应用环境中的验证,这种改进算法能够大幅降低空间开销,而...
UBFG 可以将字体导出为 XML 格式(base64 格式的图像也存储在 XML 中)或它自己的 .fnt 格式, - 准备与 Cheetah 2D 引擎一起使用。 XML 格式是自描述的,.fnt 格式使用以下规范。 UBFG 生成两个文件:font.png 和 ...
存储在此存储库中的JSON文件是可以导入到BitFontMaker2中的位图数据的备份。 参考字体 您可以在以下位置找到原始的TTF文件,以供开发期间参考。 Open Sans Regular :这个; EB Garamond :托管在; Special ...
14.4.3 存储统计信息 376 14.4.4 单表 378 14.4.5 完备性检查 379 14.4.6 一般计划 380 14.4.7 Join order[1] 380 14.4.8 Join order[2] 386 14.4.9 Join order[3] 387 14.4.10 Join order[4] 388 14.4.11 Join ...
你可以轻松从web浏览器获得图像,处理图像,存储图像,转换图像和返回优化图像和thumbnails。 <br> Image Server SDK控件新特点: 新的更强大的JPEG压缩引擎。 大大地加强了颜色reduction运算法则。 有损GIF颜色...
4. 优化后台管理界面,全面使用矢量图标替代位图,图标的颜色大小不再是头疼的问题。海量的图标库,用户也可创建自已的图标集; 5. 进一步区分各个站点的数据,包括订单、会员等信息,重点打造移动平台、微信方面的...
第1章 数据的存储结构和特征1 1.1 表和索引分离型5 1.1.1 堆表的结构5 1.1.2 聚簇因子(cluster factor)10 1.1.3 影响读取的因素13 1.1.3.1 大范围数据读取的处理方案14 1.1.3.2 提高聚簇因子的手段17 1.2 索引组织表...
第1章 数据的存储结构和特征1 1.1 表和索引分离型5 1.1.1 堆表的结构5 1.1.2 聚簇因子(cluster factor)10 1.1.3 影响读取的因素13 1.1.3.1 大范围数据读取的处理方案14 1.1.3.2 提高聚簇因子的手段17 1.2 索引组织表...