MySQL数据结构分析--DYNAMIC_ARRAY和DYNAMIC_STRING

目的

       在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()，用于释放分配的内存空间。

         以上函数的实现非常简单，主要是对字符串的一系列操作处理。不涉及复杂的操作和处理过程。

 

       通过以上源码分析，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在多个子系统和处理过程中，都使用了这两种数据结构。