MySQL数据结构分析—BITMAP

目的

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

数据结构

       BITMAP相关的数据结构定义在mysql源码的include/my_bitmap.h和mysys/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_mask和last_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_mask和last_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数值，转化为4个uchar类型的值来处理每一个字节。并且通过单个字节与0xff的比较，直接忽略该字节。在该数值bit为基本都被设置的情况下，当个字节的比较，可以减少逐bit位的比较的时间代价。

       下图所示，byte_ptr逐字节遍历value，首先判断byte_ptr是否等于255，如果byte_ptr为255，byte_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