Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1347665
  • 博文数量: 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-10 23:22:53

目的

       MySQL目前版本尽管不支持HASH索引,但在源码实现中,HASH数据结构的应用却非常广泛。MySQLHASH数据结构使用链地址法处理键值冲突,特别的是,HASH的存储使用动态数组,采用静态链表的方式存储。以下内容中,对MySQLHASH数据结构及核心处理方法进行详细的分析,并简单举例,更清晰的描述HASH数据结构的处理过程。

数据结构

       HASH相关的数据结构定义在mysql源码的include/hash.hmysys/hash.c文件中,具体定义如下所示:

 

typedef uchar *(*my_hash_get_key)(const uchar *,size_t*,my_bool);

typedef struct st_hash {

  size_t key_offset,key_length;      /* Length of key if const length */

  size_t blength;

  ulong records;

  uint flags;

  DYNAMIC_ARRAY array;      /* Place for hash_keys */

  my_hash_get_key get_key;

  void (*free)(void *);

  CHARSET_INFO *charset;

} HASH;

typedef struct st_hash_info {

  uint next;                                               /* index to next key */

  uchar *data;                                          /* data for current entry */

} HASH_LINK;

 

       从定义可知,函数指针my_hash_get_key主要用于获得hash中的键值,在HASH数据结构中作为回调函数,根据实际应用场景定义。HASH数据结构中,key_offset表示关键字的偏移量;key_length表示关键字的长度;blength用于计算数据存放在array中的地址;records表示HASH中的记录数;flags表示HASH的操作相关的标志位;array存储HASH的键值,为DYNAMIC_ARRAY数据结构,相关操作参考《MySQL数据结构分析--DYNAMIC_ARRAY》;get_key为获取键值函数指针;free为释放HASH数据结构的函数;charsetHASH字符集。HASH_LINK数据结构用于初始化HASH结构中array的元素,其中data表示数据内容;next表示下一个键值的索引。

源码实现

       MySQL数据结构HASH的基本思想是:首先,使用数据结构HASH_LINK作为DYNAMIC_ARRAY数组array的元素,使得其组织方式是使用静态链地址法来存放HASH_LINK的每个元素,如果键值冲突,使用next指向下一个相同键值的元素在array中的地址,来获得相同键值的元素。如果存储数据不能重复,则通过flag标志,通过查找array中相同键值的元素是否匹配该数据即可。键值计算方法根据字符集的hash_sort方法进行计算。

       以下内容中,对几个重要的方法进行了说明,详细分析了几个核心的并且非常复杂的处理逻辑。更加详细的内容,参照mysys/hash.c源码文件。

_my_hash_init()函数

       _my_hash_init()函数是HASH数据结构的初始化函数,根据输入的参数,初始化HASH中的各个参数变量。特别注意的是,初始化array变量时,调用my_init_dynamic_array_ci()函数,array中每个元素的长度为HASH_LINK数据结构的大小。

my_hash_free()函数

       my_hash_free()函数是HASH数据结构的析构函数。首先调用my_hash_free_elements()析构array中的每个元素,并释放array结构,然后将free函数置空。

calc_hash()函数

       calc_hash()函数用于计算HASH值的方法,该函数通过调用字符集的处理函数hash_sort()获得。

my_hash_key()函数

       my_hash_key()函数用于从存储数据中,提取HASH的关键字。如果应用中提供了get_key函数,则通过get_key函数获得。否则通过key_offset值获得。

my_hash_mask()函数

       my_hash_mask()函数是通过关键字,计算array中的位置。该函数根据关键字的键值、blength参数的值和HASH中的记录数。

my_hash_rec_mask()函数

       my_hash_rec_mask()函数根据当前记录,获得关键字,调用calc_hash()重新计算键值并调用my_hash_mask()函数计算array中存储的位置。

my_hash_search()函数

       my_hash_search()函数通过关键字,查找数据内容。该函数调用my_hash_first()函数,查找第一个符合的数据并返回。

my_hash_search_using_hash_value()函数

       my_hash_search_using_hash_value()函数是通过HASH键值和关键字,查找相应的数据内容。该函数调用my_hash_first_from_hash_value()函数获得。

my_hash_first()函数

       my_hash_first()函数用于查找第一个符合查询关键字的记录。该函数调用my_hash_first_from_hash_value()函数获得。

