IT技术博客大学习 共学习 共进步

多维度分类排行榜应用:用位图索引

风轻扬 2009-11-09 09:27:32 浏览 5,062 次
    有谁试过一张表上有50个索引,嗯,我不怎么敢。但有时有些应用的搜索条件就是很复杂,比如说有一类应用,姑且称之为多维度分类排行榜吧。这类应用的共同特征是对一个集合需要应用多种条件组合进行过滤,过滤后可能还要按某种指标进行排序。举几个例子吧:

    1. 像网易拍拍一样的相册精华区,过滤条件非常多,如可以指定一级分类(如风景)、二级分类(如云南)、三级分类(如香格里拉),可以指定城市,可以指定是不是推荐的,还可以指定相机品牌或型号(有人还想指定镜头)。这就非常多了,恐怖的是这些条件还可以组合,比如指定用佳能相册拍香格里拉的,这样几十个组合是很正常的。

    2. 像手机、汽车等等的产品中心网站,也可以指定很多过滤条件并任意组合,如价格,品牌,各种性能参数等等。过滤完了后,可能还要按价格或其它指标排序。

    用数据库来做这类应用代价是很大的,对于数据库应用,一个基本的原则是:一种选择条件组合+排序组合对应一个索引,否则性能就不好,如果选择条件没有对应的索引,则可能要做表扫描或不理想的索引扫描,如果排序没有对应的索引,每次都需要找出所有满足过滤条件的记录然后排序。这样,对于上述复杂应用,需要建50个索引是很可能的,但问题是数据库一般支撑不了这么多个索引,索引越多,更新的性能越差。有几十个索引的数据库设计是很罕见的。

    很多这类应用的解决办法可以用位图索引。位图索引的基本原则是:一个基础的选择条件+排序组合需要一个位图索引,这里“一个基础的选择条件”指的是在单个属性上的条件。用位图索引的时候,选择条件组合是不需要预先建好索引的,在求解时通过对基础的几个索引进行AND/OR位操作,可以很快的计算出结果。这样,使用位图索引时就不会存在条件组合爆炸的问题。而且,同样一个索引使用位图索引实现,比起用数据库里的B+树索引实现,占用的空间开销一般会小一个数量级。

    使用位图索引的缺点是位图索引很难实时更新,或者说一定要支持实时更新的话,位图索引的实现就会很复杂,并且一定会导致时间和空间性能下降。因此位图索引通常不是实时更新的,而只能通过定期重建来更新。幸运的是对很多应用并不需要实时更新,比如产品中心,产品的信息是不经常更新的,数据库更新后过几分钟再更新位图索引也没什么问题。

    一般的,如果要处理的数据量不过百万,那么实现分钟级的位图索引更新是不会有什么问题的。    

建议继续学习

  1. 由浅入深探究mysql索引结构原理、性能分析与优化 (阅读 16,123)
  2. 浅谈MySQL索引背后的数据结构及算法 (阅读 11,384)
  3. 由浅入深理解索引的实现(2) (阅读 7,524)
  4. HBase二级索引与Join (阅读 6,862)
  5. 如何建立合适的索引? (阅读 6,663)
  6. mysql查询中利用索引的机制 (阅读 6,583)
  7. InnODB和MyISAM索引统计集合 (阅读 6,084)
  8. Innodb 表和索引结构 (阅读 6,041)
  9. MySQL索引背后的数据结构及算法原理 (阅读 5,622)
  10. mysql索引浅析 (阅读 5,181)