MySQL数据结构分析--TREE

目的

       MySQL数据结构TREE是指红黑树（RB-TREE）数据结构及相关操作，红黑树是平衡搜索树的一种，通过结点的颜色，使得二叉搜索树近似于平衡，保证在最坏情况下基本动态集合操作的时间复杂度O(lgn)。该结构在MySQL中主要应用在myisam存储引擎的全文搜索及相关处理过程、heap键值定义数据结构HP_KEYDEF中。

       尽管红黑树在MySQL中的应用较少，但是红黑树在数据结构及算法方面的重要性毋庸置疑。因此，本文一方面简单介绍红黑树的性质和基本操作，另一方面重点分析MySQL中红黑树数据结构的设计和实现。

红黑树基础

       红黑树结构的性质和基本操作的介绍和分析的文章很多，特别推荐《算法导论》^[1]一书中对该部分的介绍，非常详尽。另外，博文《教你透彻了解红黑树》^[2]中，根据《算法导论》红黑树的介绍，更进一步分析了红黑树。特别推荐转载的《理解红黑树》^[3-4]技术博客中，对红黑树实现的细节部分有进一步的阐述和分析。

       尽管有以上丰富的参考信息，为了便于理解一下MySQL中红黑树的设计，本文给出红黑树的性质，具体内容如下。

性质：

       1、每个结点或是红色的，或是黑色的。

       2、根节点是黑色的。

       3、每个叶结点（NIL）是黑色的。

       4、如果一个结点是红色的，则他的两个子结点都是黑色的。

       5、对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

基本操作：

       由于红黑树是近似平衡的二叉搜索树，因此，在操作过程中，需要进行结点的平衡调整。红黑树的基本操作主要是旋转操作，包括左转、右转（很多文章中介绍，还有其他旋转操作，实际上其他所有的旋转操作都可以通过这两种旋转操作来实现）。

       然而，红黑树在旋转的同时，还需要对结点的颜色作调整。根据红黑树的性质，分为多种情况，具体参考《算法导论》中给出的详细分析过程。

数据结构

       通过以上红黑树的基础知识，以下将分析MySQL源码中，对红黑树的设计及实现过程进行详细分析。

       TREE相关的数据结构定义在MySQL源码的include/my_tree.h和mysys/tree.c文件中，具体定义如下所示：

 

typedef struct st_tree_element {

  struct st_tree_element *left,*right;

  uint32 count:31,

        colour:1;                     /* black is marked as 1 */

} TREE_ELEMENT;

typedef struct st_tree {

  TREE_ELEMENT *root,null_element;

  TREE_ELEMENT **parents[MAX_TREE_HEIGHT];

  uint offset_to_key,elements_in_tree,size_of_element;

  ulong memory_limit, allocated;

  qsort_cmp2 compare;

  void *custom_arg;

  MEM_ROOT mem_root;

  my_bool with_delete;

  tree_element_free free;

  uint flag;

} TREE;

 

       TREE_ELEMENT数据结构中，定义了左右孩子结点指针left、right；结点的计数变量count（31个bit位），当红黑树允许相同结点存在时，该值表示该结点的计数值；结点的颜色变量colour（1个bit位），表示当前结点的颜色状态。

       TREE数据结构中，定义了根结点指针root；NIL结点null_element；parents指针数组，用于存储从根结点到当前结点所有的祖先结点，由于红黑树在结点旋转和颜色调整时，都会涉及到父节点；offset_to_key表示关键字的偏移量；elements_in_tree表示树中结点的数目；size_of_element表示每个对象存储的大小；memory_limit表示红黑树的内存限制；allocated表示已经分配的内存大小，当allocated大于memory_limit的值时，重置红黑树；compare比较函数指针，是键值的比较函数；custom_arg是比较函数的第一个参数；mem_root是MEM_ROOT数据结构，提供特别的内存分配的操作，详细分析参考《MySQL数据结构分析--MEM_ROOT》^[5]；with_delete参数是用于控制使用mem_root内存分配方式，还是使用普通的内存分配方式；free释放内存函数指针，用于释放结点的内存空间；flag用于标志红黑树的一些特性，如TREE_NO_DUPS表示不允许红黑树中的元素重复。

