Mysql存储及索引

MySQL存储引擎包括：MyISAM引擎，MyISAM Merge引擎，InnoDB引擎，Memory引擎，NDB引擎，Archive引擎，CSV引擎，Federated引擎，Blackhle引擎，NDB Cluster引擎，Falcon引擎，SolidDB引擎，PBXT引擎，Maria引擎和其它引擎。建表时，选择合适的存储引擎很重要，如果到后期再更换将会很麻烦。这里，我们只介绍常用的三种存储引擎：存储引擎是基于表的，而非数据库。

ＭＹＳＱＬ　存储引擎

MyISAM引擎
MyISAM引擎是MySQL默认的存储引擎，MyISAM不支持事务和行级锁，所以MyISAM引擎速度很快，性能优秀。MyISAM可以对整张表加锁，支持并发插入，支持全文索引。
InnoDB引擎
InnoDB是专为事务设计的存储引擎，支持事务，支持外键，拥有高并发处理能力。但是，InnoDB在创建索引和加载数据时，比MyISAM慢。
Memory引擎（采用哈希索引）
内存表，Memory引擎将数据存储在内存中，表结构不是存储在内存中的，查询时不需要执行磁盘I/O操作，所以要比MyISAM和InnoDB快很多倍，但是数据库断电或是重启后，表中的数据将会丢失，表结构不会丢失.

为何磁盘的读取所读远远低于内存的读取速度：

我们知道，内存的读数据是根据地址总线传送的地址在相应的内存单元把数据读取到数据总线的电信号操作。

而磁盘的读数据要先找对磁盘面，然后找到相应的扇区和磁道，与主存不同，磁盘读取数据是机械运动（寻道时间，旋转时间）主存和磁盘以页为单位交换数据先读取数据到内存，再进行从内存上的读取。主存和磁盘以页为单位交换数据。

 

InnoDB存储引擎体系架构

 

内存池：（缓冲磁盘与cpu读取速度的鸿沟(原因上面已解释过)）

1. 维护所有进程/线程需要访问的多个内部数据结构。

2. 缓存磁盘上的数据，方便快速的读取，同时在对磁盘文件的数据修改之前在这里缓存。

