索引基本概念

索引是什么

官方定义:
MySQL官方对索引的定义为：索引（index）是帮助MySQL高效获取数据的数据结构（有序）。索引是在数据库表的字段上添加的，是为了提高查询效率存在的一种机制。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。如下面的示意图所示 :

更通俗的说，索引就是一个排好序的数据结构。

左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找快速获取到相应数据。

一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中[MyIsam]，也可能和数据一起存储在数据文件中[Innodb]）。
我们通常所说的索引，包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等，没有特别说明，默认都是使用B+树结构组织（多路搜索树，并不一定是二叉的）的索引。

索引优势和劣势

优势:

加快查找和排序的速率，降低数据库的IO成本以及CPU的消耗
通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。
如果按照索引列的顺序进行排序，对应order by和group by语句来说，效率就会提高很多。
innodb使用的B-Tree索引，在叶子节点存放了实际的索引列值如果是聚簇索引，则存储了整行的值，这样某些查询只需要使用索引就可以完成查询
劣势:
索引实际上也是一张表，保存了主键和索引字段，并指向实体类的记录，本身需要占用空间
虽然增加了查询效率，但对于增删改，每次改动表，还需要更新一下索引
新增：自然需要在索引树中新增节点
删除：索引树中指向的记录可能会失效，意味着这棵索引树很多节点，都是失效的
改动：索引树中节点的指向可能需要改变

索引类型

主键索引

索引列中的值必须是唯一的，不允许有空值。

普通索引

MySQL中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值。

唯一索引

索引列中的值必须是唯一的，但是允许为空值。

全文索引

只能在文本类型CHAR,VARCHAR,TEXT类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行like模糊查询时效率比较低，这时可以创建全文索引。 MyISAM和InnoDB中都可以使用全文索引。

空间索引

MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。

前缀索引

在文本类型如CHAR,VARCHAR,TEXT类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

其他（按照索引列数量分类）

单列索引

组合索引

组合索引的使用，需要遵循最左前缀匹配原则（最左匹配原则）。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。

索引的数据结构

索引是在MySQL的存储引擎层中实现的，而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同，而且也不是所有的引擎都支持所有的索引类型。

常见的索引类型有如下几种:

BTREE 索引 ：最常见的索引类型，大部分索引都支持 B 树索引。
HASH 索引：只有Memory引擎支持，使用场景简单。
R-tree索引（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少，不做特别介绍。
Full-text （全文索引）：全文索引也是MyISAM的一个特殊索引类型，主要用于全文索引，InnoDB从Mysql5.6版本开始支持全文索引。

MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持

索引	INNODB引擎	MYISAM引擎	MEMORY引擎
BTREE索引	支持	支持	支持
HASH 索引	不支持	不支持	支持
R-tree 索引	不支持	支持	不支持
Full-text	5.6版本之后支持	支持	不支持

重复一遍:
我们平常所说的索引，如果没有特别指明，都是指B+树（多路搜索树，并不一定是二叉的）结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用 B+tree 索引，统称为索引。

Hash表

Hash表，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。

二叉查找树

二叉查找树，又名二叉排序树，特点是左孩子的值<根的值<右孩子的值

现在看，貌似二叉排序树的查找效率还不错对吧，但是如果遇到下面这种情况就糟糕了

显然这种情况下出现，会导致二叉排序树的优势黯然无光

平衡二叉树

平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。

就这个特点来看，可能各位会觉得这就很好，可以达到二叉树的理想的情况了。然而依然存在一些问题：

时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）
平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B树：改造二叉树

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？

假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+4*2=16）。

因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16K）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。

这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：

B树的节点中存储着多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
父节点当中的元素不会出现在子节点中。
所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

举个例子，在b树中查询数据的情况：
假如我们查询值等于10的数据。查询路径磁盘块1->磁盘块2->磁盘块5。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，10<15，走左路，到磁盘寻址磁盘块2。

第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<10，到磁盘中寻址定位到磁盘块5。

第三次磁盘IO：将磁盘块5加载到内存中，在内存中从头遍历比较，10=10，找到10，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。

相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。

过程如图：

看到这里一定觉得B树就很理想了，但是前辈们会告诉你依然存在可以优化的地方：

