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

3)移动相应元素后,如果结点中元素个数小于ceil(m/2)-1,则需要看其相邻兄弟结点是否足够(结点中元素个数大于ceil(m/2)-1),如果足够,则向父节点借一个元素；如果其相邻兄弟都不够,即借完之后其结点元素个数小于ceil(m/2)-1,那该结点与其相邻的某一兄弟结点合并成一个结点,以此来满足条件.

总之,对于索引文件,无论是插入还是删除B-Tree结点,不断地分裂和合并结点来维持B-Tree结构是非常昂贵的操作.

4、B+Tree介绍

MySQL索引采用B+Tree,它是应文件系统所需而产生的一种B-Tree的变形树,他们的差异在于：

1) 非叶子结点的子树指针与关键字个数相同；

2) B+树父结点中的记录,存储的是下层子树中的最小值；

3) 所有叶子结点通过一个链指针相连；

4) 所有关键字都在叶子结点出现.

如下面是一棵典型的B+Tree(假设每个结点最多有4个关键字)

其它特性与操作与B-Tree基本相同.到此,B-Tree和B+Tree基础知识已经了解了,下面的内容都是基于以上的概念.

二、MySQL索引实现

MySQL索引实现是在存储引擎端,不同存储引擎对索引实现方式是不同的,比如InnoDB和MyISAM,下面我们重点介绍InnoDB引擎索引的实现方式.

1、InnoDB索引实现方式

对于InnoDB表,数据文件ibd本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录.

举例说明,下面是students表,id是主键,name上有辅助索引,有6行数据记录.

假如在一棵5阶B+Tree(关键字范围[2,4]),它的主键索引组织结构如下：

上图是InnoDB主键索引的B+Tree,叶节点包含了完整的数据记录,像这种索引叫做聚集索引.因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL会优先自动选择一个可以唯一标识数据记录的列作为主键,比如唯一索引列,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,长度为6个字节,类型为longint.

辅助索引结构：

对于secondary index,非叶子结点保存的是索引值,比如上面的name字段.

叶子结点保存的不再是数据记录了,而是主键值.

从上面的B+Tree可以总结到：

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

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

（编辑：ASP站长网）