精华内容
下载资源
问答
  • FastBit是位图索引技术的集大成者,是一系列高级位图索引技术的集合。

    本节所介绍的FastBit是位图索引技术的集大成者,是一系列高级位图索引技术的集合,该项目最初设计目标是为美国国家高能物理实验提供支撑。
    在FastBit中,两个核心创新点分别是:

    1. 字对齐混合压缩编码WAH,根据官方实验数据显示,其在高能物理实验中的索引性能是传统数据库的10倍以上,如图2.7所示;

    2. 多层次(两层)位图编码方式,包括EE、RE和IE,与传统E1、BN编码的实验性能对比如图2.8所示。
      Fastbit

    目前,FastBit也成功应用于多种开源项目中,其中包括联机实时分析引擎Druid,其将FastBit中的高级索引技术与Hadoop的分布式文件系统HDFS结合起来。下面三节的主要工作就是介绍FastBit中核心创新点之一的WAH算法,和其改进算法Concise以及另辟蹊径的一种高级位图索引技术Roaring Bitmap。

    1 WAH

    WAH算法的核心在于两点:Word-Aligned和Hybrid。

    1. Word-Aligned充分利用了现代CPU的特性,操作Word要比Byte效率高,所以WAH按照字对齐的方式对bitmap进行分组压缩;

    2. Hybrid针对bitmap中既存在大量连续的“0”或“1”序列,又存在“0”“1”混合序列的情况,对这两种情况采用不同的压缩编码策略。

    我们将Word分成两类:literal words和fill words,其中literal words用于“0”“1”混合序列,置最高位bit为0,剩余bits直接存储混合序列;fill words用于大量连续的“0”或“1”序列,置最高位bit为1,全“0”序列置次高位bit为0,全“1”序列置次高位bit为1,剩余bits存储该序列中“0”或“1”的个数,高位不足则用“0”补齐。图2.9给出了WAH算法的具体过程,下面我们结合图例进行介绍。

    WAH算法过程
    算法描述

    2 Concise Bitmap

    Concise算法,全称叫做“Compressed‘n’ Composable Integer set”,是WAH算法的改进型。从上一节中我们可以看出,对于fill words,除去最高位和次高位,剩余的30bits最大可以表示2^30-1个连续的全“0”或全“1”序列,但是在实际使用场景中并不会出现,所以必然还有优化的空间。那么Concise算法就是高效压缩fill words中低n bits的改进型的WAH算法,或者说Concise算法解决如何压缩一个可组合的整数集合,或者可以是认为如何压缩一个稀疏的bitmap这一类问题。在实验中,Concise算法的压缩性能比WAH提高50%左右。

    在Concise算法中,依然存在literal words和fill words的概念。其中,对于literal words,压缩策略与WAH基本一致,不过有一点差别,Concise置最高位为“1”来表示literal words,“0”表示fill words,如图2.10所示;对于fill words,除了最高位置“0”,次高位与WAH一致外,紧接着的5bits称为“Position bits”,代表了反转的位置(the position of a “flipped” bit),表示在第一个31-bitsgroup中从第几位开始进行0、1反转。举例说明:

    1. 若Position bits = 0 (用二进制00000表示),代表该word是一个纯粹的fill word,语义与WAH一致;

    2. 若Position bits = n (0, 32) (用五位二进制表示),代表此fill word中第一个31-bitsgroup从第n位开始0、1反转;
      而剩余的25bits表示除第一个31-bitsgroup外,该fill word还存放多少个连续的31-bits group,语义与fill words一致。我们可以看出,一个Word的最大的范围是31 + 2^25 * 31 = 1040187423 bit。

    concise
    图2.11给出了一个由6个words组成的Concise算法样例,在Concise算法中,我们把bitmap看作是一个整数集合,也就是说如果此bitmap是一个literal word,那么位数则代表整数的个数,固定为31个;如果此bitmap是一个fill word,那么整数的个数为Count(31-bits group) * 31。下面我们就结合图例来理解Concise算法。

    1. Word#0 是literal word,除去最高位,剩余31bit可以表示[0,30]这31个整数。

    2. Word #1 是fill word,其中次高位为1,表示全“1”序列,Position bits为00000,表示此fill word语义与WAH一致,后25bits为1,表示包含2个31-bits group,第一个31-bits group表示[31,61]这31个整数,第二个31-bits group表示[62,92]这31个整数,即Word#1表示[31,92]这62个整数。

    3. Word#2是fill word,次高位为0,表示全“0”序列,Position bits为00001,表示从第一个31-bits group的最低位开始0->1反转,后25bits为11101,表示除第一个31-bits group外,还有29个31-bits group,最大可以表示93(start) + 31 + 29 * 31 - 1 = 1022,即Word #2表示[93, 1022]这个区间内的整数。

    4. Word #3 是literal word,包含31个整数,表示[1023, 1053]这个区间内的整数。

    5. Word#4 是fill word,次高位为0,表示全“0”序列,Position bits为00000,表示该fill word的语义与WAH一致,后25bits为33554397(十进制表示),表示共有33554398个31-bits group,最大可以表示1054 + 31 + 33554397 * 31 – 1 = 1040187391,即Word #4表示[1054, 1040187391]这个区间内的整数。

    6. Word#5 是literal word,包含31个整数,表示[1 040 187 392, 1 040 187 422]这个区间内的整数。
      concise 算法

    3 Roaring Bitmap

    上两节介绍的WAH和Concise压缩算法都是基于RLE原理,而Roaring bitmap则另辟蹊径,实验表明Roaring bitmap的压缩性能比RLE类更高。目前已知的使用Roaring bitmap的开源项目有Apache Spark、Apache Lucene和Druid.io。

    Roaring Bitmap的主要思想是将32bit的整数分割成2^16个数据块,所有数据块共享相同的高16bit,低16bit则使用专门的容器来保存。容器可分为以下两种:

    1. 当一个数据块中的整数个数不超过4k时,我们认为是一个稀疏数据块,使用16bit/整数的有序数组容器(ArrayContainer)进行保存。

    2. 当一个数据块超过4096个整数时,我们认为是一个密集数据块,使用2^16bit的bitmap容器进行保存。

    其中,阈值4k保证了每个整数不超过16bit,其中数组容器是固定bit(16 bit/整数),而bitmap容器中每个整数不超过2^16 / 4k = 16 bit。那么,为什么选择4k这个阈值呢?因为根据上述公式,小于4k时,bitmap容器将会大于16bit/整数,大于4k时,数组容器大小会超过2^16 bit。总之,数据块基数较小时,使用数组更省空间,基数较大时,使用bitmap更省空间。

    下面,我们简单介绍下基于Roaring bitmap的相关操作:

    1. 基数计算
      每种容器(位图容器、数组容器)都使用一个计数器来记录它的基数,所以最多只需要累加2^16个计数器就可以完成。

    2. 数据查找
      判断一个32bit的整数x是否存在,我们首先使用二分查找搜索x/2^16关联的容器。如果访问到的是数组容器,那么我们将继续迭代二分查找;如果访问到的是bitmap容器,那么我们就访问第x%2^16个bit,“0”表示不存在,“1”表示存在。

    3. 数据插入与删除
      对于插入或者删除一个数据,我们首先需要找到对应的容器,当对象是一个数组容器时,我们使用二分查找在线性时间内插入或删除数据;当对象是一个bitmap容器时,我们设置对应bit的值并更新计数器。当删除一个整数时,bitmap容器的基数可能会减少到4k,退化为一个数组容器。当增加一个整数,一个整数容器的基数可能会超过4k,而变成一个bitmap容器。当上述两种情况发生时,Roaring bitmap会创建新的容器,更新计数器等并丢弃旧容器。

    展开全文
  • BIT二叉索引树(树状数组)

    千次阅读 2016-12-16 20:36:56
    本文介绍BIT二叉索引树这种数据结构的搭建和应用。该数据结构能在动态修改的数组连续和查询问题上有极其出色的表现。 POWERED BY PHANTOM_LSH 本文知识和代码(c++)风格来源于刘汝佳的《算法竞赛入门经典 训练指南...

    本文介绍BIT二叉索引树这种数据结构的搭建和应用。该数据结构能在动态修改的数组连续和查询问题上有极其出色的表现。

    POWERED BY PHANTOM_LSH
    本文知识和代码(c++)风格来源于刘汝佳的《算法竞赛入门经典 训练指南》


    前缀和

    现在有如下一个简单的问题:输入n个数据,储存在数组a[n]中,要求多次查询(sum(i , j))从i到j(即[i , j] )上所有元素的和。
    由于查询较多,循环显然效率低下。可能大多数人都可以想到使用一个辅助数组s计算每个元素的前缀和(即s[x] = a[1]+a[2]+a[3]+…+a[x]),这样,当需要计算sum(i , j)时只需要计算s[j] - s[i-1]即可。如果不明白这一点请认真思考并将它理解。

    动态连续和查询

    将上面的求连续和问题稍微改进一下,现在需要支持一种新的操作:add(x , d) 即把a[x]增加d。
    这样一来,如果通过前缀和的方式计算就不能简化计算了,因为每次修改一个元素都要修改所有在它后面的前缀和。有什么解决办法呢?我们需要用一种新的数据结构——BIT二叉索引树(树状数组)。

    lowbit

    在介绍二叉索引树之前必须要介绍这样一个函数:lowbit(x),它返回的是正整数x的二进制表示方法中最靠右的一个1所代表的数字(例如:lowbit(10) = 2,因为10的二进制是1010,最靠右的一个1在第二位上,代表2)。
    其实,lowbit看似复杂其实代码实现异常简单。即:

    int lowbit ( int x){return x&-x;}
    

    它的原理其实是:在计算机内部,负数(-x)是x按位取反(1变0,0变1)然后加1之后的结果(这里不讨论为什么),所以,-10的储存其实是0110 。然后再进行与运算,就可以得到lowbit了。

    BIT

    终于进入了正题。运用lowbit我们可以把从1到n一段数字沿lowbit从大到小一半一半的分割开。比如:1-10中,8的lowbit最大,所以1-7一段,9-10一段,以此类推。所以,好像线段树那样,一段连续的数字被不停地分割直到只剩下一个数字。
    我们把lowbit相同的节点放在同一层(没有的补上去),这样自然形成一棵结点数为大于n的 最小的 2的某整数次方-1 的一棵完全二叉树,其根结点为lowbit最大的结点。通常我们把0也变成一个虚拟化的节点放在里面,方便运算。
    一个简单的BIT示例
    我们发现一个重要的结论:由于lowbit的定义,每个结点的两个子结点与该结点的二进制只有两位不同,一位是该节点的lowbit,两个子结点分别为0和1,另一位是子结点的lowbit,两个子结点都为1但是该结点为0 。这样的现象产生一个重要性质,即:***对于一个结点x,它左上方(可以不是顺着边,而是首个向左上回溯的祖先结点)结点的编号为x-lowbit(x),而右上方(解释同上)结点的编号为x+lowbit(x) 。***请打草稿或者仔细思考一下这个结论。
    因此,我们可以不要储存这一棵树,因为边的关系可以直接计算。另:在BIT中只需要向上回溯。
    一定要记住,BIT的结点储存的是原来的序列的下标!切记!!

    动态连续和

    那么,BIT已经构造出来了,怎么用来解决问题呢?
    现在,构造辅助数组c[n](就像上面的s[n]一样),c[x] = a[x-lowbit(x)+1]+a[x-lowbit(x)+2]+a[x-lowbit(x)+3] + ……+a[x](a数组是原来的序列) 。这是什么意思呢?请看图:
    BIT应用示例
    每个结点都对应一个向左延伸的黄颜色的横条。横条所覆盖的数对应的序列值的和记录在c数组里面,就好像前缀和一样。
    那么,c数组有什么用呢?
    其实,如果要查询一个结点x的前缀和,只要不停地顺着x = x-lowbit(x) 迭代到0,将沿途的C数组的值全部相加就可以得到a[1]+a[2]+……+a[x]了。在上图中,就是顺着蓝色的箭头不停地向左上方移动,观察一下,是不是通过黄色的横条不重复不遗漏的覆盖了所有的下标?这就是查询操作了。
    那么增加的操作呢?观察发现,只要沿着x = x+lowbit(x)不停地向右上方走(图上的红色箭头),直到走出边界,修改沿途的c值就可以了(使它们增加d)。因为能够覆盖到结点x的黄色横条只有那些。修改操作也就这样完成了!
    最后再说一下预处理,预处理只要把a数组和c数组都清空,然后执行n次add操作,相当于从0开始add到原始数据就可以了!
    看上去说的很多,其实代码实现很简单,下面附上c++版本的sum函数(前缀和)和add函数代码。

    int sum(int x){ //求x前缀和
            int ans = 0;
            while(x>0){ //迭代到虚拟结点
                ans+=c[x];
                x -= lowbit(x); //向左上方移动
            }
            return ans;
        }
        void add(int x, int d){ //修改操作
            while(x<=n){ //判断是否超出边界
                c[x]+=d;
                x+=lowbit(x); //向右上方走
            }
            return ;
        }
    

    最终,要求[a , b]的连续和只需要求sum(b) - sum(a-1)就可以了!

    时间复杂度分析

    由于二叉树的基本特征,很容易看出修改和查询前缀和两个函数的时间复杂度都是O(logn),而预处理是n次add操作,所以预处理时间复杂度是O(nlogn) 在查询量多时远远优于暴力算法!


    好了,BIT二叉索引树(树状数组)就介绍到这里,我只是写下了我的理解,希望大家看了以后有所收获!刘汝佳的书上有一道例题,可以直接搜索LA 4329,供大家参考。
    谢谢阅读!


    Powered by Phantomlsh

    展开全文
  • 我看过不少对Bit字段能否建立索引,以及建立索引后性能如何的讨论,还有朋友建议用Tinyint代替Bit,我在这里深入研究一下: 研究方法: 一、建立六张表,具体说明见SQL语句中的注释部分: 建表Sql语句 CREATE ...
  • MySQL bit数据类型踩坑 测试突然报告前端无法接收数据,请求返回超时。 第一反应,代码又有BUG,脑袋急速运转。从请求入口处过细节,边看代码边往下走,三步并五步,流程走到底,没问题啊?怎么会超时呢? 网络?...

    MySQL bit数据类型踩坑

    测试突然报告前端无法接收数据,请求返回超时。

    第一反应,代码又有BUG,脑袋急速运转。从请求入口处过细节,边看代码边往下走,三步并五步,流程走到底,没问题啊?怎么会超时呢?

    网络?呼喊前端,答案是NO。咦,对网络确实不应该,再回忆一遍,数据库,这流程中有访问数据库。迅速查看定位那段代码,拿出SQL直接查询一下,18分钟才返回数据,要求秒级返回,这差距真大啊。

    接着查看为什么返回慢呢?第一反应Index失效,果然

    原来BIT数据类型存储格式是二进制,BIT当做字符串类型, 而不是数据类型。解决方案:

    select * from tab where col1 = 'xx' and col2 = false;  
    创建联合索引 
    create index tab_col1_col2_index on tab(col1,col2);
    

    上面的方案其实是一种折中方案,将原来18分钟才能返回的结果优化到110~150秒之间,长久之际还是要修改数据类型,将bit改为tinybit,或者其他类型不需要转换的,降低数据重复率,这样索引就不会失效。

    转载于:https://my.oschina.net/yutaodev/blog/2873134

    展开全文
  • 个人认为其核心技术包括:列存储和bit-wise索引。首先了解行存储,把属于一行的所有列的数据存储在连续的空间即为行存储。行存储有两个缺点:由于DBMS中磁盘IO的单位是block (oracle中的block大小2K-32K), 如果查询...

    1 IQ 简介

    SybaseIQ是一款数据仓储产品。个人认为其核心技术包括:列存储和bit-wise索引。首先了解行存储,把属于一行的所有列的数据存储在连续的空间即为行存储。行存储有两个缺点:由于DBMS中磁盘IO的单位是block (oracle中的block大小2K-32K), 如果查询只关心行中的部分列,需要同时读取其它的列,增加了IO;block上的数据类型不一致使得压缩率低。这两个缺点对数据仓储而言是非常大的限制。列存储很好的解决了这两个问题。

    位图索引在数据存储中是一个非常有用的索引,相比B+树索引而言,位图索引占用的空间极少,且非常适合集合运算,比如count函数。位图索引的缺点是只适用于基数小的列,当列的基数变大以后,位图索引占用的空间非常大。位图索引的另一个缺点是不支持范围查找。

    IQ声称其采用的bit-wise索引解决了位图索引的缺陷,bit-wise索引支持高基数列,且支持范围查找。Sybase为bit-wise技术申请了专利,其专利内容参见《METHOD AND APPARATUSFOR IDNEXING DATABASE COLUMNS WITH BIT VECTORS》,这篇专利论文详细的描述了bit-wise的技术细节。研究这篇论文后,下面是我对bit-wise的理解。

    2 bit-wise原理

    如图1所示,表存在两个列AA和BB。我们现在要在AA上建bit-wise索引。

     

    AA

    BB

    row1

    3

    row2

    1

    row3

    2

    row4

    4

    row5

    1

    图1 table1中的数据

    2.1 生成索引

    ●计算bit vector的数量

    针对AA列,我们用32bit整数(实际上只需3bit来表达,为了描述更通用的情况,所以用了32bit)来表达AA列上的值,我们需要32个bit vector。


    ●生成bit-wise索引

    如图2所示。bit vector中的位图的数量与表中记录的数量一样。

    2.2 单值查找

    假设我们执行条件为where AA=1的查询。1的二进制表示是{0…0,1},分别与bit-vector执行and运算,结果见图3。通过结果bit-vector即可获取目标记录,通过bit-vector进行集合运算也是非常方便的,比如count运算。


    2.3 范围查找

           假设我们执行条件为where AA>1的查询。

    1)忽略目标值低位连续为1的位

    在本例中我们可以忽略最低位。假如查询的条件为where AA > 11,11的二进制表示为{0…1011},则我们可以忽略最低的2位,即第1位和第2位。

    2)从低位开始,依次处理目标值的每个bit

    设V1是一个bit-vector,大小是表记录的数量,各个bit的值初始化为0。

    从低位开始,依次处理目标值的各个bit。如果bit为0,则把V1和索引进行或操作,把结果写入V1;如果bit为1,则把V1和索引进行与操作,把结果写入V1。

    如图4所示。由于第1为被忽略,所以先处理第2个bit,由于第2个bit为0,所以把V1和索引的第2个bit-vector进行或操作,把结果赋值给V1,见R2;然后处理第3个bit,由于第3个bit为0,把R2与索引的第3个bit-vector执行或操作,把结果赋值给V1,见R3;处理第32位以后,V1的值见RA。RA中值为1的行记为目标记录,即符合条件where AA>1的行。


    展开全文
  • 我们在 FastBit 中引入 PLWAH(位置列表字对齐混合)编码作为测试我们新设计的名为 SECOMPAX 和许多其他位图索引压缩方案的基准。 SECOMPAX 是一种新的位图索引编码算法,它是 COMPAX 的后裔,具有新设计的码本。 ...
  • 一直以来都认为在 bit 列上不能建立索引,因为 SQL Server 2000 的帮助文档在描述 bit 数据类型时,就是这样强调的: bit Integer data type 1, 0, or NULL. Remarks Columns of type bit c
  • 索引

    千次阅读 多人点赞 2018-09-07 23:27:20
    索引是一种对数据库表中一列或多列的值进行排序的一种数据存储结构。 需要占用磁盘空间。 类型:普通索引,唯一索引,主键索引,复合索引,聚族索引。 唯一索引:不允许具有索引值相同的行,即每一行数据的索引的...
  • 题目:给定一个整形(unsigned int)数字,输出其二进制数中的bit为1 的最高/低位索引。 示例:对于数据0,返回0;数据1,返回1;数据0x80000000,返回32; 本文以搜索最低位即最右侧的bit1索引为例。 1、迭代法...
  • 索引 索引 索引

    千次阅读 2014-07-27 16:25:58
    對單列建立索引 create index IX_TABLE1_C1 on table1(column1), create index IX_TABLE1_C2 on table1(column2) 索引的三個問題 索引( Index )是常见的数据库对象,它的设置好坏、使用是否得当,极...
  • x [BiT]-磁力与磁力索引器 __ __ __ .--.--| |--|__| |_ |_ _| _ | | _| |__.__|_____|__|____| 13-Feb-2o21 - Crashed hdd db, moved to nvme, but lost all magnets, that´s life ^^ xBiT does not host ...
  • void add(int x,int v){ for(int i = x; i <= n; i += lowbit(i)){ C[i] += v; } }
  • https://sdm.lbl.gov/fastbit/ stBit is an open-source data processing library following the spirit of NoSQL movement. It offers a set of searching functions supported by compressed bitmap ...
  • 段位树形变化 此回购包含段/二进制索引树的不同变体的代码
  • 索引分区(本地索引和全局索引

    千次阅读 2016-11-12 19:04:26
    --索引分区(本地索引和全局索引) 对索引分区有以下两种方法: 按表分区的方式对索引分区:这也称为本地索引(local index)。每个表分区都有一个索引分区,而且这个索引分区只会对这个表分区中的数据进行索引。 ...
  • Concatenated 多行索引--即如果索引建立在多个列上,只有它的第一个列被where子句引用时,优化器才会使用该索引,即至少要包含组合索引的第一列 Unique 唯一索引 NonUnique 非唯一索引 Function-based函数索引 --1...
  • 位图索引

    2018-12-31 10:08:06
    位图索引(bitmap index)技术是一类特殊的数据库索引技术,其索引使用bit数组(或称bitmap、bit set、bit string、bit vector)进行存储与计算操作。 下面给出位图索引的定义:位图索引可以看作是存储了大量bit位的...
  • 数据库的五种索引类型

    万次阅读 多人点赞 2019-03-15 21:24:13
    本文从如何建立mysql索引以及介绍mysql的索引类型,再讲mysql索引的利与弊,以及建立索引时需要注意的地方 首先:先假设有一张表,表的数据有10W条数据,其中有一条数据是nickname='css',如果要拿这条数据的话需要些的...
  • 3. 索引应该建在小字段上,大的数据字段(bit,image,text)不适用 二. 联合索引: 1. 查询条件中出现联合索引第一列或全部则能利用联合索引 2. 只要联合条件全部在 3. 查询条件中没有出现第一列,而出现第二列...
  • 现在,我们知道优化器如何对这些技术做出反应,清楚地说明 bitmap 索引和 B-tree 索引各自的最好应用。 在 GENDER 列适当地带一个 bitmap 索引,在 SAL 列上创建另外一个位图索引,然后执行一些查询。在这些列上,用...
  • 1.什么是索引?为什么要用索引? 1.1索引的含义 1.2为什么用? 2.索引的作用与缺点 2.1作用 2.2缺点 3.索引的使用场景 3.1应创建索引的场景 3.2不应创建索引的场景 4.索引的分类与说明 4.1主键索引 ...
  • 以前windows 7的时候也遇到过,索引图标不见了,取而代之的是这个图标,这次可能是之前win7升级win10导致的丢失?当时win7遇到这个问题时的解决思路好像是从别的win7的电脑里copy了一份索引的应用到本机然后解决的,...
  • 数据库索引

    万次阅读 多人点赞 2018-11-11 09:27:25
    说白了,数据库的索引问题就是查找问题 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询,更新数据库中表的数据.索引的实现通常使用B树和变种的B+树(mysql常用的索引就是B+树) 除了数据之外,数据库...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 121,437
精华内容 48,574
关键字:

bit索引