Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1349861
  • 博文数量: 107
  • 博客积分: 1715
  • 博客等级: 上尉
  • 技术积分: 3168
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-18 18:42
个人简介

阿里巴巴DBA,原去哪儿网DBA。专注于MySQL源码研究、DBA运维、CGroup虚拟化及Linux Kernel源码研究等。 github:https://github.com/HengWang/ Email:king_wangheng@163.com 微博 :@王恒-Henry QQ :506437736

文章分类

全部博文(107)

文章存档

2014年(2)

2013年(38)

2012年(67)

分类: Mysql/postgreSQL

2012-12-18 23:59:00

目的

       MySQL数据库源码中,MY_BITMAP数据结构及相关处理方法是位图相关的操作。尽管MySQL不支持位图索引,但是在binlog子系统、查询子系统、分区子系统以及table的定义中都有应用。

数据结构

       BITMAP相关的数据结构定义在mysql源码的include/my_bitmap.hmysys/my_bitmap.c文件中,具体定义如下所示:

 

typedef uint32 my_bitmap_map;

typedef struct st_bitmap

{

  my_bitmap_map *bitmap;

  uint n_bits; /* number of bits occupied by the above */

  my_bitmap_map last_word_mask;

  my_bitmap_map *last_word_ptr;

  /* mutex will be acquired for the duration of each bitmap operation if thread_safe flag in bitmap_init was set.  Otherwise, we optimize by not acquiring the mutex */

  mysql_mutex_t *mutex;

} MY_BITMAP;

 

       MY_BITMAP数据结构定义比较简单,其中bitmap是实际存储位图信息的字段;n_bits表示位图表示的位数,即bitmap的有效位数;last_word_masklast_word_ptr两个变量用于指定最后一个数的掩码值和指针地址,主要是安全访问的考虑;mutex是多线程并发操作时,提供现成安全的访问。

源码实现

       MY_BITMAP数据结构相关的操作相对较简单,主要是位的一些操作,以下仅对几个重要的方面进行分析说明。

bitmap_init()函数

       bitmap_init()初始化函数是MY_BITMAP数据结构的入口函数,该函数初始化MY_BITMAP数据结构中的各个字段。如果输入参数buf未分配内存空间时,该函数将分配4的倍数长度的内存空间,这是由bitmap的类型my_bitmap_map(实际为uint32)决定的。如果初始化函数时线程安全的,则需要为mutex分配内存空间,mutex分配的空间在bitmap对齐后的地址。最后根据n_bits的值,调用create_last_word_mask()函数初始化last_word_masklast_word_ptr两个变量。

       bitmap_init()函数流程图如下所示:

 

1 bitmap_init()函数流程图

 

bitmap_get_first()函数

       bitmap_get_first()函数用于获得第一个未设置的bit位。该函数遍历bitmap,并对bitmap中的每个值(uint32类型),调用get_first_not_set()函数,查找第一个未设置的bit位。由于实际处理函数为get_first_not_set()函数,因此,以下将详细分析get_first_not_set()处理过程。

       get_first_not_set()函数将uint32数值,转化为4uchar类型的值来处理每一个字节。并且通过单个字节与0xff的比较,直接忽略该字节。在该数值bit为基本都被设置的情况下,当个字节的比较,可以减少逐bit位的比较的时间代价。

       下图所示,byte_ptr逐字节遍历value,首先判断byte_ptr是否等于255,如果byte_ptr255byte_ptr直接到下一个字节。如果byte_ptr小于255,则第一个未设置的bit位在该字节内。然后,通过bit_pos逐个bit位查找byte_ptr字节未设置的bit位。最后,返回的地址需要根据value的地址、byte_ptr的位置,以及bit_pos的位置确定未设置的bit位。

 

2 get_first_not_set图示

 

       此外,get_first_set()函数处理过程与get_first_not_set()函数类似,不同之处是每个字节首先判断是否为0,如果为0,则直接查找下一个非0字节中设置的bit位。

       除了以上重要的处理函数以外,MY_BITMAP数据结构还提供了很多位图运算的操作,如bitmap_is_subset()函数判断是否两个位图是否存在子集关系;bitmap_is_overlapping()函数判断两个位图是否有共同bit位;bitmap_intersect()函数查找两个位图的交集;bitmap_subtract()函数计算两个位图的差集;bitmap_union()函数计算两个位图的并集;bitmap_xor()函数计算两个位图的异或。


结论

       通过以上分析,MY_BITMAP数据结构及其处理方法都较简单,没有任何难点。特别值得说明的是MY_BITMAP在查找bit位时,对每个数据(uint32类型)按照逐字节查找,这样在设置密度很大的情况下查找未设置的bit位,或者在密度稀疏的情况下查找设置的bit位,可以通过字节判断直接定位该字节是否存在查找的必要。相较于逐bit位查找该数据,可以减少比较次数,提高查找的效率。


-----------------------------------补充内容---------------------------------

    参考mysql internal manual,对bitmap仍然存在的问题进行了描述,供参考。具体如下:

There are a few warnings and limitations that apply for the present bitmap implementation. First: the allocation is an integral number of bytes, and it is not possible to determine whether the last few bits are meaningful. Second: the whole bitmap might have to be protected by a mutex for manipulations; this is settable by passing appropriate flag values. Third: the bitmap is allocated with a 'uint' size, which means that ordinarily it can't have more than 2^32 bytes. Fourth: when unioning two bitmaps, they must be of the same size.

 

参考

1、mysql internal manual: http://dev.mysql.com/doc/internals/en/bitmaps.html


 

阅读(4471) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~