3. 重做日志缓冲等。

    

   
   

   对于在数据库中页的修改操作，则首先修改在缓冲池中的页，再刷新到磁盘上（采用checkpoint机制）。（见下附。）

   每页根据哈希值平均分配到不同缓冲池实例中，减少了数据库内部资源的争夺，增加并发性。

   通过LRU（最近最久未使用）算法进行管理。（LRU List，Free List，Flush List）

   LRU 列表：管理已经读取的页。

   Free List：存放可用的空闲页。

   Flush List：存放脏页列表，（需要刷新回磁盘的页）。

    

   LRU算法在源码上的体现：

   LRU算法在源码上的体现：
   void
   buf_flush_insert_sorted_into_flush_list(	buf_block_t*	block) //in: block which is modified 
   {
   	buf_block_t*	prev_b=NULL; 
   buf_block_t*	b;
   ut_ad(mutex_own(&(buf_pool->mutex)));
   	b = UT_LIST_GET_FIRST(buf_pool->flush_list);
   
   while (b && (ut_dulint_cmp(b->oldest_modification,block->oldest_modification) > 0)) {
   		prev_b = b;
   		b = UT_LIST_GET_NEXT(flush_list, b);
   	}
   
   	if (prev_b == NULL) 
   {
   	   UT_LIST_ADD_FIRST(flush_list, buf_pool->flush_list, block);
   	} 
   Else
    {
   		UT_LIST_INSERT_AFTER(flush_list, buf_pool->flush_list, prev_b,  block);
   	 }
   ut_ad(buf_flush_validate_low());
   }
   

   重做日志缓冲：

   将重做日志信息先放到这个缓冲区，然后再刷新回日志文件。

   额外缓冲区：

   　　相当于内存中的堆。

   checkpoint机制：当有事务提交时，先写重做日志，再修改页。优点：当计算机发生宕机的时候，如果没有ｃｈｅｃｋｐｏｉｎｔ　技术，在从缓冲池将脏页刷新回磁盘时发生宕机，则数据无法恢复，反之，若有，则可通过重做日志完成数据恢复。（并非重做所有日志，只需将ｃｈｅｃｋｐｏｉｎｔ后的重做日志恢复，因为之前的都已经重新刷回磁盘了）。

    

   后台线程：

    后台线程的主要作用是负责刷新内存池中的数据，保证缓冲池中的内存缓存的是最近的数据。此外，将已修改的数据文件刷新到磁盘文件，同时保证在数据库发生一场的情况下InnoDB能恢复到正常的运行状态。

   MasterThread：负责将缓冲池中的数据异步刷新到磁盘，保证数据的一致性，包括脏页的刷新，合并插入缓冲（insertbuffer），undo页的回收等。

   IOThread:负责io请求的回调（call back）处理。有4个io线程，write，read，insert buffer，和log io thread。

   PurgeThread：回收已经使用并分配的undo页。

   Pagecleaner Thread：将之前版本中脏页的刷新操作都放入到单独的线程中完成。（减轻masterThread的工作，提高存储引擎的性能）。

    

   InnoDB的”魅力”(关键特性)

   插入缓冲（insertbuffer）：操纵对象：辅助索引页，通过b+树组织的物理页，对于非聚集索引的插入或者更新操作(因为聚集索引是按主键递增的顺序进行插入的，所以对于聚集索引不需要Insert Buffer 可以直接进行顺序读取)，不是每次直接插入到索引页中的，而是判断插入的非聚集索引页是否在缓冲池中，若在，则直接插入，否则，先放在InsertBuffer对象中，就像是已经插入到已经插入到索引的叶子节点，而实际并没有，只是存放在另一个位置，然后再以一定的频率和情况进行InsertBuffer（B+树）和辅助索引叶子节点的Merge*（合并）（合并的时机在下面讲解）操作，这时，通常能将多个插入合并到一个操作中（因为在一个索引页中），这样就极大地提高了非聚集索引的插入性能。

    

   两次写（double write）：如果发生宕机怎么办？1重做日志进行恢复。2 Double write

           

   Double write：在对缓冲池的脏数据进行刷新时，并不直接写磁盘，而是会通过memcpy函数将脏页先复制到内存的doublewriter buffer ，然后通过doublewriter Buffer分两次，每次1MB顺序的写入共享表空间的物理磁盘上。然后马上调用fsync函数，同步到磁盘（从内存到数据文件）。在完成doublewrite页的写入后，再将doublewrite Buffer中的页写入各个表空间文件中。

          如果系统在将页写入磁盘的过程中发生崩溃，在恢复过程中，InnoDB存储引擎可以从共享表空间中的doublewrite中找到该页的副本，将其复制到表空间文件，再应用重做日志。

    

   Double write源码分析见下面：

    

    

   自适应哈希索引（Adaptive Hash Index）：快，查找的时间复杂度是O（1），相比于B+树，需要查找树的深度次查找。快，不需要对整张表构建哈希索引。

              InnoDB存储引擎会自动根据访问的频率和模式自动为某些热点页建哈希索引（不受ＤＢＡ控制，自动生成），但需求必须（只能）是搜索等值的查询，where a=”XXX”，而不能是范围查询，如where (x>”XXX”andX<”XXX”)。如果是联合索引，就需要(必须)where a=”Xxx”来触发，若直接光用第二个是不会利用索引查找的。

   

    

   自适应哈希索引源码分析见下：

    

   异步io（Async io）：相对于异步IO，如果需要扫描多个索引页时，必须等待一个页扫描完成后再进行下一次扫描。异步IO用户可以在发出一个IO请求后再发另一条IO请求，当所有IO请求发送完毕后，等待所有IO操作的完成，这就是异步IO。

   刷新连接页（flush neighbor page）：当刷新一个脏页时，InnoDB存储引擎会检测该页所在的区的所有页，如果是脏页，那么一起进行刷新。这样做好处是通过异步IO将多个IO写合并成一个IO操作。

    

    

   插入缓冲（insert buffer）

    

   InsertBuffer 的使用需要同时满足以下两种情况：

                1索引是辅助索引（原因上述已解释）

                2索引不是唯一的（数据库并不去查找索引页来判断插入记录的唯一性，如果去查找肯定又会有离散读取的情况发生）

               我们在辅助索引页之上还建立了 Insert Buffer bitmap，InsertBuffer bitmap是用来追踪辅助索引页1剩下多少可用空间，2该辅助索引页是否有记录被缓存在Insert Buffer B+树中3该页是否为InsertBuffer B+树的索引页

               Ibufoibuf.c中voidibuf_bitmap_page_init对bitmap进行初始化（全为零，因为刚开始进行插入缓冲区的使用所以没有记录任何信息）。

    

             Merge Insert Buffer的操作发生的情况：

              1辅助索引页被读取到缓冲池时（通过检查Insert Buffer map页，确认该辅助索引页是否有记录存放在Insert Buffer中若有，则将InsertBuffer B+ 树中该页的记录插入到该辅助索引页中（将多次IO磁盘插入操作合并为一次磁盘操作））。

              2 Insert Buffer map页用来追踪辅助索引页中有多少可用空间，如果将记录插入辅助索引页时，发现可用空间小于1/32（这个数据是可以设置的IBUF_PAGE_SIZE_PER_FREE_SPACE）页时，会强制进行一次合并操作

               3主线程以一定的时间进行合并操作。

    

    

   Insert buffer 分析

