mysql-innodb之B+树

B+树查找原理

• 查找索引页，索引页不在缓存中，则去磁盘中找到对应的索引页并放到lru队列头部
• 从索引页中找到对应的数据页，数据页若不在内存，也需要去磁盘加载到内存
• 找到对应的数据页再查询具体的数据

B+树相关算法和数据结构

二分查找法

将记录按有序化排列后，将查找的数据和有序队列中的中点位置的数据进行比较后排除一半数据再以此类推，查询次数一般为log2n, 比如n为10，则查询次数为3~4之间

B+树

b+树最多有m个子节点，m也被叫做b+树的最小度数， 则单个节点中的键数量范围为⌈m/2⌉-1, m-1

B+树插入分裂：

插入节点后若节点内键数 > 最大键数， 则对左节点进行分裂，将中间键值放入索引页，小于中间键值的为左子树，大于等于的为右子树。若分裂后导致上层索引页的键数 > 最大键数，则继续分裂索引页，索引页分裂小于中间键值的为左子树，大于的为右子树

• b+树如下，m=5 ，键数量范围为 （2，4） 插入数据28， 由于28插入后，叶子节点键值为3，符合键数量范围，故无需进行页分裂

• 再继续插入70，插入后第三个叶节点的键为50，55，60，65，70， 超过最大键数，故需要进行页面分裂，取中间键值60放到索引页，60左侧键值为60的左子树，60右侧包含60为60的右子树。60插入后索引页后，索引页为25，50，60，75，不超过最大键数，故插入结束

• 最后插入95
  1. 插入后叶节点键值为75，80，85，90，95，键数 > 最大键数，故需要进行页分裂，取中间键值85到上层索引层，小于85的75，80为85的左子树， 大于等于85的键值为右子树
  2. 85插入到索引页后，索引页的键为25，50，60，75，85，键数 > 最大键数继续索引页分裂，取中间键60放到更上层索引页，25，50为60的左子树，60以上键为60的右子树

B+树删除合并

• 键数量不足：键数量 < ⌊(m-1)/2⌋， 假设m=5，则键数量 < 2。 m=4，则键数量 < 1
• 借键：是指键被删除后，键数量不足，且兄弟节点的键值由冗余（键数量 > ⌊(m-1)/2⌋）,则可以取左兄弟节点的最大值或者右兄弟节点的最小值，并更新用借的键更新上层索引节点
• 合并：是指兄弟节点键数 >= ⌊(m-1)/2⌋，则可以进行左兄弟或者右兄弟节点进行合并
• 删除过程：
  1. 若删除键后叶子节点键数 >= ⌊(m-1)/2⌋, 直接将键删除，若刚好键也是索引节点中的键，则使用被删键的下一个键值替换索引节点中的键值
  2. 若删除键后叶子节点键数 < ⌊(m-1)/2⌋，则考虑借键或者合并，看看满足那种情况
     1. 若借用左侧节点的最后一个键值，更新叶节点键值后并更新上层索引页的键值为借用的键值；若借用右侧节点的最后一个键值，更新叶节点键值后并更新上层索引页的键值为借用的键值
     2. 若满足合并条件，合并节点后，删除索引节点被合并的两个节点中间的键值，
• 以插入的最终b+树为初始树
• 删除70，70删除后，叶子节点不需要借键或者合并，直接更新叶子节点，且70非索引节点键值，也不需要处理索引节点

• 删除25，删除25后，叶子节点还剩2个键，不需要借键或者合并，叶子节点直接更新，但25也是索引节点，为了保持稳定，则需要用28替换25索引节点上的键
  

注意

• b+树的叶子节点不一定就单独占一页，具体取决于记录的大小和数量
• 插入最后的键60的节点的键数少于最少的2个要求是因为innodb对下限不做强制限制，大于0即可
• 在删除键值过程中，若叶子节点的数量=1，则根节点为叶子节点
• 在删除键值过程中，若索引节点只有一个，则可以直接删除更上层的索引节点
• 上述插入时页分裂(从中间分裂)比较适合非聚簇索引的页分裂，但针对有序的聚簇索引来说，若从中间分裂后前一页的分裂后的剩余空间就使用不到了,page_header里的几个参数可以调整分裂方向、分裂点
  • PAGE_LAST_INSERT:当向数据页插入新记录时，InnoDB 会优先尝试将数据插入到 PAGE_LAST_INSERT 标记的位置之后。这减少了查找插入点的开销，尤其是在有序插入（如自增主键或时间序列数据）时效率显著
  • PAGE_DIRECTION:指示数据插入的“热点”区域（页面左侧或右侧），减少查找插入点的开销，尤其在顺序插入（如自增主键、时间序列数据）时效果显著

参考书籍：mysql技术内幕(innodb存储引擎)