B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树：改造B树

B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题

B树：非叶子节点和叶子节点都会存储数据。
B+树：只有叶子节点才会存储数据，非叶子节点至存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

B+树的最底层叶子节点包含了所有的索引项。从图上可以看到，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，所以放索引的磁盘块锁存放的索引数量是会跟这增加的，所以相对于B树来说，B+树的树高理论上情况下是比B树要矮的。也存在索引覆盖查询的情况，在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。

举个例子：

等值查询：
假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走左路，到磁盘寻址磁盘块2。

第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，到磁盘中寻址定位到磁盘块6。

第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。（这里需要区分的是在InnoDB中Data存储的为行数据，而MyIsam中存储的是磁盘地址。）

过程如图：

范围查询：
假如我们想要查找9和26之间的数据。查找路径是磁盘块1->磁盘块2->磁盘块6->磁盘块7。

首先查找值等于9的数据，将值等于9的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘IO。

查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块6，键值9开始向后遍历筛选所有符合筛选条件的数据。

第四次磁盘IO：根据磁盘6后继指针到磁盘中寻址定位到磁盘块7，将磁盘7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将data缓存到结果集。

主键具备唯一性（后面不会有<=26的数据），不需再向后查找，查询终止。将结果集返回给用户。

可以看到B+树可以保证等值和范围查询的快速查找，MySQL的索引就采用了B+树的数据结构。

Mysql的索引实现

上面说过索引是Mysql在存储引擎层面实现的，因此对于不同的存储引擎底层索引的实现也有区别，这里主要分析MyIsam和Innodb存储引擎对B+ tree索引的底层实现

MyIsam索引

Myisam的数据文件有3个，.frm是表结构，.myi是索引文件，.myd是数据文件

以一个简单的user表为例。user表存在两个索引，id列为主键索引，age列为普通索引

CREATE TABLE `user`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = MyISAM
  AUTO_INCREMENT = 1
  DEFAULT CHARSET = utf8;

MyISAM的数据文件和索引文件是分开存储的。MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。

主键索引

表user的索引存储在索引文件user.MYI中，数据文件存储在数据文件 user.MYD中。

简单分析下查询时的磁盘IO情况：

根据主键等值查询数据：

select * from user where id = 28;

先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于30的索引项。（1次磁盘IO）
从索引项中获取磁盘地址，然后到数据文件user.MYD中获取对应整行记录。（1次磁盘IO）
将记录返给客户端。

磁盘IO次数：3次索引检索+记录数据检索。

根据主键范围查询数据：

select * from user where id between 28 and 47;

先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历比较16<28，18<28，28=28<47。查找到值等于28的索引项。

根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）

我们的查询语句时范围查找，需要向后遍历底层叶子链表，直至到达最后一个不满足筛选条件。

向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）
最后得到两条符合筛选条件，将查询结果集返给客户端。

磁盘IO次数：4次索引检索+记录数据检索。

备注:以上分析仅供参考，MyISAM在查询时，会将索引节点缓存在MySQL缓存中，而数据缓存依赖于操作系统自身的缓存，所以并不是每次都是走的磁盘，这里只是为了分析索引的使用过程。

辅助索引

在 MyISAM 中,辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。

可以看出，MyISAM中主键索引和其他索引在结构上没有什么不同，主键索引就是一个名为PRIMARY的唯一非空索引。

并且主键索引按照主键排序，辅助索引按照辅助的索引列值进行排序

InnoDB索引

Innodb的数据文件有两个，.frm是表结构文件，.ibd是索引和数据存储的文件

主键索引（聚簇索引）

每个InnoDB表都有一个聚簇索引，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：
1.在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。
2.如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
3.如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。

除聚簇索引之外的所有索引都称为辅助索引。在中InnoDB，辅助索引中的叶子节点存储的数据是该行的主键值。在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。

这里以user_innodb为例，user_innodb的id列为主键，age列为普通索引。

CREATE TABLE `user_innodb`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = InnoDB;

InnoDB的数据和索引存储在一个文件t_user_innodb.ibd中。InnoDB的数据组织方式，是聚簇索引。

