MySQL数据结构分析DYNAMIC_ARRAY和DYNAMIC_STRING

作者:王恒  发布日期:2012-11-06 09:11:37
目的
       在MySQL源码中,对MySQL的数据结构DYNAMIC_ARRAY和DYNAMIC_STRING的实现进行了分析。通过分析,对以上两种数据结构的定义、设计及实现进行详细的解释和说明。

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

typedef struct st_dynamic_array
{
  uchar *buffer;
  uint elements,max_element;
  uint alloc_increment;
  uint size_of_element;
} DYNAMIC_ARRAY;

typedef struct st_dynamic_string
{
  char *str;
  size_t length,max_length,alloc_increment;
} DYNAMIC_STRING;


       从定义可知,这两种数据结构定义基本一致。不同之处在于DYNAMIC_ARRAY中有一个size_of_element变量,表示数组中每个元素的大小。也正是这点区别,使得DYNAMIC_ARRAY更多的用于复杂数据类型的动态数组实现,而不是仅仅限制在字符的动态数组。如果将DYNAMIC_ARRAY中的size_of_element设置为1,那么可以实现DYNAMIC_STRING的功能,用于只存储字符类型。但是鉴于字符串处理更简单,因此MySQL设计并实现了DYNAMIC_STRING数据结构,用于对字符串操作。

源码实现
       DYNAMIC_ARRAY的源码实现在mysys/array.c源码文件中,主要处理函数包括:
1、初始化函数init_dynamic_array()和init_dynamic_array2(),其中初始化的功能实现都是init_dynamic_array2()函数实现的,根据参数init_buffer给定的指针,初始化有所不同;
2、数组插入函数insert_dynamic(),用于插入数组元素;
3、弹出数组元素的函数pop_dynamic(),该函数实现了从数组的末尾弹出一个元素;
4、替换函数set_dynamic(),用于替换给定索引处的元素;
5、获得元素函数get_dynamic(),用于得到动态数组中给定索引位置的元素;
6、删除动态数组函数delete_dynamic(),用于删除数组中的所有元素,并释放内存资源;
7、删除元素函数delete_dynamic_element(),用于删除给定索引位置的元素,该过程使用memmove函数进行内存的移动;
8、释放内存函数freeze_size(),用于释放未使用的内存空间。
9、获得元素索引的函数get_index_dynamic(),根据给定元素的指针地址,获得元素的索引。由于元素的大小一定,因此查找获取过程就是根据地址的差除以元素的大小即可获得。
10、内存分配函数alloc_dynamic和allocate_dynamic,其中alloc_dynamic函数用于为下一个元素分配空间,而allocate_dynamic函数用于分配一定数量的内存空间。
         以上函数的实现比较简单,基本思路就是根据size_of_element的值,进行一系列的地址转化、处理,从而获取元素或对元素进行操作。
 
       DYNAMIC_STRING的源码实现在mysys/string.c源码文件中,主要处理函数包括:
1、初始化函数init_dynamic_string(),用于初始化动态字符串数组。
2、字符串设置函数dynstr_set(),根据给定字符串的值,对动态字符串进行赋值。
3、动态分配函数dynstr_realloc(),用于动态扩大分配需要的字符长度空间。
4、字符串追加函数dynstr_append()和dynstr_append_mem(),用于将给定的字符串,追加到动态字符串数组的末尾,在追加中需要考虑是否超出当前数组的最大长度。其中dynstr_append()通过调用dynstr_append_mem()实现。
5、字符串截断函数dynstr_trunc(),用于截断给定长度之后的字符串。
6、释放函数dynstr_free(),用于释放分配的内存空间。
         以上函数的实现非常简单,主要是对字符串的一系列操作处理。不涉及复杂的操作和处理过程。www.it165.net
 
       通过以上源码分析,DYNAMIC_ARRAY由于size_of_element变量,因此可以存放定长的元素,甚至可以存放复杂的数据类型的元素。在MySQL的源码中,DYNAMIC_ARRAY数据结构及相关操作应用非常广泛,其中包括:选项(option)和参数(var)处理过程、HASH数据结构、复制子系统的条件过滤、排序处理过程、授权处理、插件存储和操作、键值存储和操作等多种情况。而DYNAMIC_STRING从设计来看,可以将DYNAMIC_ARRAY的size_of_element变量置为1,从而存储字符串及处理字符串的相关操作。但是由于字符串的初始化长度不能太小,否则会造成频繁调用malloc函数,影响性能。因此,DYNAMIC_STRING的设计针对字符串的操作特点而设计。具体的处理过程,可参考源码进行进一步的分析。

结论
       通过以上分析可知,MySQL实现DYNAMIC_ARRAY和DYNAMIC_STRING分别对定长的复杂数据类型进行操作和字符串进行操作。并且,MySQL在多个子系统和处理过程中,都使用了这两种数据结构。
 

延伸阅读:

  • 专题推荐

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规