mysql索引采用什么数据结构

文就是对这两种数据结构做简单的介绍。

1. B-Tree

B-Tree不是“B减树”，而是“B树”。

这里参考了严蔚敏《数据结构》对B-Tree的定义：

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

1.树中每个结点至多有m棵子树；

2.若根结点不是叶子结点，则至少有两棵子树；

3.除根节点之外的所有非终端结点至少有[m/2]棵子树；

4.所有非终端结点中包含下列信息数据:

(n,A0,K1,A1,K2,A2……Kn,An)

其中，n为关键字的数目，K(i)为关键字，且K(i) <K(i+1), Ai为指向子树根结点的指针，且指针A(i-1)所指子树中所有结点的关键字均小于Ki，Ai所指子树中所有结点的关键字均大于Ki；

5.所有叶子结点都出现在同一层次上；

下面通过一个例子解释一下B-Tree的查找过程。

这是一棵4阶的B-Tree，深度为4。

假如在该图中查找关键字47，首先从根结点开始，根据根结点指针t找到*a结点，因为47大于 *a 结点的关键字35，所以会去A1指针指向的 *c结点继续寻找，因为 *c的关键字 43 <要查找的47 <*c结点的关键字78，所以去 *c结点A1指针指向的 *g结点去寻找，结果在 *g结点中找到了关键字47，查找成功。

2. B+Tree

不同的存储引擎可能使用不同的数据结构存储，InnoDB使用的是B+Tree；那什么是B+Tree呢？

B+Tree是应文件系统所需而出的一种B-Tree的变型树，一棵m阶的B+树和m阶的B-树的差异在于:

1.有n棵子树的结点中含有n个关键字；

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字的记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大（或最小）关键字；

还是通过一个例子来说明。

这个例子中，所有非终端结点仅含有子树中最大的关键字。

因为叶子节点本身依据关键字的大小自小而大顺序链接，所以可以从最小关键字起顺序查找。也可以从根结点开始，进行随机查找。

在B+树中随机差找和在B-树中类似，以上图为例。假设要查找关键字51，现在根节点中比较，发现51<59，因为这里使用的是非终端结点的关键字是子树中最大的关键字，所以进入最大值为59的子结点(15\44\59)中查找，同理，因为44<51<59，所以进入P3指向的结点(51\59)中查找，然后命中关键字51，因为此结点(51\59)是叶子结点，所以查找终止，该结点包含指向数据的指针。

3.索引如何在B+Tree中组织数据存储

假设有如下表:

对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图展示索引是如何组织数据存储的:

索引对多个值进行排序的依据是定义索引时列的顺序。

(Allen Cuba 1960-01-01)结点左侧的指针指向[?,Allen Cuba 1960-01-01)的叶子页，(Allen Cuba 1960-01-01)和(Astaire,Angelina,1980-03-04)之间的指针指向[Allen Cuba 1960-01-01,Astaire Angelina 1980-03-04)的叶子页，以此类推。总之，每个指针指向的结点中的最小值就是该指针左侧的的值。

这种存储结构也说明了在定义多个列组成的多列索引中，为什么需要把重复率最低的列放到最左侧，因为这会减少比较的次数，查找起来更加高效。

4.索引为什么选用B树这种数据结构？

因为使用B树查找时，所用的磁盘IO *** 作次数比平衡二叉树更少，效率也更高。

为什么使用B树查找所用的磁盘IO *** 作次数比平衡二叉树更少？

大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种 *** 作能使B树保持较低的高度，从而达到有效减少磁盘IO *** 作次数。

普通索引：一个索引只包含一个列，一个表可以有多个单列索引

唯一索引：索引列的值必须唯一，但允许有空值

复合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并

聚簇索引：也可以称为主键索引，是一种数据存储方式，B+树结构，一张表只能有一个聚簇索引

非聚簇索引：顾名思义，不是聚簇索引。

MySQL 前缀索引能有效减小索引文件的大小，提高索引的速度。但是前缀索引也有它的坏处：MySQL 不能在 ORDER BY 或 GROUP BY 中使用前缀索引，也不能把它们用作覆盖索引(Covering Index)。

