B+树在mysql数据库索引中的使用

一：B-树是一种平衡的多路查找树，它在文件系统中很有用。

定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树：

⑴树中每个结点至多有m 棵子树。

⑵若根结点不是叶子结点，则至少有两棵子树。

⑶除根结点之外的所有非叶结点至少有[m/2] 棵子树；

⑷所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，…，Kn，An）

其中：n 为关键码的个数，Ki（i=1,2,…,n）为关键码且Ki<Ki+1，Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki大于Ki-1。

⑸所有的叶子结点都出现在同一层次上，并且不带信息（实际上这些结点不存在，指向这些结点的指针为空）。即所有叶节点具有相同的深度，等于树高度。

如一棵四阶B-树，其深度为4，如下图：

B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

在上图的B-树上查找关键字47的过程如下：

1）首先从更开始，根据根节点指针找到 *a节点，因为 *a 节点中只有一个关键字，且给定值47 > 关键字35，则若存在必在指针A1所指的子树内。

2）顺指针找到 *c节点，该节点有两个关键字（43和 78），而43 < 47 < 78,若存在比在指针A1所指的子树中。

3）同样，顺指针找到 *g节点，在该节点找到关键字47,查找成功。

二：B+树是应文件系统所需而产生的一种B-树的变形树。

一棵m阶的B+树和m阶的B-树的差异在于：

⑴ 有n 棵子树的结点中含有n 个关键码；

⑵所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且 叶子结点本身依关键码的大小自小而大组成顺序链表。

⑶在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。 只是在查找时，若非叶结点上的关键码等于给定值，也并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根节点到叶子结点的路径。

如图一棵3阶的B+树： 通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找。

三：下面来介绍B+树在数据库索引中的典型应用。

数据库索引常用B+树来实现。 数据库索引分为聚集索引（也叫聚簇索引）和非聚集索引（非聚簇索引）两种类型。

InnoDB引擎使用的是聚集索引。所谓 聚集索引：就是B+树的叶子节点的data域中存放的是完整的数据记录。

对于聚集索引，按照B+树中关键字的不同分为主键索引和辅助索引。使用主键属性作为B+树的关键字就是主键索引，使用非主键属性作为B+树的关键字就是辅助索引。如下图：

上图是InnoDB主键索引

上图是InnoDB辅助索引

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。从上面的数据结构也可以理解，用来做索引的属性列的字段越短性能越好。

MyISAM引擎使用的是非聚集索引。所谓 非聚集索引：就是B+树的叶子节点的data域中存放的是数据记录的地址。按照B+树中关键字的不同也可以分为主键索引和辅助索引。如图所示：

上图是MyISAM主键索引

上图是MyISAM辅助索引

InnoDB索引和MyISAM索引的区别：

1) InnoDB是聚集索引，B+树的叶子节点的data域中保存的是完整的数据记录。MyISAM是非聚集索引，B+树的叶子节点的data域中保存的是数据记录的地址。

2) InnoDB的辅助索引中，B+树的叶子节点的data域中保存的是对应的主键，因此在InnoDB中使用辅助索引需要两边检索。而对于MyISAM索引，无论是主键索引还是辅助索引对需要一次检索即可。

3）     对于聚集索引，因为它的主键索引的data域中存储的是完整的行信息，因此不会再单独存储行信息，这也是它的辅助索引的data域中存储的是主键值的原因。对于非聚集索引，它的主键索引和辅助索引的data域中存储的都是行信息的地址，因此需要单独的空间来存储行信息。如下图：

B-Tree索引适用于全键值，键值或前缀查找。其中键前缀查找只适用于根据最前缀的查找。前面所述的索引对如下类型的查询有效：

1. 全值匹配：全值匹配指的是和索引中的所有列进行匹配。

2. 匹配最左前缀：即仅仅匹配索引的最左侧列。

3. 匹配最左前缀的一部分：即仅仅匹配索引的最左侧列的一部分。

4. 匹配范围值：指定索引的最左侧列的范围。

5. 精确匹配前几列并范围匹配后一列

将上面的叙述总结起来，可以归纳出B-Tree索引的限制：

1. 如果不是按照索引的最左列开始查找，则无法使用索引。

2. 查询时不能跳过索引中的列。

3. 如果查询中有某个列的范围查询，则其右边所有的列都无法使用索引优化查找。

读者应该明白，索引列的顺序是很重要的，在性能优化的时候，可以建立相同的列但顺序不同的索引来满足不同的需求。

• 

• 大小: 24.4 KB

• 

• 大小: 20.5 KB

• 

• 大小: 19.5 KB

• 

• 大小: 42.6 KB

• 

• 大小: 43 KB

• 

• 大小: 24.8 KB

• 

• 大小: 96.9 KB

• 查看图片附件