MySQL索引设计背后的数据结构及算法详解

问题1：为什么InnoDB表需要主键?

• InnoDB表数据文件都是基于主键索引组织的,没有主键,MySQL会想办法给我搞定,所以主键必须要有；
• 基于主键查询效率高；
• 其它类型索引都要引用主键索引；

问题3：为什么不建议InnoDB表主键设置过长?

• 因为辅助索引都保存引用主键索引,过长的主键索引使辅助索引变得过大；

三、InnoDB对B+Tree的改进

在上面的例子中：将下面数字插入到一棵5阶B-Tree中：[3,19]

插入这些无序数据一共经历了6次分裂,对于磁盘索引文件而言,每次分裂都是很昂贵的操作；如果将以上数据排好序,再次插入是不是效果会好,我试验了下,虽然每次都是插入到最右结点,涉及迁移数据量会少,但是分裂的次数依然挺多,需要7次分裂.

每次分裂都是按照50%进行,这样存在明显的缺点就是导致索引页面的空间利用率在50%左右；而且对于递增插入效率也不好,平均每两次插入,最右结点就得进行一次分裂.那InnoDB是如何进行改进的呢?

InnoDB其实只是针对递增/递减情况进行了改进优化,不再采用50%的分裂策略,而是使用下面的分裂策略：

1、插入新元素,判断叶子结点空间是否足够,直接插入；

2、如果叶子结点空间满了,判断父结点空间是否足够,将该新元素插入到父结点中；如果父结点空间满了,则进行分裂.

比如下面一棵5阶B+Tree：

现在连续插入10,15,采用优化后分裂策略的分步图例如下：

【第一步】：插入10

由于最右结点还有空间,直接插入即可.

【第二步】：插入11

插入11时,由于最右结点空间已满,如果使用50%分裂策略,则需要分裂操作了,但是使用优化后的分裂策略,当该结点空间已满,还要判断该结点的父结点是否满了,如果父结点还有空间,那么插入到父结点中,所以11插入到父结点中了,同时形成一个子结点.

【第三步】：插入14,17

优化后的分裂策略仅仅针对递增/递减情况,显著的减少了分裂次数并且大大提高了索引页面空间的利用率.

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!