本文共 7484 字，大约阅读时间需要 24 分钟。

        索引—数据库绕不开的话题：对于良好性能的提升起着关键的作用。尤其是当表中的数据量越来越大时，索引显得愈发重要。不过索引却经常被忽略，有时甚至会被误解，在实际开发过程中常常遇到糟糕索引遇到的问题。索引优化应该是对查询性能优化最有效的手段了。这是索引的基本功能，除此之外，索引还有其他方面有用的属性。本文将从索引基础和索引优化来讲解MySQL的索引，并指出常见的误区。

• 引言

索引-它的出现是由于我们实际的服务器环境造成的，是必然的结果。选用B-tree树作为很多索引实现的数据结构，也是为了弥补硬件设备（通常是硬盘）性能不足的问题。实际也是如此：如果在内存中进行有序数据的存储和查找，我们更倾向于使用红黑树实现，例如JDK里面HashMap的实现。

索引不仅仅都是使用B-tree实现，还有hash等各种结构。索引不仅仅被用来提高查询速度，还可以加快排序。甚至在可以减少锁的竞争：InnoDB只有在访问行的时候才会对其加锁，而索引你能够减少InnoDB访问的行数，从而减少锁的数量。

第二节 B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引，这一节先单纯从数据结构角度描述它们。

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

1.　定义任意非叶子结点最多只有M个儿子；且M>2；

2.　根结点的儿子数为[2, M]；

3.　除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.　每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.　非叶子结点的关键字个数=指向儿子的指针个数-1；

6.　非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.　非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8.　所有叶子结点位于同一层；

图1  B-Tree示意图

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。与B-Tree相比，B+Tree有以下不同点：

1.每个节点的指针上限为2d而不是2d+1。

2.内节点不存储data，只存储key；叶子节点不存储指针。

图2  B+Tree示意图

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。一般来说，B+Tree比B-Tree更适合实现外存储索引结构，内节点不存data可以存更多的key，降低了b树的高度，减少了磁盘IO次数，加快了查询速度。

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

图4 带有顺序访问指针的B+Tree

如图4所示，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

为什么使用B-Tree（B+Tree）？

上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

第三节 局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

1. 当一个数据被用到时，其附近的数据也通常会马上被使用。
2. 程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

第四节 B-/+Tree索引的性能分析

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：

dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

这一节从理论角度讨论了与索引相关的数据结构与算法问题，下一节将讨论B+Tree是如何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

 

第五节 索引分类

从数据结构角度：

1. B+树索引(O(log(n)))：

B+树索引意味着数据是顺序存储的，并且每个叶子节点到根的距离相等（查询时间相同）。非叶子节点可存储多个数据（硬盘每次读取一块，数据量小了会资源浪费并产生IO问题）

1. hash索引：

其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。但是hash索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。

只有Memory存储引擎显示支持hash索引。InnoDB引擎有一个特殊的功能叫“自适应哈希索引”当InnoDB注意到某些索引被频繁使用时，会在B+树索引上创建hash索引。这是一个完全自动的、内部的行为，用户无法控制干预。

1. 全文索引（FULLTEXT）

现在MyISAM和InnoDB引擎都支持了，这是一种特殊类型索引，类似搜索引擎做的事情。

1. 空间数据索引（R-Tree）

用于对GIS数据类型创建SPATIAL索引。

从物理存储角度：

因为是存储引擎负责实现，因此不是所有的存储引擎都支持聚簇索引，本节以InnoDB为例。

1. 聚簇索引（clustered index）

聚簇的含义是将数据行和相邻键值存储在一起。聚簇索引将表的数据行存放在索引的叶子页中，无法将数据行同时放在两个地方，所以聚簇索引一张表最多一个。

InnoDB通过主键聚集数据，如果没有定义主键，会选择一个非空唯一索引代替。如果没有这样的索引InnoDB将会隐式定义一个主键定义聚簇索引。InnoDB的数据分布，因为InnoDB支持聚簇索引，索引使用非常不同的方式存储这样的数据，如下图：

图5  聚簇索引

仔细查看，会注意到该图显示了整个表，而不是只有索引。因为在InnoDB中，聚簇索引“就是”表，所以不像MyISAM那样需要独立的行存储。聚簇索引的每个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。如果主键是一个列前缀索引，InnoDB也会包含完整的主键列和剩下的其他列。

还有一点和MyISAM的不同是，InnoDB的二级索引和聚簇索引很不相同。InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。这样的策略减少了当出现航移动或者数据页分裂时二级索引的维护工作。使用主键值当作指针会让二级索引占用更多的空间，换来的好处是，InnoDB在移动行时无需更新二级索引中的这个“指针”。下图就是InnoDB的二级索引：

图6  InnoDB的二级索引

优点：

1. 把相关数据放在一起，可能会减少磁盘IO次数，有利于提高IO密集型应用的性能：实现电子邮箱时，以用户ID作为主键聚集数据，只需读取几次IO就能查询某个用户所有邮件。如果没有使用聚簇索引，每封邮件都需要一次磁盘IO。
2. 数据访问更快。数据行和索引放在一起，不需要进行二次查询。

缺点：

1. 插入速度依赖于插入顺序。按照索引顺序插入最快，随机插入最慢。如果不是按照索引顺序插入，最后最好使用 OPTIMIZE TABLE 命令重新优化。
2. 插入新行时，或者主键被更新需要移动行的时候，可能会导致页分裂问题（要插入的页空间不够，将该页分裂为两页）导致占用过多的磁盘空间。
3. 二级索引访问需要两次查找，并且二级索引可能比想象的要大（叶子节点是行的主键值）。

