MySQL数据结构分析--LF_DYNARRAY

目的

       MySQL源码中，LF_DYNARRAY数据结构是应用于LF_PINS和LF_HASH数据结构的一种特殊数据结构。该结构不同于DYNAMIC_ARRAY动态数组结构物理分配和逻辑操作，而是一种层级分配管理方式进行组织，对于稀疏、非连续的数组存储可以有效的提高空间利用率。

数据结构

       LF_DYNARRAY相关的数据结构定义在mysql源码的include/lf.h和mysys/lf_dynarray.c文件中，具体定义如下所示：

 

#define LF_DYNARRAY_LEVEL_LENGTH 256

#define LF_DYNARRAY_LEVELS       4

typedef struct {

  void * volatile level[LF_DYNARRAY_LEVELS];

  uint size_of_element;

  my_atomic_rwlock_t lock;

} LF_DYNARRAY;

 

       其中，level是一个数组指针，level[i]是LF_DYNARRAY每个层分配的首地址；size_of_element是存储的每个元素的大小；lock是原子读写锁变量，用于并发控制读写操作。LF_DYNARRAY_LEVELS表示总的层级数，默认为4；LF_DYNARRAY_LEVEL_LENGTH表示每个数据块的大小，默认为256个字段长度。

源码实现

       LF_DYNARRAY数据结构的实现是一种层级关系，level[0]存储实际的数据块，level[1]存储指向数据块的指针，level[2]存储指向数据块指针的指针，依此类推。在分配存储空间时，由level的上层往下一次分配，即从level[3]开始往level[0]分配数据块。查找存储的数据时，也是通过上层逐级往下查找。

       具体的层级架构如下所示：

  

_lf_dynarray_lvalue()函数

       _lf_dynarray_lvalue()函数时返回给定idx处的内存地址，如果该地址不存在，则调用内存分配函数进行分配。具体的处理逻辑是：首先定位idx的搜索层次，通过索引数组的常量值来定位具体的值；其次，根据搜索层次，逐层查找具体的“索引”（指向下一级指针的指针），如果不存在，则先内存分配该“索引”内存块；最后，返回数据块中的idx的地址，如果数据块不存在，则先分配数据块的内存空间，然后返回idx的地址指针。处理流程图如下所示：

 

_lf_dynarray_lvalue()流程图

 

       从结果可以看出，查找遍历可以通过递归的方式进行。并且MySQL也是这么实现的，如_lf_dynarray_iterate()函数。

       由于其他处理函数都相对较为简单，因此，再次不做详细的分析和解释，通过源码即可很清晰的了解LF_DYNARRAY数据结构的相关操作时如何处理的。

结论

       LF_DYNARRAY数据结构及其相关操作，通过层级分配管理方式，可以提高稀疏的非连续内存空间的利用率。在MySQL数据库中，这种需求较少，仅在LF_HASH扩展HASH数据结构中和PINS数据结构中使用。具体的使用情况，可以参考对应数据结构的分析。