近一年来一直在分析关于数据库相关的,前段时间分析了levelDB的实现和BeansDB的实现,这两个网络上分析的文章很多,也都比较分析的比较深,所以也就没有太多必要重复劳动。最近开始关注关系数据库和MYSQL,当然主要还是数据库存储引擎,首先我还是从innodb这个最流行的开源关系数据库引擎着手来逐步分析和理解。我一般分析源码的时候都是从基础的数据结构和算法逐步往上分析,遇到不明白的地方,自己按照源码重新输入一遍并做对应的单元测试,这样便于理解。对于Innodb这样的大项目,也应该如此,以后我会逐步将具体的细节和实现写到BLOG上。我分析Innodb是以MySQL-3.23为蓝本作为分析对象,然后再去比较5.6版本的改动来做分析的。这样做有个好处就是先理解相对基础的代码容易,在有了基本概念后再去理解最新的改动。以下是我对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链表,Z喎"http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc19ldmVudMrH0LTP37PMzeqzybrzzajWqsv509C2wc/fs8y/ydLUvfjQ0HF1ZXVltcS2wcrCvP6jrNKyvs3Kx8u1o6zWu9PQz/JxdWV1ZdC0zeqzydK7uPbP+8+io6yyxbvht6LLzWV2ZW500MW6xbj4tsHP37PMoaNxdWV1ZbXEz/vPoru6s+XH+MrHssnTw2liX2xpc3RfdMC01/a05rSitcSjrNK7sOPQtLXEyrG68tC01NpsaXN0tcTX7rrzo6y2+LbB19zKx7bByKFsaXN0tcS12tK7uPaho3F1ZXVltKbA7czhuanSu9axtsHIobW9z/vPos6q1rm1xLe9t6jS1M3io6zSsszhuanX7rOktci0/bbByKHP+8+itcS3vbeoo6zV4tH5tsHIoc/fs8zDu9PQsdjSqtK71rG1yLT9z/vPoqOsv8nS1NTatci0/dK7ts7KsbzkuvPIpbSmwO3G5Mv7tcTIzs7xoaPG5EO94bm5tqjS5cjnz8I6CjxwcmUgY2xhc3M9"brush:sql;">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有点步子迈大了的感觉。