索引

索引图解

首先数据是以文件的行持存储在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，要从500w行的数据里面检索一条数据，只能一次便利这张表的全部数据，直到找到这条数据。

但是有了索引之后，只需要在索引里面检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。

这就像我们从一本500页的书里面去找特定的一小截的内容，肯定不可能从第一页开始翻。呢么这一本书有专门的目录，他可能只有几页的内容，它是由页码来组织的，可以根据拼音或者偏旁部首来查找，只要确定内容对应的页码，就能很快地找到我们想要的内容。

索引类型

怎么创建一个索引

在InnoDB里面，索引的类型有三种：

1. 普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何限制。

2. 唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，逐渐索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。逐渐索引用primary key创建。

3. 全文索引（Fulltext）：针对比较大的数据，比如我们存放的消息内容，有几kb的数据的这种情况，如果要解决like查询效率低的问题，可以创建全文索引。只有文本类型的字段可以创建全文索引，比如char，varchar，text

全文索引的使用：

MyISAM和InnoDB支持全文索引。 这个索引的三种类型：普通、唯一、全文。 我们说索引是一种数据结构，哪么它到底应该选择一种什么数据结构，才能实现数据高效检索？

二分查找

二分查找是一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。

有序数组的等值查询和比较查询效率非常高，但是跟新数据的时候会出现一个问题，可能要挪动大量的数据（改变index），所以知识和存储静态数据。

为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查询效率还是不够高。

二叉查找树（BST Binary Search Tree)

左子树索引的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。 二叉查找树即能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题： 就是它的查找耗时是和这棵树的深度有关系的，最坏的情况下时间复杂度会退化成O(n)。

这会变成链表（我们把这种树叫做“斜树”），这种情况下不能达到加速索引速度的目的，和顺序查找效率是没有区别的。 造成倾斜，是因为左右子树深度差太大了，这棵树的左子树根本没有节点，也就是他不够平衡。所以，我们有没有左右子树深度相差不是哪么大，更加平衡的树呢？

平衡二叉树（AVL Tree）（左旋、右旋）

AVL Trees（Balanced binary search trees） 平衡二叉树的定义：左右子树深度差绝对值不能超过1。 这个时候我们再按循序插入1、2、3、4、5 6，一定是这样的，不会变成一颗斜树。

模拟 AVL Tree

它会存储三块内容：

1. 索引的键值。比如我们在id上面创建了一个索引，我在用where id =1的条件查询的时候就会找到索引里面的id的这个键值。

2. 数据的磁盘地址，因为索引的作用就是去查找数据的存放地址。

3. 因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如找到26的时候，走右边，到下一个树的节点，继续判断。

行Row

InnoDB存储引擎是面向行的（row-oriented），也就是说数据的存放按行进行存放。 https://dev.mysql.com/doc/refman/5.7/en/innodb-row-format.html

Antelope是InnoDB内置的文件格式，有两种行格式：

1. REDUNDANT ROW FORMAT

2. COMPACT ROW FORMAT（5.6默认） Barracuda是InnoDB plugin支持的文件格式，新增了两种行格式：

DYNAMIC ROW FORMAT（5.7默认）

COMPRESSED ROW Format

innodb_file_format在配置文件中指定；row_format则在创建数据表时指定。

在创建表的时候可以指定行格式。

查看行格式：

树用于存储索引数据

首先索引的数据，是放在硬盘上的。查看数据和索引的大小：

当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次IO。InnoDB操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是16k（16384字节）。哪么，一个树的节点就是16k的大小。 如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16k的容量，所以访问一个树节点，进行一次io的时候，浪费了大量的空间。

所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。

如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数越多，消耗的时间就越多。

所以我们的解决方案是什么呢？

1. 让每一个节点存储更多的数据

2. 节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”）

因为分叉数越多，树的深度就会减少（根节点是0）。 这样我们的书是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？

这个时候，我们的树就不再是二叉，而是多叉，或者叫做多路

B+树（加强版多路平衡查找树）

B Tree的效率已经很高了，为什么mysql还要对B Tree进行改良，最终使用了B+Tree呢？

总体上来说，这个B树的改良版本解决的问题比B Tree更全面。

我们来看一下InnoDB里面的B+树的存储结构：

