Bit-Map(位图)索引 对于数据库表的位图索引 lass sales state-NY Class=A 字段F的一个位图索引是一个长度为n的 位向量的集合(n为文件的记录数 state=AK sta state=NY 恤张 有,成即些究 张写 0取有。就成鲁印当 特征文件 位图索引特点 Signature file(也译为“签名文件”) 按“列”为单位存储数据 倒排表(30foo)(30bar)(30baz) 列数据比行数据更易进行压缩, (40, baz), (40, bar ) (50, foo) 可节省50%的磁盘空间 记录 bar, baz,foo 索引空间比B树小 110 1 K1表示在那个记录中出现了相应的字段值 大带管息张铭写权质有,成即盛究 总结 ■基本概念 101线性索引 The endp 102静态索引 103倒排索引 ■104动态索引 ■105动态、静态索引性能比较 讨论和补充 大带息理张铭写 1919 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 109 Bit-Map（位图）索引 „ 字段F的一个位图索引是一个长度为n的 位向量的集合（n为文件的记录数） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 110 对于数据库表的位图索引 state=AK state=AL … state=NY 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 3/1 3/1 3/1 3/1 3/1 3/1 32 36 38 41 43 46 NY AL NY AK NY AK A A B A A B 6 9 5 11 9 3 1 0 1 0 1 0 1 1 0 1 1 0 date store state class sales State＝NY Class=A 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 111 特征文件 „ Signature file （也译为“签名文件”） „ 倒排表(30,foo),(30,bar),(30,baz) (40,baz),(40,bar ),(50,foo) 记录 bar, baz, foo 30 40 50 1 1 1 0 1 1 0 0 1 1表示在那个记录中出现了相应的字段值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 112 位图索引特点 „ 按“列”为单位存储数据 „ 列数据比行数据更易进行压缩， 可节省50%的磁盘空间 „ 索引空间比B树小 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 113 总结 „ 基本概念 „ 10.1 线性索引 „ 10.2 静态索引 „ 10.3 倒排索引 „ 10.4 动态索引 „ 10.5 动态、静态索引性能比较 „ 讨论和补充 The End!