集一个索引包含多个列（最左前缀匹配原则）

索引列的值必须唯一，但允许有空值

全文索引为FUllText，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值，全文索引可以在CHAR,VARCHAR,TEXT类型列上创建

设定主键后数据会自动建立索引，InnoDB为聚簇索引

即一个索引只包含单个列，一个表可以有多个单列索引

覆盖索引是指一个查询语句的执行只用从所有就能够得到，不必从数据表中读取，覆盖索引不是索引树，是一个结果，当一条查询语句符合覆盖索引条件时候，MySQL只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后的回表 *** 作，减少了I/O效率

查看索引

列名解析：

删除索引

查看：

删除前:

删除后：

普通的索引，没有什么介绍

查看:（注意和前缀索引Sub_part的区别）

当索引的列是unique的时候，会生成唯一索引，唯一索引关于null有下列两种情况

SQLSERVER 下的唯一索引的列，允许null值，但最多允许有一个空值

MYSQL下的唯一索引的列，允许null值，并且允许多个空值

查看:

会建立两个索引，一个非聚簇索引，一个是唯一索引

结果:

可以插入两个空值（明人不说暗话，我喜欢MySQL）

一方面，它不会索引所有字段所有字符，会减小索引树的大小.

另外一方面，索引只是为了区别出值，对于某些列，可能前几位区别很大，我们就可以使用前缀索引。

一般情况下某个前缀的选择性也是足够高的，足以满足查询性能。对于BLOB，TEXT，或者很长的VARCHAR类型的列，必须使用前缀索引，因为MySQL不允许索引这些列的完整长度。

查看：

查看：

复合索引的最左前缀匹配原则 ：

对于复合索引，查询在一定条件才会使用该索引

减少开销。 建一个联合索引(col1,col2,col3)，实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引。每多一个索引，都会增加写 *** 作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销！

覆盖索引。 对联合索引(col1,col2,col3)，如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2。那么MySQL可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机io *** 作。减少io *** 作，特别的随机io其实是dba主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。

效率高。 索引列越多，通过索引筛选出的数据越少。有1000W条数据的表，有如下sql:select from table where col1=1 and col2=2 and col3=3,假设假设每个条件可以筛选出10%的数据，如果只有单值索引，那么通过该索引能筛选出1000W10%=100w条数据，然后再回表从100w条数据中找到符合col2=2 and col3= 3的数据，然后再排序，再分页；如果是联合索引，通过索引筛选出1000w10% 10% *10%=1w。

在模糊搜索中很有效，搜索全文中的某一个字段，可以参考这篇博文

: https://zhuanlan.zhihu.com/p/88275060

我们先进行下面一个实验看看InnoDB下的主键索引的一个现象。

查看:

我们插入进去的时候，数据的id都是乱序的，为什么这里最后select查询出来的结果都是进行了排序？

这是因为InnoDB索引底层实现的是B+tree，B+tree具有下列的特点：

所以上面的排序是为了使用B+tree的结构 ，B+tree为了范围搜索，将主键按照从小到大排序后，拆分成节点。后续还有新的节点进入的时候，和B-tree相同的 *** 作，会进行分裂。

一般来说，聚簇索引的B+tree都是三层

InnoDB中主键索引一定是聚簇索引，聚簇索引一定是主键索引。

为什么这里辅助索引叶子结点不直接存储数据呢？

MYISAM只有非聚簇索引，索引最终指向的都是物理地址。

Q:既然有回表的存在，那么聚簇索引的优势在哪里？

Q:主键索引作为聚簇索引需要注意什么

在查询语句中使用LIke关键字进行查询时，如果匹配字符串的第一个字符为"%"，索引不会使用。如果“%”不是在第一位，索引就会使用

多列索引是在表的多个字段上创建的索引，满足最左前缀匹配原则，索引才会被使用

查询语句只有Or关键字时候，如果OR前后的两个条件都是索引，这这次查询将会使用索引，否则Or前后有一个条件的列不是索引，那么查询中将不使用索引

---