Mysql中的B+Tree有几个特点：

1. 它的关键字的数量是跟路数相等的。

2. B+Tree的根节点和枝节点都不会存储数据，只有也子节点才会存储数据。搜索的关键字不会直接返回，回到最后一层的也子节点。比如我们搜索id=28，虽然在第一层直接命中了，但是全部的数据在也子节点上面，所以我还要继续往下搜索，一直到叶子节点。

假设索引字段是bigint类型，长度8字节。指针大小在InnoDB源码中设置为6字节，这样一共14字节。非叶子节点可以存储16384/14=1170个这样的单元（键值+指针），代表有1170个指针。

树深度上为2的时候，有1170^2个叶子节点，可以存储的数据为1170×1170×16=21802400

在查找数据时一次页的查找代表一次io，也就是说，一张2000w左右的表，查询数据最多需要访问3次磁盘。 所以InnoDB中B+树深度一般为1-3层，它就是能满足千万级的数据存储。 3. B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指下一个也子节点的第一个数据，形成一个有序的链表的结构。 4. 它是根据左闭右开的区间[)来检索数据。

1. 比如我们要查找28，在根节点就找到键值，但是因为它不是页子节点，所以会继续往下搜索，28是[28,66)的左开右闭的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在也子节点上找到需要的数据。

2. 第二个，如果是范围查询，比如要查询从22到60的数据，当找到22之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。

总结一下，InnoDB中B+Tree的特点：

1. 它是BTree的变种，BTree能解决的问题，它都能解决。BTree解决的两大问题是什么？（每个节点存储更多关键字；路数更多）

2. 扫库、扫表能力增强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整颗B+Tree拿到所有的数据）

3. B+Tree的磁盘读写能力相当于B Tree来说更强（根节点和直枝节点不保存数据区，所以一个节点可以保存多个关键子，一次磁盘加载的关键字更多）

4. 排序能力更强（因为也子节点上有下一个数据区的指针，数据形成了链表）

5. 效率更加稳定（B+Tree永远是在也子节点拿到数据，所以IO次数是稳定的）

索引方式：真的是用B+Tree吗？

在navicat的工具中，创建索引，索引方式有两种，Hash和B Tree。

Hash：以KV的形式检索数据，也就是说，他会根据索引字段生成哈希码和指针，指针指向数据。

哈希索引有什么特点？

1. 他的时间复杂度是o(1)，查询速度比较快。因为哈希索引里面的数据不是按顺序存储的，所以不能用来排序。

2. 我们在查询数据的时候要根据键值计算哈希码，所以它只能支持等值查询（=IN），不支持范围查询（> < >= <= between and）。

另外一个就是如果字段重复值很多的时候，就会出现大量的哈希冲突（从用拉链法解决），效率会底下。

MySql架构

Mysql是一个支持插件存储引擎的数据库。在MySql里面，每个表在创建的时候都可以指定它所使用的存储引擎。 这里我们主要关注一下最常用的两个存储引擎，MyISAM和InnoDB的索引的实现。

Mysql数据存储文件

首先，Mysql的数据都是文件的形式存放到磁盘中，我们可以找到一个数据目录的地址。在Mysql中有这么一个参数，我们看一下：

每一个数据库有一个目录，我们新建一个叫做gupao的数据库，哪么这里就有一个gupao的文件夹。 在这个数据库中我们建5张表：archive、innodb、memory、myisam、csv。我们进入gupao的目录，发现这里面有一些跟我们创建的表明对应的文件。

在这里我们能看到，每一张InnoDB的表有两个文件（.frm和.ibd)，MyISAM的表有三个文件（.frm .MYD .MYI）

有一个是相同的文件，.frm .frm是mysql里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成。 我们主要看一下其他两个文件是怎么实现mysql不同的存储引擎的索引的。

MyISAM

在MyISAM里面，另外有两个文件：

1. .MYD文件，D代表data，是MyISAM的数据文件，存放数据记录，比如我们的user_myisam表的所有的表数据。

2. .MYI文件，I表示Index，是MyISAM的索引文件，存放索引，比如我们在id字段上面创建一个主键索引，哪么主键索引就是在这个索引文件里面。

也就是说在MyISAM里面，索引和数据是两个独立的文件。

