MySQL B+树插入与页分裂

页分裂

叶子节点分裂

一个叶子page的大小16KB，当插入的数据超过16KB时，就会发生页分裂。

如果要插入数据的叶子节点已满，就会发生页分裂。 此时，MySQL 会创建一个新的叶子节点，将原节点中的数据按照一定的规则（通常是平均分配）分成两部分，一部分留在原节点，另一部分移动到新节点。 同时，更新原节点和新节点的指针，使它们相互链接，并且更新父节点中指向这两个节点的指针和索引值，以反映新的节点结构和数据分布。 如果父节点因此也变得满了，那么这种分裂操作可能会递归地向上传播，直到根页。 但由于根页是树的起始点，为了保持树的稳定性和高效性，根页的分裂相对特殊，它会创建一个新的根页， 原根页的数据和指针会被重新分配到两个新的子节点中，新的根页则指向这两个子节点，从而使树的高度增加一层。

非叶子节点分裂

当非叶子节点已满且需要插入新的索引值和指针时，也会发生分裂。 与叶子节点分裂类似，会创建一个新的非叶子节点，将原节点中的索引值和指针进行分配，一部分留在原节点，一部分放入新节点。 同时，更新相关节点的指针和索引值，以确保树的结构正确和查询能够正确进行。不过，非叶子节点的分裂不会直接影响数据的存储位置，主要是为了维护索引结构的平衡和高效性。

插入数据原理

定位插入位置

当插入一条新数据时，首先会从根页开始，根据索引值通过比较操作沿着树的分支向下查找，直到找到合适的叶子节点。 这个查找过程类似于二分查找，通过不断地比较索引值与节点中的值来决定下一步的查找方向。

插入数据到叶子节点

找到叶子节点后，会检查该叶子节点是否还有足够的空间来插入新数据。 如果叶子节点未满，即节点中存储的数据量未达到节点的容量上限， 那么直接将新数据插入到该叶子节点中合适的位置。 通常，叶子节点中的数据是按照索引值的顺序排列的， 所以新数据会被插入到能保持顺序的位置上。