主键索引的叶子节点会存储数据行，辅助索引只会存储主键值。

因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引

优点:

缺点:

等值查询数据：

select * from user_innodb where id = 28;

先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项，直接可以获取整行数据。将改记录返回给客户端。（1次磁盘IO）

磁盘IO数量：3次。

辅助索引

除聚簇索引之外的所有索引都称为辅助索引，InnoDB的辅助索引只会存储主键值而非磁盘地址。

以表user_innodb的age列为例，age索引的索引结果如下图。

底层叶子节点的按照（age，id）的顺序排序，先按照age列从小到大排序，age列相同时按照id列从小到大排序。

使用辅助索引需要检索两遍索引：首先检索辅助索引获得主键，然后使用主键到主索引中检索获得记录。

画图分析等值查询的情况：

select * from t_user_innodb where age=19;

根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。

磁盘IO数：辅助索引3次+获取记录回表3次

组合索引

还是以自己创建的一个表为例：表 abc_innodb，id为主键索引，创建了一个联合索引idx_abc(a,b,c)。

CREATE TABLE `abc_innodb`
(
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a`  int(11)     DEFAULT NULL,
  `b`  int(11)     DEFAULT NULL,
  `c`  varchar(10) DEFAULT NULL,
  `d`  varchar(10) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_abc` (`a`, `b`, `c`)
) ENGINE = InnoDB;

查询语句:

select * from abc_innodb order by a, b, c, id;

组合索引的数据结构：

组合索引的查询过程：

select * from abc_innodb where a = 13 and b = 16 and c = 4;

最左前缀匹配原则

最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。

在组合索引树中，最底层的叶子节点按照第一列a列从左到右递增排列，但是b列和c列是无序的，b列只有在a列值相等的情况下小范围内递增有序，而c列只能在a，b两列相等的情况下小范围内递增有序。

就像上面的查询，B+树会先比较a列来确定下一步应该搜索的方向，往左还是往右。如果a列相同再比较b列。但是如果查询条件没有a列，B+树就不知道第一步应该从哪个节点查起。

可以说创建的idx_abc(a,b,c)索引，相当于创建了(a)、（a,b）（a,b,c）三个索引。

组合索引的最左前缀匹配原则：使用组合索引查询时，mysql会一直向右匹配直至遇到范围查询(>、<、between、like)就停止匹配。

覆盖索引

覆盖索引并不是说是索引结构，覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候，我们只可以拿到主键值，相当于获取数据还需要再根据主键查询主键索引再获取到数据。但是试想下这么一种情况，在上面abc_innodb表中的组合索引查询时，如果我只需要abc字段的，那是不是意味着我们查询到组合索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是覆盖索引。

可以看一下执行计划：

覆盖索引的情况：

未使用到覆盖索引：

避免回表

在InnoDB的存储引擎中，使用辅助索引查询的时候，因为辅助索引叶子节点保存的数据不是当前记录的数据而是当前记录的主键索引，索引如果需要获取当前记录完整数据就必然需要根据主键值从主键索引继续查询。这个过程我们称为回表。想想回表必然是会消耗性能影响性能。那如何避免呢？

使用索引覆盖，举个例子：现有User表（id(PK),name(key),sex,address,hobby…）

如果在一个场景下，select id,name,sex from user where name ='zhangsan';这个语句在业务上频繁使用到，而user表的其他字段使用频率远低于它，在这种情况下，如果我们在建立 name 字段的索引的时候，不是使用单一索引，而是使用联合索引（name，sex）这样的话再执行这个查询语句是不是根据辅助索引查询到的结果就可以获取当前语句的完整数据。这样就可以有效地避免了回表再获取sex的数据。

联合索引不需要加上id,是因为辅助索引的叶子节点保存了主键的id值

这里就是一个典型的使用覆盖索引的优化策略减少回表的情况。

联合索引的使用

联合索引，在建立索引的时候，尽量在多个单列索引上判断下是否可以使用联合索引。联合索引的使用不仅可以节省空间，还可以更容易的使用到索引覆盖。试想一下，索引的字段越多，是不是更容易满足查询需要返回的数据呢。比如联合索引（a_b_c），是不是等于有了索引：a，a_b，a_b_c三个索引，这样是不是节省了空间，当然节省的空间并不是三倍于（a，a_b，a_b_c）三个索引，因为索引树的数据没变，但是索引data字段的数据确实真实的节省了。