哪我们怎么根据索引找到数据呢？

MyISAM的B+Tree里面，也子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI中找到键值后，会到数据文件.MYD中获取相应的数据记录。

这里是逐渐索引，如果是辅助索引，有什么不一样的呢？

在MYISAM里面，辅助索引也在.MYI这个文件里面。

辅助索引跟主键索引存储和检索数据方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据。

InnoDB

InnoDB只有一个文件（.ibd文件），哪索引放在那里呢？

在InnoDB里面，它是以逐渐萎缩引来组织数据的存储的，索引所以文件和数据文件是同一个文件，都在.ibd文件里面。

在InnoDB的主键索引的叶子节点上，他直接存储了我们的数据。

什么叫做聚集索引（聚簇索引）？

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。（比如字典的目录是按照拼音排序的，内容也是按照拼音排序的，按拼音排序的这种目录就叫聚集索引。

在InnoDB里面，它组织数据的方式叫做（聚集）索引组织表（clustered index organize table），索引逐渐索引是聚集索引，非主键都是非聚集索引。

如果InnoDB里面主键是这样存储的，哪主键之外的索引，比如我们在name字段上面建普通索引，优势怎么存储和检索数据的呢？

InnoDB中，主键索引和辅助索引是有一个主次之分的。

复制索引存储的是辅助索引的主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。

比如我们用name索引查询name=‘青山’，他会在叶子结点找到主键值，也就是id=1，然后再到主键索引的叶子结点拿到数据。

为什么在辅助索引里面存储的是主键值而不是逐渐的磁盘地址呢？如果主键的数据类型比较大，是不是比存地址更消耗空间呢？

我们前面说了B Tree是怎么时间一个节点存储多个关键字，还保持平衡呢？

是因为有分叉和合并的操作，这个时候键值的地址会发生变化，所以在辅助索引里不能存储地址。

另外一个文件，如果一张表没有主键怎么办？

1. 如果我们定义了逐渐（PRIMARY KEY），哪么InnoDB会选择主键作为聚集索引。

2. 如果没有显示定义主键，则InnoDB会选择第一个不包含有null值的唯一索引作为主键索引。

3. 如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐藏的聚集索引，它绘随着行记录的写入而主键递增。

列的离散度

第一个叫做列的离散度，我们先来看一下列的离散度的公式：

count(distinct(column_name)):count(*)，列的全部不同值和所有数据行的比例。数据行数相同的情况下，分子越大，列的离散度就越大。

简单来说，如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。

了解了离散度的概念之后，我们再来思考一个问题，我们在name上面建立索引和在gender上面建立索引有什么区别。

当我们用在gender上建立索引去检索数据的时候，由于重复值太多，需要扫描的行数就更多。例如：我们现在在gender列上面创建一个索引，然后看一下执行计划。

而name的离散度更高，比如‘青山’这个名字，只需要扫描一行。

查看表上的索引，Cardinality 代表基数，代表预估的不重复的值的数量。索引的基数与表总行数越接近，列的离散度就越高。 show indexes from user_innodb;

如果在B+Tree里面的重复值太多，MYSQL的优化器发现走索引跟使用全表扫描差不多的时候，就算建了索引，也不一定会走索引。 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

这个给我们的启示是什么？建立索引，要使用里离散度（选择度）更高的字段。

联合索引最左匹配

前面我们说的都是针对单列创建的索引，但有时候我们的多条件查询的时候，也会建立联合索引。单列索引可以看成是特殊的联合索引。

比如我们在user表上面，给name和phone建立一个联合索引。

联合索引在B+Tree中是符合的数据结构，它是按照从左到右的顺序来建立搜索树的（name在左边，phone在右边）。

从这张图可以看出，name是有序的，phone是无序的。当name相等时，phone才是有序的。

这个时候我们使用 where name = '青山' and phone = '136×' 去查询数据的时候，B+Tree会优先比较name来确定下一步应该搜索的方向，往左还是往右。如果name相同的时候在比较phone。但是如果查询条件没有name，就不知道第一步应该查哪个节点，因为建立搜索树的时候name是第一个比较因子，所以用不到索引。

覆盖索引

回表：非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查处索引里面没有的数据，它比基于主键索引的查询多扫描了一颗索引树，这个过程就叫回表。