my_hash_first_from_hash_value()函数

       my_hash_first_from_hash_value()函数是查找关键字或键值对应数据记录的实际处理函数。其处理逻辑是:首先根据键值,获得array中的地址,然后比较关键字是否匹配。匹配成功,直接返回当前数据内容。否则,调用my_hash_rec_mask()函数计算array的地址,如果与当前偏移不相等,则中断继续查询,查找失败,否则根据next的值,获得下一个相同键值数据记录的偏移地址,直到没有下一条数据为止。其中,hashcmp()函数用于比较关键字是否匹配,比较时依赖字符集,不做详细分析和说明。

       my_hash_first_from_hash_value()函数流程图如下所示:

 

1 my_hash_first_from_hash_value()函数流程图

 

my_hash_next()函数

       my_hash_next()函数查找键值的下一条数据记录,该函数必须首先调用my_hash_search()函数,根据返回到HASH_SEARCH_STATE的值,查找下一条数据记录。

my_hash_insert()函数

       my_hash_insert()函数用于插入记录到HASH中。主要处理逻辑是:首先,如果当前HASH必须关键字唯一,那么通过调用my_hash_search()函数查找是否有当前关键字,如果存在则直接返回。其次,根据关键字,为当前数据记录查找一个存储位置。在查找过程中,有两种处理方式,其中一种需要移动存储位置。最后,将当前记录插入到存储位置。

       my_hash_insert()函数流程图如下图2所示:

 

2 my_hash_insert()函数流程图

 

my_hash_delete()函数

       my_hash_delete()函数是从HASH表中删除记录。该函数的处理逻辑是:首先根据记录的关键字,计算键值,根据键值计算记录在array中的存储位置。如果记录不匹配,查找下一条记录。查找到相应的记录后,将array中最后一条数据记录进行调整。如果是键值相同,直接将最后一个位置的数据记录调整到删除位置,并修改链地址。否则需要进行调用movelink()函数进行链接调整。

       my_hash_delete()函数流程图如下图3所示:

 

3 my_hash_delete()函数流程图

 

my_hash_update()函数

       my_hash_update()函数是修改数据的处理函数。该函数的逻辑是:首先,如果不允许数据重复,那么需要首先验证当前记录是否在HASH表中,如果存在直接返回。其次,分别计算原关键字和当前记录关键字存储的位置,如果相等,不需要处理。否则,需要调整记录到正确的位置。

       my_hash_update()函数流程图如下所示:

 

4 my_hash_update()函数流程图

 

       以上是HASH数据结构的主要处理函数,实际上最核心的处理方法是my_hash_insert()my_hash_delete()my_hash_update()my_hash_first_from_hash_value()四个函数。通过这四个函数就可以实现对HASH数据结构的增、删、改、查基本操作。

举例

       由于以上逻辑分析比较难懂,为了进一步更加清晰的了解HASH的工作原理,以下将举例说明HASH数据结构的基本操作流程。

       为了简单起见,定义四条记录,分别是“a”“b”“c”“a”“d”,并且关键字也是这四个值,关键字长度是1,关键字偏移量是0,字符集为utf8

1、计算关键字的键值

       根据字符集的sort_order函数计算,得到四条记录的键值分别为:580587590580597

2、插入操作

       最初HASH表中为空,然后依次插入“a”“b”“c”“a”“d”五条记录。并且,插入过程输入的flag0HASHarray中的存储过程图示如下:

1) 插入“a”

       array“a”的存储地址索引idx=my_hash_mask(580,1,1)=0,插入位置pos=array+0,将pos位置的data指针指向“a”next值为-1。插入之后,info->records=1info->blength=2。具体如下所示

 

 

2) 插入“b”

       起初,array中的存储状态如下(1)所示。根据判断条件if (!(hash_nr & halfbuff)),即(!(580&1)),条件成功,不需要移动数据;此时,将gpos指针指向pos位置,如下(2)所示;计算“b”存放的地址,my_hash_mask(587,2,2)=1,将pos指向data+1位置,如下(3)所示;将pos->data指向“b”pos->next=-1,如下(4)所示。此时,info->records=2info->blength=4

 

1

2

3

4

 