联合索引的创建原则，在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面，频繁使用代表索引利用率高，区分度高代表筛选粒度大，这些都是在索引创建的需要考虑到的优化场景，也可以在常需要作为查询返回的字段上增加到联合索引中，如果在联合索引上增加一个字段而使用到了覆盖索引，那我建议这种情况下使用联合索引。

联合索引的使用

考虑当前是否已经存在多个可以合并的单列索引，如果有，那么将当前多个单列索引创建为一个联合索引。
当前索引存在频繁使用作为返回字段的列，这个时候就可以考虑当前列是否可以加入到当前已经存在索引上，使其查询语句可以使用到覆盖索引。

B-Tree索引对哪些类型的查询有效

全值匹配: 查询条件中使用到的列和索引中的所有列匹配

创建了emp表，并创建一个联合索引，下面演示一下全值匹配:

匹配最左前缀: 仅仅使用索引中最左边列进行查找，例如当前例子中，只有 (name),(name,age),(name,age,gae1)这样的查询索引才会生效，而(age),(age,age1)不会生效
匹配列前缀: 仅仅使用索引中的第一列，并且只使用第一列开头一部分字符进行查找

#为name创建一个索引，该索引只会匹配name的前两个字符进行查找
create index name_index  on emp(name(2));

测试:

select * from emp where name="dhy"

该条sql查询语句，会先按照name的前面两个字符dh查询出所有匹配的记录，再从这个集合中查询出name=dhy的记录

匹配范围值，我们可以利用索引查询姓名在dhy到xpy之间的人
精确匹配某一列并范围匹配另外一列: 例如: 查询name=dhy并且age在18到20之间的记录，第一列name全匹配，第二列age范围匹配
只访问索引的查询： B-Tree通常支持"只访问索引的查询"。即查询只需要访问索引，而无须访问数据行，这个就是我们

因为索引树中的节点是有序的，所以除了除了按值查找之外，索引还可以用与查询中的ORDER BY操作(按顺序查找)。一般来说，如果B-Tree可以按照某种方式查到值，那么也可以按照这种方式用于排序。所以，如果ORDER BY子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。

B-Tree索引的限制

如果不是按照索引的最左列开始查找，则无法使用索引。例如：上面的例子中，索引无法查询age=1的记录，也无法查询age1=0的记录
不能跳过索引中的列。例如: 无法使用索引查询name=dhy并且age1=1的记录，如果不指定age，则MySQL只能使用索引的第一列。
如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询。例如: where name like “d%” and age=1 ，这个查询只能使用索引的第一列，因为这里like是一个范围条件。

也有一些限制并不是B-Tree本身导致的，而是MYSQL优化器和存储引擎使用索引的方式导致的。

小结

MySQL的数据查询过程，二级索引需要回表到主键索引才可以查询出数据(Innodb)
MySQL加载索引时，按页加载，一个索引页16K，所以三层索引树，可以支持2000万左右的数据查询。
索引对多个值进行排序的依据是CREATE TABLE 语句中定义索引时列的顺序。
索引是一个有序的数据结构，当有序性被打破时，索引不生效。例如在字段上加函数、左侧模糊查询、联合索引不符合最左前缀等，皆是无法找到有序的索引树。（左侧模糊匹配时，无法知道字段左侧还存在多少字符，无法利用已知的索引去匹配，只能全表扫描）

扩展

哈希索引

哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。

对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且在不同键值的行计算出来的哈希码也不一样。

哈希索引将所有哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

在MySQL中，只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索引类型。Memory引擎同时也支持B-Tree索引。值得一提的是，Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

举例:

create table testhash 
 (
 fname varchar(50) not null,
 lname varchar(50) not null,
  key using hash(fname)
  )
  engine=memory;

表中有如下数据:

假设使用假象的哈希函数f(),它返回值如下:

f("Arjen")=2323
f("Baron")=7437
f("Peter")=8784
f("Vadim")=2458

则哈希索引的数据结构如下:

注意每个槽的编号是顺序的，但是数据行不是。现在，来看下面这个查询

select lname from testhash where fname="Peter";

MySQL先计算"Peter"的哈希值，并使用该值寻找对应的记录指针，因为f(“Peter”)=8784,所以MySQL在索引中查找8784，可以找到指向第3行的指针，最后一步是比较第三行的值是否为"Peter",以确保就是要查找的行。

因为索引自身只需要存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有其限制:

因为这些限制，哈希索引只适合某些特定的场景，而一旦适合哈希索引，则它带来的性能提升会非常显著。

innodb对哈希索引的使用

InnoDB引擎有一个特殊的功能叫做"自适应哈希索引"。当InnoDB注意到某些索引值被频繁使用时，它会在内存只能够基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找，这是一个完全自动的，内部的行为，用户无法控制或者配置，不过如果有必要，完全可以关闭该功能。

创建自定义的哈希索引，如果存储引擎不支持哈希索引，则可以模拟像InnoDB一样创建哈希索引，这可以享受一些哈希索引的遍历，例如:只需要很小的索引就可以为超长的键创建索引。

思路很简单: 在B-Tree基础上创建一个伪哈希索引，这和真正的哈希索引不是一回事，因为还是使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的WHERE子句中手动指定使用哈希函数。

举例: 如果需要存储大量的URL，并需要根据URL进行搜索查找，如果使用B-Tree来存储URL，存储的内容就会很大，因为URL本身很长，正常情况下会像下面这样查询:

select id from url where url="http://www.mysql.com";

若删除原来URL列上的索引，而新增一个被索引的url_crc列，使用CRC32做哈希，就可以使用下面的方式查询:

select id from url where url="http://www.mysql.com" 
and url_crc=CRC32("http://www.mysql.com");

采用这种方式，记住不要使用SHA1()和MD5()作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量存储空间，而且查询更慢。SHA1()和MD5()是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。简单的哈希函数的冲突在一个可以接受的范围，同时又能提供更好的性能。

如果数据表非常大，CRC32()会出现大量的哈希冲突，则可以考虑自己实现一个简单的64位哈希函数，这个自定义函数要返回整数，而不是字符串。一个简单的办法可以使用MD5函数返回值的一部分来作为自定义哈希函数。这可能比自己写一个哈希算法性能要要差，不过这样实现最简单。

处理哈希冲突，当使用哈希索引进行查询的时候，必须在WHERE字句中包含常量值:

因为一旦出现哈希冲突，另一个字符串的哈希值也是1560514994，则下面的查询是无法正确工作的

小总结: 在innodb中，我们可以考虑在某个经常被查询的字段并且该字段的为字符串类型且长度很长的情况下，增加一个哈希索引列，确保得到的哈希码长度适中，且冲突较小，以此来加快查询速度

索引是最好的解决方案吗?

上面我们已经对索引的类型和底层数据结构进行了介绍和分析，下面我们思考一下索引是万能的吗?

索引并不总是好的工具，总的来说，只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作的时候，索引才有效。对于非常小的表，大部分情况下简单的全表扫描更高效，对于中到大型的表，索引就非常有效，但对于特大型的表，建立和使用索引的代价将随之增长。

这种情况下，则需要一种技术可以直接区分出查询需要的一组数据，而不是一条记录一条记录地匹配。例如可以使用分区技术。

高性能索引策略

独立的列

前缀索引和索引选择性

有时候需要索引很长的字符列，这会让索引变得大且慢。一个策略是前面提到过的模拟哈希索引，但有时候这样做还不够，还需要做些什么呢?

讲了那么多，那么该如何创建前缀索引呢?

总结: 在保证前缀索引长度尽可能短的情况下，让其选择性接近完整列的选择性

后缀索引

有时候后缀索引也有用途(例如:找到某个域名的所有点子邮件地址)。

mysql原生并不支持反向索引，但是可以把字符串反转后存储，并基于此建立前缀索引，可以通过触发器来维护这种索引。

多列索引

如果在EXPLAIN中看到有索引合并，应该好好检查一下查询和表的结构，看看是否存在问题，也可以通过参数optimizer_switch来关闭索引合并功能。也可以使用IGNORE INDEX提示让优化器忽略掉某些索引。