例如：select * from user_innodb where name = '青山';

在辅助索引里面，不管是单列索引还是联合索引，如果select的数据列只用从索引中就能够取得，不必从数据区中取，这个时候使用的索引就叫做覆盖索引，这样就避免了回表。

我们先来创建联合索引：

这三个查询语句都用到了覆盖索引：

extra里面值为“Using index”代表使用了覆盖索引。

select * ，用不到覆盖索引。

如果改成只用where phone = 查询呢？动手试试？

很明显，因为覆盖索引减少了io次数，减少了数据的访问量，可以大大提升查询效率。

索引条件下推（ICP)

https://dev.mysql.com/doc/refman/5.7/en/index-condition-pushdown-optimization.html

再来看这么一张表，在last_name和first_name上面创建联合索引。

关闭ICP：

查看参数

现在我们要查询所有姓wang，并且名字最后一个字是zi的员工，比如王胖子、王瘦子。查询的sql：

这条sql有两种执行方式：

1. 根据联合索引查处所有行wang的二级索引数据，然后回表，到主键索引上查询全部符合条件的数据（3条数据）。然后返回给server层，在server层过滤出名字以zi结尾的员工。

2. 根据联合索引查处所有姓wang的二级索引数据（3个索引），然后从二级索引中筛选出first_name以zi结尾的索引（1个索引），然后再回表，到主键索引上查询全部符合条件的数据（1条数据），返回给server层。

   

很明显，第二种方式到主键索引上查询的数据更少。

注意，索引的比较实在存储进行的，数据记录的比较，是在server层进行的。而当first_name的条件不能用于索引过滤，server层不会把first_name的条件传递给存储引擎，所以读取了两条没有必要的记录。

这时候，如果满足last_name='wang'的记录有100000条，就会有99999条没有必要读取的记录。

执行以下sql，Using where：

Using where 代表从存储引擎取回来的数据部全部满足条件，需要在server层过滤。

先用last_name条件进行索引范围扫描，读取数据表记录，然后进行比较，检查是否符合first_name like '%zi'的条件。此时3条中只有一条符合条件。

开启ICP：

此时执行计划，Using index condition: |id|select_type|table|partitions|type|possible_keys|key|key_len|ref|rows|filtered|Extra| |---|---|---|---|---|---|---|---|---|---|---|---| |1|SIMPLE|employees||ref|idx_lastname_firstname|idx_lastname_firstname|18|const|3|11.11|Using index condition| 把first_name like '%zi'下推给存储引擎后，只会从数据表读取所需的1条记录

索引条件下推（index condition pushdown），5.6以后完善的功能。只是用于二级索引。ICP的目标是减少访问表的完整行的读取量从而减少io操作。

索引的创建

1. 在用于where判断order排序和join的（on）字段上创建索引。

2. 索引的个数不要过多。--浪费空间，更新变慢。

3. 区分度低的字段，例如性别，不要建立索引。--离散度太低，导致扫描行数过多。

4. 频繁更新的值，不要作为主键或者索引。--页分裂

5. 组合索引把散列性高的值放在前面。

6. 创建复合索引，而不是修改单列索引。

7. 过长的字段，怎么建立索引

8. 为什么不建议用无序的值（例如身份证、uuid）作为索引？

什么时候用不到索引？

1. 索引列上使用函数（replace\substr\concat\sum count avg)、表达式、计算（+ - × /）：

2. 字符串不加引号，出现隐式转换

3. like条件中前面带% where条件中like abc%,like %2673%,like %8888都用不到索引吗？为什么？

过滤的开销太大，所以无法使用索引。这个时候可以用全文检索。 4. 负向查询 not like 不能：

!= (<>)和NOT IN在某些情况下可以：

注意一个sql语句是否使用索引，跟数据库版本、数据量、数据选择都有关系。

其实，用不用索引，最终都是所有其说了算。

优化器是基于什么的优化器？

基于cost开销（cost baser optimizer），它不是基于规则（Rule-Based Optimizer），也不是基于语法。怎么样开销小就怎么来。 https://dev.mysql.com/doc/refman/5.7/en/cost-model.html https://docs.oracle.com/cd/B10501_01/server.920/a96533/rbo.htm#38960