MySQL列：innodb的源代码的分析的基础数据结构

在过去的一年中的数据库相关的源代码分析。前段时间分析levelDB实施和BeansDB实现，数据库网络分析这两篇文章非常多。他们也比较深比较分析，所以没有必要重复很多劳力。MYSQL，当然主要还是数据库存储引擎，首先我还是从innodb这个最流行的开源关系数据库引擎着手来逐步分析和理解。

我一般分析源代码的时候都是从基础的数据结构和算法逐步往上分析。遇到不明确的地方，自己依照源代码又一次输入一遍并做相应的单元測试，这样便于理解。对于Innodb这种大项目，也应该如此，以后我会逐步将详细的细节和实现写到BLOG上。我分析Innodb是以MySQL-3.23为蓝本作为分析对象，然后再去比較5.6版本号的修改来做分析的。这样做有个优点就是先理解相对基础的代码easy。在有了基本概念后再去理解最新的修改。下面是我对innodb基础的数据结构和算法的理解。

1.vector

innodb的vector是个动态数组的数据结构。和c++的STL使用方法相似，值得一提的是vector的内存分配能够通过函数指针来指定是从heap内存池堆上分配内存还是用OS自带的malloc来分配内存。内存分配器的结构为:

        struct ib_alloc_t {
             ib_mem_alloc_t	mem_malloc; 				//分配器的malloc函数指针
             ib_mem_free_t	mem_release;  				//分配器的free函数指针
             ib_mem_resize_t	mem_resize;  				//分配器的又一次定义堆大小指针
             void*	 arg;     					//堆句柄，假设是系统的malloc方式，这个值为NULL
<span style="white-space:pre">	</span>};

vector内部集成了排序功能函数。其排序的算法是通过qsort（高速）来进行排序。

vector内存结构:

2.内存list

innodb的list数据结构是个标准的双向链表结构。ib_list_node_t其中有指向前一个node的prev和指向后一个

node的next，list的内存分配能够通过heap内存堆来分配，也能够通过系统的malloc来分配。

就看是採用

ib_list_create_heap来创建list爱是永ib_list_create来创建list。可是内部的ib_list_node_t的内存分配是通过

heap来分配的。

ist的内存结构:

3.FIFO-queue

innodb的FIFO queue是个多线程的消息队列。能够有多个线程向queue中加入消息，可有多个线程同一时候读取queue中的消息并进行处理。queue的mutex是保证同一时候仅仅有一个线程在操作（读或者写）queue的items链表,os_event是写线程完毕后通知全部读线程能够进行queue的读事件。也就是说，仅仅有向queue写完毕一个消息。才会发送event信号给读线程。queue的消息缓冲区是採用ib_list_t来做存储的。一般写的时候写在list的最后，而读总是读取list的第一个。

queue处理提供一直读取到消息为止的方法以外，也提供最长等待读取消息的方法。这样读取线程没有必要一直等待消息。能够在等待一段时间后去处理其它的任务。其C结构定义例如以下:

struct ib_wqueue_t
{
	ib_mutex_t	mutex; /*相互排斥量*/
	ib_list_t*	items; /*用list作为queue的载体*/
	os_event_t	event; /*信号量*/
};

4.哈希表

innodb中的哈希表的基本构造和传统的哈希表的构造是相似的，不同的就是innodb的哈希表採用的是自己定义链式桶结构。而没有採用每一个桶单元用传统的list来做碰撞管理。由于这个特性。innodb中的哈希表操作採用了一系列操作宏来做操作。这样做的目的是为了能泛型的对哈希表做操作，由于在innodb中，除了操作内存中的数据以外，还会操作隐射硬盘中的数据。下面是innodb的操作宏：

HASH_INSERT 插入操作

HASH_DELETE 删除操作

HASH_GET_FIRST 获取指定HASH key相应cell的第一个数据单元

HASH_GET_NEXT 获取cell_node相应的下一个单元

HASH_SEARCH 查找相应key的值

HASH_SEARCH_ALL 遍历整个hash table并将每一个数据单元为參数运行ASSERTION操作

HASH_DELETE_AND_COMPACT 删除操作而且优化和调整heap堆上的内存分配布局，使得heap效率更高

HASH_MIGRATE 将OLD_TABLE的数据单元合并到NEW_TABLE其中

这些宏在调用的时候都会指定数据的类型和Next函数名。

innodb的哈希表在多线程并发模式下也提供cell级粒度的锁，有mutex类型的锁。也有rw_lock类型的锁。

在hash_create_sync_obj_func函数调用过程中，会创建一个n_sync_obj的锁数据单元。n_sync_obj必须是2的N次方。也就是说假设n_sync_obj = 8, 哈希表的n_cells = 19。那就至少两个cell公用一个锁。

这是其它哈希表无法比拟的。

下面是hash table的结构定义：

struct hash_table_t
{
	enum hash_table_sync_t	type;		/*hash table的同步类型*/
	ulint			n_cells;	/*hash桶个数*/
	hash_cell_t*		array;		/*hash桶数组*/
#ifndef UNIV_HOTBACKUP
	ulint			n_sync_obj;
	union{ /*同步锁*/
		ib_mutex_t*	mutexes;
		rw_lock_t*	rw_locks;
	}sync_obj;
	/*heaps的单元个数和n_sync_obj一样*/
	mem_heap_t**		heaps;
#endif
	mem_heap_t*		heap;
	ulint			magic_n;	/*校验魔法字*/
#endif
};

5.小结

Innodb还有其它的一些数据结构，比如最小堆，这些都是通用的封装，也就不做过多的描写叙述，在能够去看看innodb的源代码相关就能够。innodb在定义数据结构的时候做了特殊的处理，比如对线程并发的控制。对内存分配的控制。

这样做的目的是为了统一的管理。

innodb的代码是C的。但支持C++。里面并没有使用STL这样的传统的数据结构和算法，非常大程度上是适合性的问题。

据说MYSQL 5.7開始大量使用boost 和STL。

个人感觉STL还勉强。使用boost有点感觉阔步前进。