技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 查看专题: bitmap
    今天,有个同学向我咨询大数据的一些面试题,其中一类比较有代表性比如判断是否在集合内,比如10个url,判断一个url是否在集合内,还比如有个1~100万个连续无序数字,随机取出里面的N个,求这N个数字等等。这类问题都需要一个大的数据集合,而且每个数据单元都很小,比如一个int 。很大程度上,这类问题可以用Bitmap或者Bloomfilter来做,基本思想就是开辟一块大内存,然后利用一个byte里的8个bit来实现按位标记元素。因为地址空间都是连续的,所以查找都是O(1)的。这里需要说的是,BloomFilter判断属不属于集合,在理论上是存在误判的,如果要求数据100%正确,则不要使用BloomFilter。
    在Oracle 9i中,Oracle有时候会选择将B-Tree索引进行BITMAP转换来进行SQL执行,从而导致极其恶劣的执行计划。在下图中BITMAP CONVERSION FROM / TO ROWIDS 就是进行了位图转换后的执行计划
    这篇文章基于 fastbit 软件包,加以实际的用例对常用的 bitmap 索引算法进行了一个较为系统的介绍。不过生成 bitmap 索引仅仅是第一步,bitmap 索引在存储时会有很大的开销,在不损害(较少损害)查询效率的情况下,对 bitmap 索引进行有效的压缩是一个非常有挑战性的课题。除了 bitmap 索引的生成和存储之外,在不同类型的 bitmap 索引上实现高效的各种类型的查询,也是一个值得进一步探讨的问题。我们很高兴地看到 fastbit 软件包实现了很多这些相关领域的算法,为我们提供了非常宝贵的资料。
     bitmap我们可能平时使用的不多,但是觉得它在特殊的应用场景,还 是有优势的。bitmap join index更是一种多表JOIN的新方式,很有意思。
[ 共4篇文章 ][ 第1页/共1页 ][ 1 ]
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1