Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1449260
  • 博文数量: 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-10-29 00:09:14

目的

       在分析MySQL源码中,对MySQL的数据结构Queue的实现进行了分析。通过分析,发现MySQL中的实现不是普通意义上的Queue数据结构,而是在Queue数据结构基础之上增加了堆排序,对队列中存储的内容根据不同实现提供的比较算法进行调整。因此,可以视为一种有优先级的Queue队列设计思路进行的设计。

数据结构

       Queue的数据结构定义在mysql源码的include/queues.h文件中,具体定义如下所示:

typedef struct st_queue {

  uchar **root;

  void *first_cmp_arg;

  uint elements;

  uint max_elements;

  uint offset_to_key;     /* compare is done on element+offset */

  int max_at_top/* Normally 1, set to -1 if queue_top gives max */

  int  (*compare)(void *, uchar *,uchar *);

  uint auto_extent;

} QUEUE;

        从定义可知,root二维指针用于存储添加到队列中的数据;first_cmp_arg表示第一个比较的参数;elements表示当前队列中的对象数;max_elements表示队列中可以容纳的最大对象数;offset_to_key表示比较的关键字的偏移量;max_at_top表示队列头的值是否是最大的值,如果设置为1,队列的头的值是最大值。由于队列中的数据进行堆调整,也就是表示堆调整为大顶堆或小顶堆;compare函数表示比较函数,根据不同场景,比较函数也不同;auto_extent表示队列是否自动扩展。特别注意的是:Queue的存储从1开始存储,而不像数组一样从0开始。

源码实现

       传统的Queue的基本原理是:只允许在队列的前端(front)进行删除操作,而在队列的后端(rear)进行插入操作。最先插入在元素将最先被删除;反之最后插入的元素将最后被删除,即先进先出

       QueueMySQL的实现却不是根据传统Queue进行设计的,而似乎是一种有优先级的Queue队列设计思路进行的设计。

Queue的实现在mysql源码的mysys/queues.c文件中,以下主要对主要函数queue_insertqueue_remove进行分析。除此之外,特别对核心算法_down_heap进行分析。 

/* Insert element into queue */

void queue_insert(register QUEUE *queue, uchar *element)

{

  reg2 uint idx, next;

  DBUG_ASSERT(queue->elements < queue->max_elements);

  queue->root[0]= element;

  idx= ++queue->elements;

  /* max_at_top swaps the comparison if we want to order by desc */

  while ((queue->compare(queue->first_cmp_arg,

                         element + queue->offset_to_key,

                         queue->root[(next= idx >> 1)] +

                         queue->offset_to_key) * queue->max_at_top) < 0)

  {

    queue->root[idx]= queue->root[next];

    idx= next;

  }

  queue->root[idx]= element;

}

        queue_insert函数可知,插入队列不是将数据插入到队列的尾,而是在插入时,需要根据比较算法,调整队列中的值,满足堆排序。while循环中代码,是插入过程中,堆的调整过程。 

/* Remove item from queue */

uchar *queue_remove(register QUEUE *queue, uint idx)

{

  uchar *element;

  DBUG_ASSERT(idx < queue->max_elements);

  element= queue->root[++idx];  /* Intern index starts from 1 */

  queue->root[idx]= queue->root[queue->elements--];

  _downheap(queue, idx);

  return element;

}

        queue_remove函数用于删除队列中,下标为idx的元素。因为Queue的存储从1开始,因此删除idx+1位置的元素。删除元素之后,将最后一个元素替换当前删除的元素,然后调用_downheap进行堆的调整。具体_downheap的调整算法如下所示,不再赘述。 

/* Fix heap when index have changed */

void _downheap(register QUEUE *queue, uint idx)

{

  uchar *element;

  uint elements,half_queue,offset_to_key, next_index;

  my_bool first= TRUE;

  uint start_idx= idx;

  offset_to_key=queue->offset_to_key;

  element=queue->root[idx];

  half_queue=(elements=queue->elements) >> 1;

  while (idx <= half_queue)

  {

    next_index=idx+idx;

    if (next_index < elements &&

       (queue->compare(queue->first_cmp_arg,

                     queue->root[next_index]+offset_to_key,

                     queue->root[next_index+1]+offset_to_key) *

        queue->max_at_top) > 0)

      next_index++;

    if (first &&

        (((queue->compare(queue->first_cmp_arg,

                          queue->root[next_index]+offset_to_key,

                          element+offset_to_key) * queue->max_at_top) >= 0)))

    {

      queue->root[idx]= element;

      return;

    }

    queue->root[idx]=queue->root[next_index];

    idx=next_index;

    first= FALSE;

  }

  next_index= idx >> 1;

  while (next_index > start_idx)

  {

    if ((queue->compare(queue->first_cmp_arg,

                       queue->root[next_index]+offset_to_key,

                       element+offset_to_key) *

         queue->max_at_top) < 0)

      break;

    queue->root[idx]=queue->root[next_index];

    idx=next_index;

    next_index= idx >> 1;

  }

  queue->root[idx]=element;

}

        _downheap函数从下标为idx的位置进行堆调整,选择idx2*idx2*idx+1三个位置上,最大的元素调整到idx位置上(最大元素根据比较给定比较函数的返回值和max_at_top值决定)。然后,继续调整idx = idx/2位置的元素,直到堆顶元素。

       通过以上源码分析可知,可以将队列中最大或最小的元素调整到队列头,则调用queue_top将返回当前队列中最大或最小的元素。此外,通过调用关系发现,这种队列应用在mysqlalarm子系统、查询中的filesort处理过程、全文搜索子系统、myisammerge存储引擎mysiammrgmyisamsort过程以及uniquemerge处理过程等都使用了这种队列。具体使用的处理过程,可参考源码进行进一步的分析。

结论

       通过以上分析可知,MySQL数据结构Queue在实现上,采用了有优先级的Queue队列设计思路,通过给定比较算法,进行堆调整。这样以来,queue_top将返回当前队列中优先级最高的(最大或最小的)元素。并且,MySQL将这种Queue数据结构应用在多个子系统和处理过程中。

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