Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1731643
  • 博文数量: 107
  • 博客积分: 1715
  • 博客等级: 上尉
  • 技术积分: 3168
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-18 18:42
个人简介

阿里巴巴DBA,原去哪儿网DBA。专注于MySQL源码研究、DBA运维、CGroup虚拟化及Linux Kernel源码研究等。 github:https://github.com/HengWang/ Email:king_wangheng@163.com 微博 :@王恒-Henry QQ :506437736

文章分类

全部博文(107)

文章存档

2014年(2)

2013年(38)

2012年(67)

分类: Mysql/postgreSQL

2012-12-16 22:23:06

目的

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

数据结构

       LF_DYNARRAY相关的数据结构定义在mysql源码的include/lf.hmysys/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表示总的层级数,默认为4LF_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数据结构中使用。具体的使用情况,可以参考对应数据结构的分析。

 

 

阅读(2981) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~