一、B树基础 在B树的定义中，中间节点存储n个键值和n+1个指针，下面是一个乌托邦式的B树实例。在这个实例中可以看到，每个键值存储的都是其紧邻右侧指针指向子树的最小值。   但是比较特殊的是第一个键值的左边还有一个指针，这个指针也是n+1个指针中(+1)的由来。那么为什么要使用n+1个指针而不是直观上更为简洁而工整的n个<键值、指针>对呢？其实看一下下面图的结构就可以知道，   假设说没有最左指针，成为下面结构，那么在每次插入一个最小值的时候，这个最小值需要在B树上逐层向上传递。对于这个场景，假设现在插入一个键值为50的记录，那么这个不仅B节点需要修改，而且其父节点N中指针对应的键值也要由100修改为50，并且由于100同样是N节点的最左元素，这个值还需要向可能的更上层的节点传递。这样看来，如果中间节点使用简单的n个<键值、指针>结构虽然看起来更简洁，但是在实际应用中还是使用了n+1个指针以减少插入最小元素时可能的上层节点修改，在考虑到磁盘操作的代价以及原子性的保证，这个成本相对较高，而使用一个最左指针可以很好的规避这个问题。 这个多处来的一个指针在中间节点分裂的时候同样将会带来一个微妙的问题。对于上面的例子，假设说插入一个新的键值290，此时C节点发生分裂，并进而导致N节点分裂。按照常规理解，将新分裂节点的键值280插入父节点之后发现一个尴尬的问题：N2的最左指针没有地方可以指向，成了孤寡老人。 事实上，这个问题是B树中间接点分裂时必然遇到的问题。满节点中有n个键值，n+1个指针；插入一个键值之后变成n+1键值，每个键值有自己对应的右侧指针，分裂之后的两个节点都有自己的最左指针，两个节点共2个最左指针，所以指针总数为n+1+2=n+3个。但是叶子节点只是进行了一次分裂，所以节点数是在原来n+1的基础上加上1个，也就是n+2个叶子节点，这必然导致有一个指针无处安放。所以，B树解决这个问题的方法是分裂点的记录在分裂之后上提到父节点中，对于上面的例子，就是N2中的280键值上提到更上层节点中(并删除它对应的右侧指针)，从而空出一个叶子节点，这样达到再次平衡。 二、innodb中B树对页面分裂的实现 n+1个指针的最左指针比较特殊，因为它对应的键值在自己的右边，并且是小于键值，其它的指针的意义和这个则相反。另外，中间节点分裂之后需要将一个节点上提的动作也有点意思，所以可以看下innodb中对于这个烦琐的操作如何处理。 1、最左指针如何表示 在典型的搜索流程btr_cur_search_to_nth_level===>>>page_cur_search_with_match的流程中，在页面上对记录进行简单的二分查找，并没有看到对最左指针的特殊处理。page_cur_search_with_match返回之后，btr_cur_search_to_nth_level函数也不客气，直接就从结构的最后解析处指针位置(也就是子节点页面编号page_no)。总之整个过程行云流水，丝毫没有看到对于最左节点的特殊关照。下面是btr_cur_search_to_nth_level函数中对于中间节点指针的暴力解析 node_ptr = page_cur_get_rec(page_cursor); offsets = rec_get_offsets(node_ptr, cursor->index, offsets,   ULINT_UNDEFINED, &heap); /* Go to the child node */ page_no = btr_node_ptr_get_child_page_no(node_ptr, offsets); 2、是否是使用infinum结构来存储指针？ 这个从一个新B树内部节点的创建说起，一个典型而重要的场景就是下面的btr_root_raise_and_insert函数， btr_root_raise_and_insert( /*======================*/ /* out: inserted record */ btr_cur_t* cursor, /* in: cursor at which to insert: must be on the root page; when the function returns, the cursor is positioned on the predecessor of the inserted record */ dtuple_t* tuple, /* in: tuple to insert */ mtr_t* mtr) /* in: mtr */ { …… /* Allocate a new page to the tree. Root splitting is done by first moving the root records to the new page, emptying the root, putting a node pointer to the new page, and then splitting the new page. */   new_page = btr_page_alloc(index, 0, FSP_NO_DIR,   btr_page_get_level(root, mtr), mtr); …… /* Move the records from root to the new page */   page_move_rec_list_end(new_page, root, page_get_infimum_rec(root),        index, mtr); ……     /* Insert node pointer to the root */   page_cur_set_before_first(root, page_cursor);   node_ptr_rec = page_cur_tuple_insert(page_cursor, node_ptr,      index, mtr); 首先简单描述下根节点分裂的流程：分配一个新页面，将当前根节点的所有记录拷贝到新新页面，删除根节点上所有记录，将待插入节点插入到已清空根节点中，之后新页面再分裂。 在根节点清空之后，新插入节点的位置在哪里，是否是第一条infinum记录？这个地方其实非常明显，其插入位置由page_cur_set_before_first确定，而这个函数就是将游标设置到第一个“用户记录”前，也就是infinum记录的位置，之后page_cur_tuple_insert插入的位置其实就是infinum之后。注意：不是使用了infinum记录，而是插入在infinum记录之后，也就是说innodb并没有最左指针的概念。 3、没有最左指针的窘境 如果没有最左指针，那么就会遇到前面提到的问题：每次插入最小值(即使插入记录没有导致页面分裂)的时候都可能导致这个最小值向上层传递。但是在btr_cur_optimistic_insert函数中，也通常没有看到这个所谓的最小值提升问题，而是只要判断page中有空间可以插入新的记录就结束新键值的插入。 其实再回过头来仔细看下btr_root_raise_and_insert函数不难发现(函数不长，注释不少)，可以发现下面的语句： /* The node pointer must be marked as the predefined minimum record, as there is no lower alphabetical limit to records in the leftmost node of a level: */   btr_set_min_rec_mark(node_ptr_rec, page_is_comp(root), mtr); 这里说明了最左节点并不存在，所以必须设置一个特殊标志位，那么无疑这个标志位就是解决这个问题的关键。在前面提到的page_cur_search_with_match函数中，它对记录的比较通过cmp_dtuple_rec_with_match函数完成，在这个函数中可以看到对于该标志位的使用： int ret = 3333; /* return value */ …… if (cur_bytes == 0 && cur_field == 0) { ulint rec_info = rec_get_info_bits(rec,      rec_offs_comp(offsets)); ulint tup_info = dtuple_get_info_bits(dtuple);   if (rec_info & REC_INFO_MIN_REC_FLAG) { ret = !(tup_info & REC_INFO_MIN_REC_FLAG); goto order_resolved; } else if (tup_info & REC_INFO_MIN_REC_FLAG) { ret = -1; goto order_resolved; } } 也就是具有REC_INFO_MIN_REC_FLAG标志的记录小于任何tuple，这样在二分查找的时候就总能找到一个可用的“用户”记录。一个有意思的推论是，无论一个B树中有多少条记录，REC_INFO_MIN_REC_FLAG标志置位的记录数只和B树中间层数决定(当根节点也是叶子节点的时候，根节点同样没有该记录，这一点可以从btr_create函数验证)，只有每层的最左节点的最左记录具有这个标志位，即使每个记录都预留了这个bit的空间。并且这个标志位的置位只有在前面提到的btr_root_raise_and_insert函数中通过btr_set_min_rec_mark完成。 4、btr_root_raise_and_insert生成的新根节点有几条记录 结合这个细节，btr_root_raise_and_insert新提升的根节点是有两条记录，一条是btr_root_raise_and_insert函数中通过page_cur_tuple_insert直接插入的节点，这个节点具有REC_INFO_MIN_REC_FLAG标志位；另一条记录通过btr_root_raise_and_insert===>>>btr_page_split_and_insert===>>>btr_attach_half_pages===>>>btr_insert_on_non_leaf_level完成。 三、页面分裂的位置 在通常的(教科书)B树描述中，当一个节点需要分裂的时候按照记录的数量从中间分裂，但是，这样做可能并不合理。在一些典型的数据库操作中，键值通常是按顺序插入的，例如身份证的编号中由于有时间，所以大部分同一个地区的编号都是递增的；订单的编号通常也可以做到递增。这样在中间分裂之后，左边部分的半满节点将长时间无法获得新数据，而右边的半满节点则很快再次分裂并再次导致一个不再被更新的半满节点，这个过程如果一直持续，那么系统中将遍布这种半满节点，导致页面利用率下降。 1、插入新节点时的统计 为了解决这个问题，在一个页面插入的时候会进行一些统计信息，从而在分裂的时候不是机械的按照记录数量分裂，而是按照逻辑上的键值特性分裂。具体来说，就是在每次插入的时候记录本次插入位置是否紧邻上次插入位置，如果相邻则记录和上次插入记录键值之间的大小关系。这个过程在函数page_cur_insert_rec_low中实现： …… else if ((page_rec_get_next(insert_rec) == last_insert)    && (page_header_get_field(page, PAGE_DIRECTION)        != PAGE_RIGHT)) {   page_header_set_field(page, PAGE_DIRECTION, PAGE_LEFT); page_header_set_field(page, PAGE_N_DIRECTION,       page_header_get_field(       page, PAGE_N_DIRECTION) + 1); } else { page_header_set_field(page, PAGE_DIRECTION, PAGE_NO_DIRECTION); page_header_set_field(page, PAGE_N_DIRECTION, 0); }   page_header_set_ptr(page, PAGE_LAST_INSERT, insert_rec); 2、页面分裂是对上次插入统计信息的使用 btr_page_split_and_insert===>>>btr_page_get_split_rec_to_right         /* We use eager heuristics: if the new insert would be right after the previous insert on the same page, we assume that there is a pattern of sequential inserts here. */   if (UNIV_LIKELY(page_header_get_ptr(page, PAGE_LAST_INSERT) == insert_point)) { …… /* If there are >= 2 user records up from the insert point, split all but 1 off. We want to keep one because then sequential inserts can use the adaptive hash index, as they can do the necessary checks of the right search position just by looking at the records on this page. */   *split_rec = next_next_rec; …… 3、这种"启发式"分裂对于顺序插入的效果 在同样是顺序插入的时候，由于最后一次插入通常是页面的最后，从该位置分裂就可以使当前页面几乎是满的，新分裂页面几乎为空，并且下次顺序插入时会插入空页面，这样页面利用率提高。当然这个是最好情况，在某些情况下也会出现一些意想不到的问题。例如在最后一次插入并不是连续的，或者新插入节点键值太大而导致从上次插入位置分裂不合理(btr_page_split_and_insert函数进行循环判断，启发式分裂失败之后按大小分裂)等。 四、分裂之后锁的迁移 页面分裂之后，一个直接受影响的数据结构就是迁移记录上的锁结构，不过这个锁迁移总体来说比较直观，这个操作随着记录在页面之间迁移而同时进行：btr_page_split_and_insert===>>>lock_move_rec_list_start， while (lock != NULL) {   page_cur_set_before_first(page, &cur1); page_cur_move_to_next(&cur1);   page_cur_position(old_end, &cur2); page_cur_move_to_next(&cur2);   /* Copy lock requests on user records to new page and reset the lock bits on the old */   while (page_cur_get_rec(&cur1) != rec) { ut_ad(comp || !memcmp(page_cur_get_rec(&cur1),       page_cur_get_rec(&cur2),       rec_get_data_size_old(       page_cur_get_rec(       &cur2)))); heap_no = rec_get_heap_no(page_cur_get_rec(&cur1),   comp);   if (lock_rec_get_nth_bit(lock, heap_no)) { type_mode = lock->type_mode;   lock_rec_reset_nth_bit(lock, heap_no);   if (lock_get_wait(lock)) { lock_reset_lock_and_trx_wait(lock); }   lock_rec_add_to_queue(type_mode,       page_cur_get_rec(&cur2),       lock->index, lock->trx); }   page_cur_move_to_next(&cur1); page_cur_move_to_next(&cur2); }   lock = lock_rec_get_next_on_page(lock); } 还有gap锁在infinum和suprenum之间的继承通过lock_update_split_left或lock_update_split_right完成。 五、B树分裂原子性的保证 在页面分裂的时候，修改的是最为关键的B树结构，而且可能进行多层修改，如果在这个过程中发生崩溃会导致整个B树不可能用，所以在整个操作过程中，使用同一个mtr结构，以保证整个B树修改的原子性，下面的调用链传递的都是相同的mtr参数 btr_cur_pessimistic_insert===>>>btr_page_split_and_insert===>>>btr_attach_half_pages===>>>btr_insert_on_non_leaf_level===>>>btr_cur_pessimistic_insert===>>>btr_root_raise_and_insert