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

《MySQL索引设计背后的数据结构及算法详解》要点：
本文介绍了MySQL索引设计背后的数据结构及算法详解，希望对您有用。如果有疑问，可以联系我们。

在我们公司的DB规范中,明确规定：

1、建表语句必须明确指定主键

2、无特殊情况,主键必须单调递增

对于这项规定,很多研发小伙伴不理解.本文就来深入分析MySQL索引设计背后的数据结构和算法,从而帮你释疑以下几个问题：

1、为什么InnoDB表需要主键?

2、为什么建议InnoDB表主键是单调递增?

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

一、B-Tree基础知识

B-Tree(多路搜索树)是一种常见的数据结构.使用B-Tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度.B通常认为是Balance的简称.这个数据结构一般用于数据库的索引,综合效率较高.目前很多数据库产品的索引都是基于B+Tree结构.MySQL也采用B+Tree,是B-Tree的一个变种,其实特性相差不大,理解了B-Tree也就懂了B+Tree.

1、一颗M阶B-Tree具有的特性【熟记于心】

1) 根结点的孩子数>=2(前提是树高度大于1)

2) 除根结点与叶子结点,其它结点的孩子数为[ceil(m/2),m]个.ceil函数表示上取整数.

3) 所有叶子结点都出现在同一层,叶子结点不存储数据.

4) 各个结点包含n个关键字信息：(P0,K1,P1,K2,P2……Kn,Pn)

• Ki(i=1,2……n)为关键字,且K(i-1)<Ki,即从小到大排序
• 关键字的个数n必须满足：[ceil(m/2)-1,m-1]
• 4.3) Pi指向子树,且指针P(i-1)所指向的子树结点中所有关键字均小于Ki.即：父结点中任何关键字的左孩子都小于它,右孩子大于它.

2、B-Tree插入操作

1)插入新元素,如果叶子结点空间足够,则插入其中,遵循从小到大排序；

2)如果该结点空间满了,进行分裂.将该结点中一半关键字分裂到新结点中,中间关键字上移到父结点中.

【举例】如果单从上面特性及插入规则看得不明白,请结合以下分步骤图例：

将下面数字插入到一棵5阶B-Tree中：[3,14,7,1,8,5,11,17,13,6,23,12,20,26,4,16,18,24,25,19]

首先根据B-Tree特性知道,每个结点的关键字数量范围是: ? 2<=n<=4

【第一步】：插入3,1

到这里,第一个结点中关键字数量刚好满了.

【第二步】：插入8

由于8是大于7的,故应该插入右子树,一个结点中最多存储4个关键字,按照插入规则,将中间关键字7上移形成父结点,其他按照50%分裂成两个结点,如上图.

【第三步】：插入5,17

由于5小于7,插入左子树,17大于7,插入右子树.叶子结点没有满4个关键字,故可以直接插入5,17.

【第四步】：插入13

13大于7,应该插入右子树结点中,由于该结点中满4个关键字了,需要进行分裂.13刚好是中间关键字,上移到父结点中；其他按照50%分裂成两个结点.

【第五步】：插入6,20

以上几个数字按照规则直接插入即可,无需分裂操作.

【第六步】：插入26

由于26大于13,应该插入13的右子树结点中,但是该结点已经满了,需要分裂,将中间20上移到父结点中,其他按照50%分裂成两个结点.

【第七步】：插入4

由于4小于7,应该插入7的左结点中,但该结点满了,需要进行分裂,将中间关键字4上移到父结点中,其他按照50%分裂成两个结点.

【第八步】：插入16,25

以上4个数字按大小直接插入到相应位置即可,无需分裂操作.

【第九步】：插入19

插入19,需要放到18的后面,但是由于该结点已满,需要分裂操作,将中间关键字17上移到父结点中,其它按照50%分裂成14,16以及18,19两个结点；别以为到这就结束了,再看17被上移到父结点中,由于父结点已经满了,所以这时对父结点进行分裂,将中间关键字13上移形成新的父结点,其他按照50%分裂成4,7和17,20两个结点,到此,数据插入全部完成,形成了一棵B-Tree.

?3、删除操作

删除操作稍稍复杂一些,这里就不举例展开了.大概思路如下：

1)查找B-Tree中需删除的元素,如果该元素在B-Tree中存在,则将该元素在其结点中进行删除.

2)删除该元素后,判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素到父节点中,然后进入第三步；如果没有,直接删除后,进入第三步.

（编辑：ASP站长网）