源码实现

       根据数据结构定义可知，MySQL实现的红黑树不是用一个个的NIL结点表示，而用一个哨兵null_element来代替。结构设计如下所示，其中数字表示键值，仅仅是为了说明设计的结构，无实际的意义：

图1 MySQL红黑树设计结构

 

       从操作来看，红黑树的基本操作包括插入、删除、查找等操作，内部实际处理操作包括旋转操作和颜色调整操作。具体如下：

tree_insert函数

       tree_insert()函数是红黑树插入新元素的操作，该处理过程首先按照二叉树的插入逻辑，将新节点插入到对应键值的位置。在查找插入位置时，将根结点root到查找位置路径上的结点的指针存储在parent指针数组中。实际的旋转和调整结点颜色处理逻辑在rb_insert()函数中，具体的处理逻辑参考该函数的详细分析过程。

tree_delete函数

       tree_delete()函数是红黑树删除元素的操作，首先处理过程同二叉树的删除逻辑类似，将删除结点左子树中最小的结点替换删除结点的位置。如果删除结点的颜色为红色，则不需要进行调整。否则，调用rb_delete_fixup()函数进行旋转和调整结点颜色，详细参考该函数的处理逻辑。

tree_search函数

       tree_search()函数是红黑树查找键值的操作，操作同二叉树查找逻辑一致。此外，MySQL提供了tree_search_key()、tree_search_edge()、tree_search_next()函数，提供进一步特殊的查询功能。

left_rotate函数

       left_rotate()函数是红黑树的左旋转函数，在rb_insert()和rb_delete_fixup()函数调整红黑树平衡时，会根据红黑树结点的颜色和状态，调用该函数进行左旋转，已达到平衡。

right_rotate函数

       right_rotate()函数是红黑树的右旋转函数，处理过程类似left_rotate()函数。

rb_insert函数

       rb_insert()函数是红黑树插入元素后，进行旋转和颜色调整的主要处理过程，该过程根据parent中的父结点及其兄弟结点，以及插入的元素进行颜色调整和旋转操作。该过程分为3种不同的状态，具体不同状态的调整策略，同普通红黑树的调整一致。

rb_delete_fixup函数

       rb_delete_fixup()函数是红黑树删除元素后，对树进行旋转和颜色调整的主要处理过程。该过程分为四种不同状态，调整策略同普通红黑树的调整一致。

       其中，left_rotate()、right_rotate()、rb_insert()、rb_delete_fixup()函数为内部函数，实现红黑树的旋转和颜色调整处理逻辑。

结论

       通过分析MySQL实现的红黑树数据结构TREE，发现TREE数据结构在原有红黑树基础上，进行了细微的改进和优化。具体如下

       1、使用哨兵null_element代替NIL结点，节省了内存空间；

       2、使用parent指针数组，记录从根结点到插入位置或删除元素位置的所有父结点，通过该指针数组，即可对红黑树进行旋转和颜色调整。从而避免了为每个元素定义parent指针，浪费内存空间；

       3、定义with_delete参数，使用MEM_ROOT数据结构内存分配方式，提高分配相同大小和类型的内存空间的效率。

 

参考资料

[1] 《算法导论第三版》 --P174-P192

[2] 《教你透彻了解红黑树》 --http://blog.csdn.net/v_JULY_v/article/details/6105630

[3] 《理解红黑树1》 --http://blog.chinaunix.net/uid-26896862-id-3340352.html

[4] 《理解红黑树2》 --http://blog.chinaunix.net/uid-26896862-id-3340353.html

[5] 《MySQL数据结构分析--MEM_ROOT》 --http://blog.chinaunix.net/uid-26896862-id-3412033.html