3) 插入“c”

       插入“c”的过程同“b”类似,在(3)中,计算计算“c”存放的地址,my_hash_mask(590,4,3)=2,将pos指向data+2位置。插入后,info->records=3info->blength=4

 

1

2

3

4

 

4) 插入“a”

       首先,插入前的状态如下(1)中所示;根据判定条件if (!(hash_nr & halfbuff)),即if(!(587&2))为假,此时需要移动数据,确定移动位置gpos2指向最后位置,empty指向pos位置,并将ptr_to_rec2指向移动记录“b”,如下(2)所示;如下(3)所示,将“b”移动到gpos2位置,next=-1;最后,计算当前记录“a”的索引地址idx=my_hash_mask(580,4,4)=0

pos指向data+idx位置。由于当前位置pos不是empty存放位置,那么将pos复制给empty,即empty指向最先插入的“a”gpos=data+my_hash_mask(580,4,4)=0,由于当前pos=gpos,则pos->data指向新插入的记录“a”pos->next=(empty-data)=1。具体如下(4)所示。此外,info->records=4info->blength=8

 

1

2

3

4

 

5) 插入“d”

       插入“d”之前,array的状态如下(1)所示;根据判定条件if (!(hash_nr & halfbuff)),即if(!(580&4))为假,此时需要移动数据,确定移动位置gpos2指向最后位置,empty指向pos位置,并将ptr_to_rec2指向移动记录“a”,如下(2)所示;由于(pos->next=1)!=-1,继续查找下一条记录,pos指向下一条记录,并且仍然需要移动数据。第一次循环后,flag=4,因此if(!(flag & HIGHFIND))条件为假,但if (!(flag & HIGHUSED))条件为真,将gpos2->data指向上一次的数据ptr_to_rec2gpos2->next=1flag=12,如下(3)所示;循环结束后,如下(4)所示,并且将gpos2指向pos位置,ptr_to_rec2指向pos->data“d”的索引idx=my_hash_mask(597,8,5)=1,由于pos!=empty,将empty赋值为posgpos=data+my_hash_mask(580,8,5)=4,即gpos指向data+4。此时,由于gpos!=pos,则将pos->data指向“d”pos->next=-1。此时,需要移动链地址的链接,调用movelink()函数,从gpos开始,将pos之前的记录的next指向empty,如下(5)所示;插入“d”之后,array中的状态如下(6)所示。此外,此时info->records=5info->blength=8

 

1

2

3

4

5

6

 

       从以上插入可以看出,blength主要用于计算数据存放的掩码值,当records等于blength时,该值增大一倍。如果出现键值冲突时,需要进行移动数据位置,调整链接值,新插入的数据总是放在链地址的末尾。

3、删除操作

       删除处理过程将以数据第一个“a”删除为例,进行详细说明。

       删除之前,需要首先获取“a”记录,然后再删除该记录。HASH中进行比较的是地址,因此只有相同地址的数据内容才能被删除。

       如下(1)所示,pos=data+my_hash_mask(580,8,5)=data+4;删除poslinkempty=data+pos->nextpos->data=empty->datapos->next=1,如下(2)所示;最后位置的数据的键值lastpos_nr=580pos=data+my_hash_mask(580,8,4)=data+0,如下(3)所示;最后将最后的数据“a”删除,如下(4)所示。此时,hash->records=4

 

1

2

3

4

 

       从删除操作来看,基本处理策略是将匹配的数据置换到最后位置,并调整置换数据的链地址,最终释放该数据资源即可。

       update操作相对较容易,主要是找到更新的数据,然后重新计算键值,调整之前的链地址和修改后数据的链地址。

结论

       通过详细分析HASH数据结构及核心操作的基本处理逻辑,并举例说明HASH具体的处理过程,对MySQLHASH有深入的理解。分析发现,该HASH实现通过静态链地址法,连续存储数据,有效的提高了空间的利用率。然而,这也使得在键值出现冲突时,需要进行调整链地址和修改数据指针,调整代价较高。此外,使用blength来计算键值存放地址时,会导致键值冲突较频繁,以举例的插入即可看出。

       HASH数据结构在MySQL的很多处理过程及子系统中都有应用,如:用户认证子系统、plugin子系统、replication复制子系统、sql层的很多处理过程中等都有使用。

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