1. 非聚簇索引（non-clustered index）

MyISAM引擎不支持聚簇索引。它的数据分布非常简单：按照数据插入的顺序存储在磁盘上如图：

图7  MyISAM的索引

这种分布式很容易创建索引，如图：

图8  MyISAM的索引

3.MyISAM和InnoDB的对比

图9  MyISAM和InnoDB索引对比

从逻辑角度：

Mysql常见索引有：主键索引、唯一索引、普通索引、全文索引、组合索引。Mysql各种索引区别：

普通索引：最基本的索引，没有任何限制

唯一索引：与"普通索引"类似，不同的就是：索引列的值必须唯一，但允许有空值。

主键索引：它 是一种特殊的唯一索引，不允许有空值。 

全文索引：仅可用于 MyISAM 表，针对较大的数据，生成全文索引很耗时好空间。

组合索引：为了更多的提高mysql效率可建立组合索引，遵循”最左前缀“原则。

#PRIMARY KEY（主键索引） 

ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )

#UNIQUE(唯一索引)  

ALTER TABLE `table_name` ADD UNIQUE (`column`)

#INDEX(普通索引)  

ALTER TABLE `table_name` ADD INDEX index_name ( `column` )

#FULLTEXT(全文索引)   

ALTER TABLE `table_name` ADD FULLTEXT ( `column` )

#组合索引  

ALTER TABLE `table_name` ADD INDEX index_name ( `column1`, `column2`, `column3` )

第六节 最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。

这里先说一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组<a1, a2, …, an>，其中各个元素均为数据表的一列，实际上要严格定义索引需要用到关系代数，但是这里我不想讨论太多关系代数的话题，因为那样会显得很枯燥，所以这里就不再做严格定义。另外，单列索引可以看成联合索引元素数为1的特例。

以People表为例，下面先查看其上都有哪些索引：

每列含义如下：

1.Table

表的名称。

2.Non_unique

如果索引不能包括重复词，则为0。如果可以，则为1。

3.Key_name

索引的名称。

4.Seq_in_index

索引中的列序列号，从1开始。

5.Column_name

列名称。

6.Collation

列以什么方式存储在索引中。在MySQL中，有值‘A’（升序）或NULL（无分类）。

7.Cardinality

索引中唯一值的数目的估计值。通过运行ANALYZE TABLE或myisamchk -a可以更新。基数根据被存储为整数的统计数据来计数，所以即使对于小型表，该值也没有必要是精确的。基数越大，当进行联合时，MySQL使用该索引的机会就越大。

8.Sub_part

如果列只是被部分地编入索引，则为被编入索引的字符的数目。如果整列被编入索引，则为NULL。

9.Packed

指示关键字如何被压缩。如果没有被压缩，则为NULL。

10.Null

如果列含有NULL，则含有YES。如果没有，则该列含有NO。

11.Index_type

用过的索引方法（BTREE, FULLTEXT, HASH, RTREE）。

12.Comment

多种评注。

从结果中可以到titles表的主索引为<id>，还有一个辅助索引<id,name>。为了避免多个索引使事情变复杂（MySQL的SQL优化器在多索引时行为比较复杂），这里我们将辅助索引drop掉：

alter table people drop  PRIMARY KEY;

alter table people add  PRIMARY KEY(id,name,age);

这样就可以专心分析索引PRIMARY的行为了。

情况一：全列匹配。

很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。这里有一点需要注意，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，例如我们将where中的条件顺序颠倒：效果是一样的。

情况二：最左前缀匹配。

当查询条件精确匹配索引的左边连续一个或几个列时，如<id>或<id,name>，可以被用到，但是只能用到一部分，即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引，但是key_len为4，说明只用到了索引的第一列前缀。

情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。

此时索引使用情况和情况二相同，因为name未提供，所以查询只用到了索引的第一列，而后面的age虽然也在索引中，但是由于name不存在而无法和左前缀连接，因此需要对结果进行扫描过滤age（这里由于id唯一，所以不存在扫描）。如果想让age也使用索引而不是where过滤，可以增加一个辅助索引<id,age>，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为“隔离列”的优化方法，将id与age之间的“坑”填上。

首先我们看下name一共有几种不同的值：

只有4种。在这种成为“坑”的列值比较少的情况下，可以考虑用“IN”来填补这个“坑”从而形成最左前缀：

这次key_len为775，说明索引被用全了，但是从type和rows看出IN实际上执行了一个range查询，这里检查了3个key。

情况四：查询条件没有指定索引第一列。

由于不是最左前缀，索引这样的查询显然用不到索引。

情况五：匹配某列的前缀字符串。

此时可以用到索引，但是如果通配符不是只出现在末尾，则无法使用索引。

情况六：范围查询。

范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方，那就是仅用explain可能无法区分范围索引和多值匹配，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询：

看起来是用了两个范围查询，但作用于emp_no上的“BETWEEN”实际上相当于“IN”，也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配，否则会对MySQL的行为产生困惑。

情况七：查询条件中含有函数或表达式。

虽然这个查询和情况五中功能相同，但是由于使用了函数left，则无法为title列应用索引，而情况五中用LIKE则可以。

转载地址：https://blog.csdn.net/h2453532874/article/details/97573410 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！