选择合适的索引顺序

选择性越高意味着该列值的重复性越低

上面说的其实是一个非常典型的问题，那这个典型的问题如何解决呢？看下面这个例子:

总结:根据列的选择性高低和使用频率两者结合考虑，并且需要考虑特殊的情况—例如:系统账号问题

在Innodb中按主键顺序插入行

对比使用UUID作为聚簇索引的表:

覆盖索引

定义:

一个索引包含(或者说覆盖)所有需要查询的字段的值，我们就称为"覆盖索引"。

覆盖索引的好处:

延迟关联

很好理解，因为需要获取额外的列信息，因此只能通过辅助索引找打主键索引，去问他要,这个过程上面讲过，叫做回表

个人想法:如果内层查询可以查询出主键值，那么内存查询也可以使用索引覆盖，因为辅助索引叶子节点也包含主键值。然后将查询出来的主键值传递到外层查询中，然后外层查询可以利用主键值，查询出需要的数据，也不需要进行回表啥的操作。

在高性能mysql书的覆盖索引这节的最后也给我们提供了一个小技巧，其实就是我上面的个人想法: Innodb的二级索引可以有效利用这些额外的主键列来覆盖查询

使用索引扫描来做排序

这里也指出了一个不适用索引的场景和优化方案: 尽可能通过索引就能获取到需要的字段信息，即覆盖索引，避免回表查询带来的随机I/O的性能损耗。

上面这点要记住

压缩前缀索引

冗余和重复索引

我们还需要考虑一个问题，就是索引过多带来的插入效率降低的问题

索引和锁

总结: 即使使用了索引，InnoDB也可能锁住一些不需要的数据，如果不能使用索引查找和锁定行的话问题会更糟糕，mysql会做全部扫描并锁住所有的行。

索引案例学习

in()的巧用

我们创建一个(sex,name)索引，当我们某个查询不限制性别时，常理来说，sql语句会写成下面这样:

select * from peo where name="xxx";

但是这样显然无法利用上最左前缀原则，那怎么解决呢？看下面这种写法

select * from peo where sex in ('m','f') and name="xxx";

这里还有一个原则：我们可以使用IN()来代替范围查询，另外一点，我们需要尽可能将要做范围查询的列放到索引的后面，以便优化器能使用尽可能多的索引列。

避免范围条件

优化排序

总结

到此为止，也只是介绍了索引的大概，并没有讲解的非常透彻，大家还是要多多实战，并且有空去研究一下底层的具体实现

后续的章节，也会继续对索引的使用和其他方面进行讲解，感兴趣可以持续关注

参考资料

高性能Mysql第三版

深入浅出mysql

innodb技术内幕

一文搞懂MySQL索引所有知识点

「 MySQL高级篇」MySQL索引原理，设计原则

MySQL进阶【二】—— 一文讲清楚为什么MySQL选择B+树索引

MySQL还能这样玩---第三篇之索引也可以如此easy

索引基本概念

索引是什么

索引优势和劣势

索引类型

主键索引

普通索引

唯一索引

全文索引

空间索引

前缀索引

其他（按照索引列数量分类）

单列索引

组合索引

索引的数据结构

Hash表

二叉查找树

平衡二叉树

B树：改造二叉树

B+树：改造B树

Mysql的索引实现

MyIsam索引

主键索引

辅助索引

InnoDB索引

主键索引（聚簇索引）

辅助索引

组合索引

最左前缀匹配原则

覆盖索引

避免回表

联合索引的使用

B-Tree索引对哪些类型的查询有效

B-Tree索引的限制

小结

扩展

哈希索引

innodb对哈希索引的使用

索引是最好的解决方案吗?

高性能索引策略

独立的列

前缀索引和索引选择性

后缀索引

多列索引

选择合适的索引顺序

在Innodb中按主键顺序插入行

覆盖索引

延迟关联

使用索引扫描来做排序

更多示例

压缩前缀索引

冗余和重复索引

索引和锁

索引案例学习

in()的巧用

避免范围条件

优化排序

总结

参考资料

相关文章

热门标签

最新文章

目录