MySQL数据结构分析--Queue

目的

       在分析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）进行插入操作。最先插入在元素将最先被删除；反之最后插入的元素将最后被删除，即“先进先出”。

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

Queue的实现在mysql源码的mysys/queues.c文件中，以下主要对主要函数queue_insert和queue_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的位置进行堆调整，选择idx及2*idx和2*idx+1三个位置上，最大的元素调整到idx位置上（最大元素根据比较给定比较函数的返回值和max_at_top值决定）。然后，继续调整idx = idx/2位置的元素，直到堆顶元素。

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

结论

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