Ibool  ibuf_insert()函数调用
Static ulint ibuf_insert_low( )函数实现插入记录
{
	ibool		do_merge;//是否合并
	ut_a(!(index->type & DICT_CLUSTERED));//必须是非聚集索引
do_merge = FALSE;
if (ibuf->size >= ibuf->max_size + IBUF_CONTRACT_DO_NOT_INSERT)//如果插入缓冲池太大，对其进行缩小但不会再试图插入。
    {
		ibuf_contract(TRUE);//缩小缓冲池
	return(DB_STRONG_FAIL);
	}
    
	if (mode == BTR_MODIFY_TREE)//需要进行分裂操作的模式
{	
while (!ibuf_data_enough_free_for_insert(ibuf_data)) //看插入缓冲的ＦＲＥＥ＿ＬＩＳＴ里是否有足够的ｆｒｅｅ页。
{

			err = ibuf_add_free_page(0, ibuf_data);／／申请一个新页加入到ｆｒｅｅｌｉｓｔ里
	　　　　}
	}

	ibuf_entry = ibuf_entry_build(index, entry, space, page_no, heap);／／创建记录
　　　
if (buffered + entry_size + page_dir_calc_reserved_space(1)//假设插入后的大小超过了缓冲池的容量的上限
>ibuf_index_page_calc_free_from_bits(bits)) 
{ 
do_merge = TRUE;
	  ibuf _merge_page ();//进行合并操作
	}

	ibuf_bitmap_page_set_bits()//对ibuf_bitmap进行相应位的修改

	cursor = btr_pcur_get_btr_cur(&pcur);

	if (mode == BTR_MODIFY_PREV)
 {
		err = btr_cur_optimistic_insert(BTR_NO_LOCKING_FLAG, cursor, ibuf_entry, &ins_rec,
						&dummy_big_rec, thr,
						&mtr);
}
	
	Else
 {
		ut_ad(mode == BTR_MODIFY_TREE);
root = ibuf_tree_root_get(ibuf_data, 0, &mtr);
err = btr_cur_pessimistic_insert(BTR_NO_LOCKING_FLAG| BTR_NO_UNDO_LOG_FLAG,
						 cursor,
						 ibuf_entry, &ins_rec,
						 &dummy_big_rec, thr,
						 &mtr);
}
	Func_exit();//退出操作
}

Double write源码分析： 

1当我们需要请求一页而缓冲区中没有可用页给我们

2或者当我们提交一个页在写完成后提交时且InnoDB存储引擎通过判断当前缓冲池中脏页的比例（buf_get_modified_ratio_pct）超过了配置文件中innodb_max_dirty_pages_pct这个参数（默认为90，即90%），如果超过了这个阈值，InnoDB存储引擎认为需要做磁盘同步操作，将100个脏页写入磁盘

