Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1071466
  • 博文数量: 646
  • 博客积分: 288
  • 博客等级: 二等列兵
  • 技术积分: 5375
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-08 14:33
个人简介

为了技术,我不会停下学习的脚步,我相信我还能走二十年。

文章分类

全部博文(646)

文章存档

2014年(8)

2013年(134)

2012年(504)

分类: Mysql/postgreSQL

2013-02-25 09:09:21

目的

       在MySQL的SQL层源码中,链表(Linked list)数据结构是使用最频繁、应用最广泛的结构之一,是SQL各个数据结构的基础结构。本文分析MySQL在SQL层的所有链表结构,以便于分析SQL层其他复杂数据结构。

数据结构

       MySQL的SQL层基本是C++代码,因此数据结构不是单纯的存储结构,而会涉及到class的继承。链表数据结构的源码在MySQL源码的/sql/sql_list.cc、/sql/sql_list.h,包含所有与链表相关的数据结构和操作。

       在SQL层,MySQL的链表结构包括两类:单项链表结构和双向链表结构。以下分别对这两种链表进行分析:

       单向链表:base_list是链表的头结点,first和last分别指向链表的第一个和最后一个结点,elements表示链表中的结点个数;list_node是链表中的结点,next指向下一个结点的地址,info指针指向存储数据的具体地址。具体如下:

 

图1 单向链表结构

 

       双向链表:base_ilist是双向链表的头结点,first和last指针分别指向双向链表的第一个和最后一个结点;ilink是双向链表中结点的数据结构,prev指针指向结点的前驱结点,next指向当前结点的下一个结点。与单向链表不同的是:base_ilist头结点中没有表示链表中数据结点个数的变量,这与ilink结点的结构相关;ilink结点中没有指向存储数据的结点指针,这是考虑到该结构可以链接任意数据结构,具体数据结构类型和数据的内容,双向链表都不关心,这也解释了头结点中没有必要记录数据结点的个数。具体如下所示:

 

图2 双向链表结构

 

       在实际的实现中,为了适用于不同数据结构,链表结构设计并没有那么简单。以下是整个单向链表数据结构的UML设计图,其中:Sql_alloc数据结构定义了内存分配相关的操作;SQL_I_List是SQL相关的链表结构,该结构是泛型类型,应用于TABLE_LIST、ORDER等数据结构;list_node是struct结构,是链表的结点;base_list是链表的头结点,并且该结点与base_list_iterator和error_list_iterator数据结构是友元关系(friend);base_list_iterator是base_list结构的迭代器,用于遍历base_list中的所有数据结点;List类继承base_list,对外提供服务,主要应用在Item、Item_field、field、handler以及存储引擎接口等结构中;而List_iterator和List_iterator_fast继承base_list_iterator,实现了两种遍历的List的不同方式,具体的差异是List_iterator_fast增加了sublist方法,并且将replace、remove、after以及ref函数的可见性定义为protected,具体的实现,由子类重写实现。


图3 单向链表UML设计图

 

       双向链表中,结点ilink派生了两种数据类型,i_string用于存储字符类型,i_string_pair用于存储key/value结构的字符类型。这两种结构主要用于满足字符或字符对存储的要求,其中i_string广泛应用在各个结构或处理中,而i_string_pair主要应用在复制过滤处理中。具体的UML设计图如下所示:


图4 ilink的UML设计图

 

       双向链表的设计如下所示,其中:base_ilist是表头结构,与base_ilist_iterator是友元关系;base_ilist_iterator是遍历base_ilist的迭代器;I_List是双向链表对外提供服务的结构,广泛应用在keycache、复制过滤、查询等子系统中,与I_List_iterator是友元关系;I_List_iterator继承自base_ilist_iterator,是I_List的迭代器。具体如下所示:

 

图5 双向链表UML设计图

 

       由于链表作为数据结构最基本的结构之一,具体的源码实现,不进行赘述。

结论

       通过对MySQL的SQL层的链表结构进行分析,作为SQL层的基础数据结构,提供了单项链表和双向链表两种结构,以及丰富的基本操作,为SQL层的复杂数据结构提供基础服务。


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