2014年(20)
分类: Mysql/postgreSQL
2014-10-14 11:44:19
原文地址:MySQL数据结构分析—sql_list 作者:king_wangheng
目的
在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层的复杂数据结构提供基础服务。