Void  buf_flush_post_to_doublewrite_buf(buf_block_t*	block)	/* in: buffer block to write */
{
try_again:
    如果缓冲池已经被使用的大小超过了buff_write  块的大小（两块）
if (trx_doublewrite->first_free>= 2 * TRX_SYS_DOUBLEWRITE_BLOCK_SIZE) // first_free将要写的页的个数
// TRX_SYS_DOUBLEWRITE_BLOCK_SIZE表空间的一块所包含页的个数。
{	
buf_flush_buffered_writes();//对缓冲池中的double writer Buffer 进行刷新操作
	goto try_again;
	}
     将页的内容拷贝到缓冲区上

	ut_memcpy(trx_doublewrite->write_buf + UNIV_PAGE_SIZE * trx_doublewrite->first_free,
		  block->frame, UNIV_PAGE_SIZE);
   如果插入后超标刷新。
	if (trx_doublewrite->first_free
	    >= 2 * TRX_SYS_DOUBLEWRITE_BLOCK_SIZE) 
{
		mutex_exit(&(trx_doublewrite->mutex));
		buf_flush_buffered_writes();
	return;
	}
}
下面来看如何将缓冲区的内容刷新到磁盘和共享表空间的
Static void buf_flush_buffered_writes(void)
{
if (!srv_use_doublewrite_buf || trx_doublewrite == NULL) 
{
		os_aio_simulated_wake_handler_threads();
	    return;
}
对将要刷新的每一页进行日志***检查等检查操作
使用同步IO进行写。
第一次刷新到共享表空间前1M

   fil_io(OS_FILE_WRITE, TRUE, TRX_SYS_SPACE, trx_doublewrite->block1, 0, len,
	       (void*)trx_doublewrite->write_buf, NULL);

//trx_doublewrite->write_buf,从这里开始写
// len 将要写的长度
写到表空间fil_system_t*	fil_system
第二次刷新到共享表空间后1M
fil_io(OS_FILE_WRITE, TRUE, TRX_SYS_SPACE, trx_doublewrite->block2, 0, len,
		       (void*)(trx_doublewrite->write_buf+ TRX_SYS_DOUBLEWRITE_BLOCK_SIZE
			       * UNIV_PAGE_SIZE), NULL);
将double write共享表中的内容刷新到磁盘
fil_flush(TRX_SYS_SPACE);
	
for (i = 0; i < trx_doublewrite->first_free; i++) 
{
		block = trx_doublewrite->buf_block_arr[i];
	fil_io(OS_FILE_WRITE | OS_AIO_SIMULATED_WAKE_LATER,
		       FALSE, block->space, block->offset, 0, UNIV_PAGE_SIZE,
		       (void*)block->frame, (void*)block);将double_write_buff中的内容刷新到自己的表空间
}
    将表空间的内容刷新到磁盘
	fil_flush_file_spaces(FIL_TABLESPACE);

//double_write_buff又重新可用了~~~
	trx_doublewrite->first_free = 0;
}

 

自适应哈希源码解读：

srv_use_adaptive_hash_indexes标记（禁止或者启动自适应哈希索引）

buf_pool_init中：

srv_use_adaptive_hash_indexes 标记（禁止或者启动自适应哈希索引）
buf_pool_init中：
 if (srv_use_adaptive_hash_indexes) 
{
btr_search_sys_create(curr_size * UNIV_PAGE_SIZE/ sizeof(void*) / 64);
}
 else 
{
	/* Create only a small dummy（虚设的） system */
 btr_search_sys_create (1000);
}
btr_search_sys_create（ulint	hash_size// hash index hash table size）
此函数功能是在数据库启动的时候创建并初始化自适应查找系统
在此函数中：
btr_search_sys->hash_index = ha_create(TRUE, hash_size, 0, 0);
btr_search_sys->hash_index = ha_create(hash_size, 0, 0);

 

 

刷新邻接页：

体现出我们在刷新数据时，不是只刷一页，而是将页的所在的区能刷新的都进行刷新。

Static ulint buf_flush_try_neighbors(ulint	space, ulint	offset,	ulint	flush_type) type:BUF_FLUSH_LRU or BUF_FLUSH_LIST
{
	buf_block_t*	block;
	ulint		low, high;
	ulint		i;
     low 和hight记录在此区内，从哪里到哪里需要刷新。
     for (i = low; i < high; i++)
{
block = buf_page_hash_get(space,     i);//返回文件页的控制块
//space id    offset of the page within space
if (buf_flush_ready_for_flush(block, flush_type)&& (i == offset || block->buf_fix_count == 0)) 
//只对此条件成立的页进行刷新  block->buf_fix_count == 0代表block 没有上锁
// buf_flush_ready_for_flush(block, flush_type)//如果是flush list 直接ready，如果是LRU list && block->buf_fix_count == 0方为ready。否则都是not  ready 
{ 
buf_flush_try_page(space, i, flush_type);//把这页异步地从缓冲池写到磁盘上去（关于这步的详解u见下面）
}
}
}

buf_flush_try_page   函数在刷新时又调用 buf_flush_write_block_low()函数（做页的异步写工作）
if (!srv_use_doublewrite_buf || !trx_doublewrite)//如果没有使用double write 策略，则直接磁盘IO写
 {
		fil_io(OS_FILE_WRITE | OS_AIO_SIMULATED_WAKE_LATER,
		       FALSE, block->space, block->offset, 0, UNIV_PAGE_SIZE,
		       (void*)block->frame, (void*)block);
	} 
Else否则刷到doublewrite缓冲区中
 {
		buf_flush_post_to_doublewrite_buf(block);
	}

 

了解数据库的存储结构：

层次结构图：

