前言
我们知道Innodb使用BTREE来进行数据组织存储，当发生INSERT/UPDATE/DELETE时，有可能会产生数据空洞，不能有效的利用page的空间。而这些空洞在未来甚至有可能不再被使用到。本文主要记录了相关的代码，现有的处理方式，最后介绍了facebook mysql对page碎片的处理方式.
DML对page空间影响
以下简述下三种操作类型对页面空间的影响
INSERT
即时是顺序的Insert，也可能产生空间浪费，为了保证以后对相同page的更新不会产生page分裂，Innodb总是为其保留一部分的剩余空间.
简单说一下，对于INSERT也分两种情况，直接INSERT 以及通过更改已有记录的方式来INSERT；第一种方式大家可能比较理解；对于第二种方式，假设这种场景：
CREATE TABLE t1 (a int, b int, c int, primary key(a,b));
INSERT INTO t1 (1,2,3);
DELETE FROM t1;
INSERT INTO t1 (1,2,6);
MySQL使用标记删除的方式来删除记录，如果DELETE和再次INSERT中间的间隔足够小，Purge线程还没来得及清理该记录时，新插入的(1,2,6)就会沿用之前的记录的位置，因为他们主键是相同的
参考函数：
row_ins_must_modify_rec
row_ins_clust_index_entry_by_modify
INSERT BY MODIFY的方式是，先将原记录的delete标记清除，然后再对该记录做update.
扯远了，这里我们只讨论第一种方式，在插入记录时，对于page 内数据大小是有个硬限制的：
从btr_cur_optimistic_insert函数截取的代码：
1399 /* If there have been many consecutive inserts to the
1400 clustered index leaf page of an uncompressed table, check if
1401 we have to split the page to reserve enough free space for
1402 future updates of records. */
1403
1404 if (leaf && !zip_size && dict_index_is_clust(index)
1405 && page_get_n_recs(page) >= 2
1406 && dict_index_get_space_reserve() + rec_size > max_size
1407 && (btr_page_get_split_rec_to_right(cursor, &dummy)
1408 || btr_page_get_split_rec_to_left(cursor, &dummy))) {
1409 goto fail;
1410 }
dict_index_get_space_reserve函数的返回值是十六分之一的page size，也就是说插入新记录后，留余的空闲空间不能小于这个1/16 *page size，默认16k配置下，就是1K
说到INSERT，就不得不提一个bug#67718，以主键逆序的方式插入记录可能导致索引分裂非常频繁。有人已经写了博客来描述这个问题，这里简单描述下.
假定page最多插入6条记录
子节点p1有数据(1,2,3,4,5,6)
插入记录（10），产生分裂新子节点p2(10)
插入记录（8），寻址到p1，PAGE_LAST_INSERT是6，满足顺序插入条件，但p1已满，产生新子节点p3(8)。
参考函数：
分裂选择： btr_page_get_split_rec_to_right btr_page_get_split_rec_to_left
顺序插入优化：page_cur_search_with_match.
Twitter的mysql fix掉了这个问题： patch连接. 官方在MySQL5.6.21及5.7.5发布fix.
UPDATE
对于更新操作，有两种方式，一种是IN-PLACE更新，另一种是先标记删除再插入新记录的方式。更新的顺序是总是先更新聚集索引，再更新二级索引。
对于二级索引记录更新，总是先标记删除再插入新记录。对于聚集索引，这两种情况都存在。例如如果没有改变记录大小（row_upd_changes_field_size_or_external），就直接In-place更新了（btr_cur_update_in_place），否则在代码逻辑上，总是先删除（page_cur_delete_rec）再插入记录（btr_cur_insert_if_possible），如果主键未变，则沿用其之前的聚集索引记录所在的位置，注意尽管主键不变，但如果记录长度变小了，依然会在page内产生碎片
如果更新的是聚集索引记录，引起索引顺序发生变化，则采用标记删除+插入（row_upd_clust_rec_by_insert）
很显然频繁的Update可能会导致空间膨胀，尤其是当二级索引比较多的时候。当然purge线程可以去回收被标记删除的空间，但page空间利用率依然会有所降低。
参考函数：
row_upd_clust_step //更新聚集索引非pk列
row_upd_sec_step //更新二级索引
btr_cur_del_mark_set_clust_rec
DELETE
实际上删除操作和update操作走类似的接口函数row_update_for_mysql，只是将prebuilt->upd_node->is_delete设置为TRUE来进行区分。使用标记删除的方式。
参考函数：
row_upd_del_mark_clust_rec
btr_cur_del_mark_set_clust_rec
row_upd_sec_index_entry->btr_cur_del_mark_set_sec_rec
Innodb的自我调节
页内调整
当page内的最大可用空间不满足记录插入时，可能会触发page内的数据重组（btr_page_reorganize）。即使空闲空间满足插入记录，还有一个硬限制来进行重组，即page大小的32分之一(BTR_CUR_PAGE_REORGANIZE_LIMIT)。
参考函数：
btr_page_reorganize
页面合并
当一个Page内的记录数过少时，有可能触发page合并，当发生悲观删除一条记录后，page的记录数小于1/2 page size时（BTR_CUR_PAGE_COMPRESS_LIMIT）, 可能触发。
早期有个bug#68501，innodb在确定合并的page是左节点还是右节点时，总是先尝试左节点，如果左节点是可用的，但是合并失败时，没有去再次尝试右节点页。在做逆序删除操作时，可能导致大量btr_compress失败，引起idb空间无法有效收缩。
Oracle mysql 在5.6.13版本fix了这个问题，当合并左节点失败时，会再次尝试右节点，具体可以浏览补丁Rev:4384
参考函数：
btr_cur_compress_if_useful
btr_compress
传统方案
optimize table、alter table tbname engine=innodb (MySQL 5.6.17及之后已经开始支持ONLINE)
dump/restore 数据集
Facebook实现的在线碎片整理
Fb的实现中，引入了一个独立的线程(btr_defragment_thread)来专门做碎片整理，每次从叶子节点开始，持有索引X锁，每整理N个page后释放锁，然后再继续执行。可以指定做defragement操作的索引是聚集索引还是二级索引。一次处理最多不超过32个page，以降低持有索引X锁的时间。
其大概流程为：
- 用户通过alter table tbname defragement [async_commit]发起请求
- innodb层(defragment_table)将用户请求加入一个任务队列（队列项为一个已经定位到leaf page的persistent cursor，初始化在第一个叶子节点页）.对于async_commit，直接返回，否则进入condition wait.
- 独立线程btr_defragment_thread读取任务队列，然后开始操作N个page，总是将记录尽量往左边的叶子节点页转移，当出现空page时，直接从btree删除。
- 做完一次操作后，如果达到索引末尾，则从任务队列删除，唤醒等待的用户线程，否则将item更新后，sleep一段时间，下一轮继续。
代码没怎么细看，感兴趣的同学可以参考fb-mysql的代码，或者这个commit
关于facebook的实现也可以参考该ppt