逻辑存储结构：

每张表的表空间内存放的只是数据，索引和插入缓冲bitmap页，其他数据如插入缓冲索引页，二次写缓冲区等都仍存在共享表空间

常见的段有数据段，索引段回滚段等

 

对总体有概念之后我们再来看数据页结构

 

File Header 用来记录：

Checksum的值，表空间中页的偏移量（FIL_PAGE_OFFSET），

当前页的前一个页和当前页的后一个页（B+树特性决定其叶子节点是双向链表FIL_PAGE_PREV，FIL_PAGE_NEXT）

该页最后被修改的日志序列位置LSN（FIL_page_lsn）

页的类型：（与我们后面讲解相关的类型）FIL_PAGE_INDEX（B+树叶节点）FIL_PAGE_INODE（索引节点）FIL_PAGE_IBUF_BITMAP（InsertBuffer位图）

 

该页属于哪个表空间

 

Page Header用来记录：（include/pageopage.c/page_create）

索引ID（ＰＡＧＥ＿ＩＮＤＥＸ＿ＩＤ）

当前页在索引树中的位置　０表示叶子节点（ＰＡＧＥ＿ＬＥＶＥＬ）

该页中记录的数量（ＰＡＧＥ＿Ｎ＿ＲＥＣＳ）

 

 

 

索引

 

什么是索引

 

索引是一种数据结构。

既是一种数据结构就会占内存空间。索引本身很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。索引检索需要磁盘I/O操作，上面讲述过磁盘读取和内存读取的差别，哈哈（几个数量级），所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。

 

 下面讲解中我们将用到的数据结构B+树：

 

InnoDB存储引擎支持的几种常见索引：

B+树索引：并不能找到一个给定健值的具体行，B+树索引只能找到被查找数据行所在的页，然后从数据库将页读入内存，在内存中查找。B+树索引可以分为聚集索引和辅助索引。

全文索引

哈希索引

 

聚集索引

这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键。

按照表的主键构建一颗B+树。

键值的逻辑顺序决定了表中对应行（记录集）在逻辑地址上是连续的，注意：很多书上说是在物理地址上连续，其实是指逻辑地址连续。

 

聚集索引查询速度快，叶子节点的数据就是用户需要查询的数据。

 

聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。例如，如果应用程序执行的一个查询经常检索某一日期范围内的记录，则使用聚集索引可以迅速找到包含开始日期的行，然后检索表中所有相邻的行，直到到达结束日期。

 

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

 

非聚集索引：（辅助索引）

叶节点的data域存放的是数据记录的地址，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。（MYISAM采用此种索引方式）

 

辅助索引：

 

不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大

 

对于建立辅助索引的表需要先根据辅助索引找到相应的主键，再根据主键在聚集索引中找到相应的记录集。

MYSQL数据库的操作过程

对于目前的MySQL来说，所有的对于索引的添加或者删除操作，MySQL数据库都是要先创建一张新的临时表，然后再把数据导入临时表，再删除原来的表，然后再把临时表命名为原来的表。所以，如果一张表中数据太多的话，那么后期添加删除索引需要花费很长的时间，因而最好在数据库设计初期便设计好索引。

 

B+树与B-树应用于数据库的的区别：

1 b+树叶子节点存放记录集，分支节点只存放键值，这样，每页上存放的键值数就越多，磁盘i/O的置换就越少，相对就快。

2 b+树的叶子节点有指向兄弟的指针，所以既可以进行随机访问，也可以进行顺序访问。提高区间访问的性能，例如，如果想进行访问相邻多个叶子节点的数据，就可以直接根据指针进行访问。如图：如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

 

Cardinality:表示索引中唯一值的数目的估计值应尽可能接近1非常小时应考虑删除此索引。如性别，无非男女，如果建立索引，那么Cardinary==0.5,查询结果并不能直接的显示我们所需要的结果，故建立像这样的索引是没有意义的。非重复的行/总行（大约的值，不精确）

 

 

联合索引：对表上的多个列进行索引。对于a列的查询，或者a b 列的查询，都能用到联合索引，但直接用b列查询时不能用到联合索引（必须使用第一列进行触发）联合索引的第二个列也是排好序的。

对于联合索引（a,b,c）,是根据先对a，然后是b,最后是c的这样的排序顺序，

所以如果是select …from …where a=XXXorder by c是不能直接联合索引的

先使用联合索引找到A,然后在对C进行filesort排序操作才能得到结果。

如果是select …from …where a=XXXand b=XXxorder by c就是OK的，因为其排序顺序。