索引简介

索引的定义

在数据库系统的使用过程当中，数据的查询是使用最频繁的一种数据操作。最基本的查询算法是顺序查找，遍历表然后逐行匹配行值是否等于待查找的关键字，其时间复杂度为 O(n) 。当时间复杂度为 O(n) 的算法查询规模小的表、负载轻的数据库，也能有好的性能。但是数据增大的时候，时间复杂度为 O(n) 的算法显然是糟糕的，性能就很快下降了。为了提高查询速度发展提供了很多更优秀的查找算法，例如二分查找、二叉搜索树查找等，但是每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上。但是数据本身的组织结构不可能完全满足各种数据结构，所以在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，而这种数据结构就是索引。

索引的优缺点

优点

  • 索引大大减小了服务器需要扫描的数据量，从而大大加快数据的检索速度，这也是创建索引的最主要的原因
  • 索引可以帮助服务器避免排序和创建临时表
  • 索引可以将随机IO变成顺序IO
  • 索引对于InnoDB（对索引支持行级锁）非常重要，因为它可以让查询锁更少的元组，提高了表访问并发性
  • 关于InnoDB、索引和锁：InnoDB在二级索引上使用共享锁（读锁），但访问主键索引需要排他锁（写锁）
  • 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性
  • 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义
  • 在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间

  • 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

    缺点

  • 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加

  • 索引需要占用物理空间，除了数据表占用数据空间之外，每一个索引还要占用一定的物理空间，如果需要建立聚簇索引，那么需要占用的空间会更大
  • 对表中的数据进行增、删、改的时候，索引也要动态的维护，这就降低了整数的维护速度
  • 如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果

  • 对于非常小的表，大部分情况下简单的全表扫描更高效

    InnoDB 索引类型

    主键索引

    一张表有且仅有有一个主键索引，它是根据表的主键组织形成的，不允许重复、不允许为 NULL 。在InnoDB中，主键索引即存放索引又存放数据。

    1. ALTER TABLE TableName ADD PRIMARY KEY(column_list);

    普通索引

    这是最基本的索引类型，而且它没有唯一性之类的限制。普通索引可以通过以下几种方式创建：

  • 创建索引，例如CREATE INDEX <索引的名字> ON tablename (列的列表);

  • 修改表，例如ALTER TABLE tablename ADD INDEX [索引的名字] (列的列表);

  • 创建表的时候指定索引，例如CREATE TABLE tablename ( […], INDEX [索引的名字] (列的列表) )

    1. CREATE INDEX IndexName ON `TableName`(`字段名`(length));
    2. # 或者
    3. ALTER TABLE TableName ADD INDEX IndexName(`字段名`(length));

    唯一索引

    该索引对字段进行了限制，它要求该字段的值必须是唯一的，也就是所有记录中，该字段都不能出现重复的内容。比如在学生表中，就可以为身份证号设置唯一索引，这样便于查询，且可以保证不同学生的身份证号不出现重复。这种索引和前面的“普通索引”基本相同，但有一个区别：索引列的所有值都只能出现一次，即必须唯一。唯一性索引可以用以下几种方式创建：

  • 创建索引，例如CREATE UNIQUE INDEX <索引的名字> ON tablename (列的列表)

  • 修改表，例如ALTER TABLE tablename ADD UNIQUE [索引的名字] (列的列表)

  • 创建表的时候指定索引，例如CREATE TABLE tablename ( […], UNIQUE [索引的名字] (列的列表) )

    CREATE UNIQUE INDEX IndexName ON `TableName`(`字段名`(length));
# 或者
ALTER TABLE TableName ADD UNIQUE (column_list);

    全文索引

    全文索引是为了使得“关键词搜索”功能更加高效的一种方式，主要用于检索全文。使用LIKE关键字虽然在一定程度上也能进行全文检索，但是检索效率和全文索引不是一个量级的。

  • MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引；

  • MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引;
  • 只有字段的数据类型为 char、varchar、text 及其衍生系列才可以建全文索引

    注意： InnoDB内部并不支持中文、日文等，因为这些语言没有分隔符，可以使用插件辅助实现中文、日文等的全文索引。

//建表的时候
FULLTEXT KEY keyname(colume1,colume2)  // 创建联合全文索引列

//在已存在的表上创建
create fulltext index keyname on xxtable(colume1,colume2);

alter table xxtable add fulltext index keyname (colume1,colume2);

全文索引有独特的语法格式，需要配合 match 和 against 关键字使用：

  • match()函数中指定的列必须是设置为全文索引的列
  • against()函数标识需要模糊查找的关键字

其它详见：https://blog.csdn.net/mrzhouxiaofei/article/details/79940958

注意： InnoDB的全文索引的关键词最小索引长度为3，即against最小长度为3，当然这个是可以修改的。

复合索引

即一个索引包含多个列，然后按列的先后顺序逐层建立起的索引，先对第一列排序，排完才会逐渐对后面的列排序。

---建表时创建
 create table t_user(id varchar(20) primary key,name varchar(20),age int,key(name,age));

--建表后创建
 create index nameageindex on t_user(name,age);

索引的实现 - 图1
如果创建复合索引，那么查询的话sql语句中必须要用到复合索引最左边的字段，否则复合索引就会失效，即查询时不会使用到索引。其原因也很简单。创建的复合索引具有这样的排序规则：如果name一样就根据age排序，如果name和age一样就根据position排序。此外，mysql为了更好的利用复合索引，会在查询的时候为where语句调整字段顺序，比如“where age=31 and name=’bill’ ”原本是索引失效，最后会被调整为“ where name=’bill’ and age=31”，从而使用到复合索引。

select * From employees where name = 'bill' and position = dev

select * From employees where age = 31 and name = 'bill'
select * From employees where name = 'bill' and age = 31

select * From employees where position = 'dev' and name = 'bill'
select * From employees where  name = 'bill' and position = 'dev'

select * From employees where age = 31 and position = 'dev'
select * From employees where age = 31
select * From employees where position = 'dev'

因此，在上面的四组SQL中，第1、2、3组SQL是使用到了复合索引，而第4组则没有使用到复合索引。在InnoDB存储引擎中，如果能达到业务需求或者影响较小，应尽量使用一个复合索引代替多个普通的单列索引，而不是创建多个单列索引。原因如下：

  • 每一个索引是以b+树的形式存储的，而B+树的存储是需要占用存储空间，索引越多需要占用的磁盘空间也就越多
  • 当每插入或删除一个数据时，这个表中的索引都是需要维护的，索引越多维护也就越麻烦
  • 可以更加方便的进行索引覆盖

    索引结构

    B+树

    B+树的结构

    MySQL主要的存储引擎，如：InnoDB和MyISAM 都是采用B+树这一数据结构实现的索引，B+树是一种平衡多叉搜索树，它是在B树的基础上衍生而来的一种数据结构。

    B树的数据结构详见： https://www.yuque.com/docs/share/ebf9b18a-a6f7-42d6-b921-8a4a1b185f98?# 《B树》

未命名图片(1).png
下面是B+树的一下重要特征：

  • 所有数据存放在叶子结点，非叶子结点只存放索引，不存放数据
  • 一个非叶子结点中包含索引和结点指针，结点指针指向它的孩子结点，一般一个非叶子结点具有多个子结点
  • 非叶子结点的索引两端一定是指针，一个非叶子结点具有K个索引和K+1个结点指针
  • 数据全部存放在叶子结点之中，两个叶子结点之间通过双向指针连接，所有叶子结点形成一个双向链表

    问题： 为什么采用B+树作为数据库索引而不采用B树？

首先看一下B+树和B树的主要区别：

  • B树的所有节点都存储数据，也就是索引即数据，数据即索引
  • B树的叶子节点没有横向指针
  • B树的叶子节点没有全部节点信息，父节点不会在子节点出现

image.png
至于为什么数据库索引使用B+树而不使用B树主要有以下两个原因：

  • 存储数量：在MySQL中，每一页的大小通常都是固定的16KB，如果采用B树，由于B树的非叶子结点的索引即数据，数据即索引，但是每个结点（即一页）只有固定大小的16KB，如上图非叶子结点的data（也即索引）越大，能存放的索引数量就越少，这样势必导致树的高度越高，检索结点数量越多，磁盘I/O也就越多，检索效率也就越低。举个例子，如果一个数据是1KB大小，那么一个非叶子结点可以存储的索引就只有16个，可以三层非叶子结点存储的索引数量只有16^3=4096，如果要存储更多的数据，则必然要加高树的结构。
  • 范围查询：B+树相比B树更加适合范围查询，这主要取决于B+树的叶子结点（即数据页）之间采用指针，相互形成一个双向链表。B+树只需要通过二分查询找到查询下限，然后通过双向链表的横向遍历即可找到范围上限，而B树只能不断的中序遍历来查询指定范围内的数据。

    注意： B+树虽然更加适合范围查询，但是当树的高度相同时，B+树的单值查询的效率可能会略低于B树，因为B+树必须一路走到叶子结点，而B树可能不需要走到叶子结点就找到这个值，当然二者效率也不会相差特别大。但是MySQL数据库会进行很多范围查询，所以B+树还是很适合作为数据库索引的。

为什么不选其它的数据结构，比如：数组、哈希索引、二叉树作为索引可以参考下面文章： https://juejin.cn/post/6844904126392827917 https://www.modb.pro/db/134175

B+树索引查询过程

了解了B+树是数据库索引采用的数据结构之后，在介绍索引的具体实现之前，有必要了解以下一条SQL是怎么检索数据的。以“select * from user where id=8”为例：
image.png

  • 把第一层的磁盘块中的所有数据先加载到内存中去
  • 加载到内存中后，我们对我们需要的数据进行比较，然后找出下一个节点，并把下一个节点也加载到内存中去
  • 重复第二步，找到我们的叶子节点，并将数据读取到内存
  • 找到所需要的数据

    思考一： 当数据读取到内存后我们是如何进行比较的呢？

利用二分法查找，当我们数据大的时候，我们一个节点的数量可能是有几百上千个的。那我们要加快查询速度，就要快速比较，刚好我们每一层的数据都是线性有序的，就可以采用二分查找 ，时间复杂度为log2^n，在实际查询中这一步并不会占用太多时间。
索引的实现 - 图5

思考二： 上面那一步最耗时？

将数据从磁盘中读取到内存是最耗时的，也是查询过程中花费的主要时间，所以我们如果想降低查询时间，就必须减少读取次数，而MySQL的B+树索引将读取的次数控制在了2~3次，这就是MySQL索引高效查询的根本原因。至于为什么可以控制在2~3次，其原因如下：
每次读取数据都是一层一层的去读，而且是一个节点一个节点的去读，也就是说磁盘的读取次数就等于树的结构的层数。InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针一般也是4或8个字节，16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为10^3）。叶子节点存储数据，我们便算一个时间是1KB好了（往大了算），也就是说一个叶子节点至少可以存储16个数据，那么一个深度为3的B+Tree索引大约可以维护索引的实现 - 图6%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-36%22%20x%3D%22500%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2217%22%20x%3D%221223%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(1945%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-30%22%20x%3D%22500%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-33%22%20x%3D%221415%22%20y%3D%22583%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2217%22%20x%3D%223623%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(4345%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-30%22%20x%3D%22500%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-33%22%20x%3D%221415%22%20y%3D%22583%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=16%2A10%5E3%2A10%5E3&id=JzcAe)即大约至少1.6千万条数据，这已经是一个非常大的数据量了，对于一张普通的表来说一般3层的B+树是已经够用了的。

聚簇索引和非聚簇索引

聚簇索引

聚簇索引不是单独的一种索引类型，而是一种数据存储方式。这种存储方式是依靠B+树来实现的，根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时，方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引（叶子结点的）放到了一块，找到索引也就找到了数据。也就是说，聚簇索引的B+树的叶子结点存放的是行记录。

注意： 上面所说的索引是指位于B+树叶子结点的索引，并不是指非叶子结点的索引。

在InnoDB中，每张表有且仅有一个聚簇索引，一般来说是以主键组织的。因为InnoDB的数据文件（.idb）按主键聚集，所以InnoDB必须有主键（MyISAM可以没有），如果没有显示指定主键，则选取首个为唯一且非空的列作为主键索引，如果还没具备，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。因为InnoDB是主键组织表，因此在InnoDB中聚簇索引也称主键索引，如下所示：
image.png

  • B+树单个叶子节点内的行数据按主键顺序排列，物理空间是连续的（聚簇索引的数据的物理存放顺序与索引顺序是一致的）
  • 叶子节点之间是通过指针连接，相邻叶子节点的数据在逻辑上是连续的（根据主键值排序），但是物理上可能并不连续

image.png
在InnoDB中，需要注意聚簇索引的几个地方：

  • 聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一且非空的列代替。如果没有这样的索引，InnoDB 会隐式定义一个主键rowId（类似oracle中的RowId）来作为聚簇索引。
  • 当使用主键为聚簇索引时，主键最好不要使用uuid，因为uuid的值太过离散，不适合排序且可能出现新增加记录的uuid，会插入在索引树中间的位置，导致索引树调整复杂度变大，消耗更多的时间和资源。
  • 建议使用int或bigint类型的自增主键，方便排序并且默认会在索引树的末尾增加主键值，对索引树的结构影响最小。而且，主键值占用的存储空间越大，辅助索引中保存的主键值也会跟着变大，占用存储空间，也会影响到IO操作读取到的数据量。

关于上面的第二点，为什么要使用自增的主键，其原因如下：
结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少了页的分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：
image.png
这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。

但是，如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：
image.png

图示插入连续的数据：
索引的实现 - 图11
图示插入非连续的数据：
索引的实现 - 图12

非聚簇索引

非聚簇索引也称辅助索引或二级索引，辅助索引的叶子结点索引和数据是分来的，非聚簇索引的B+树的叶子结点存放的不是表的行记录，而是聚簇索引B+树中的索引，一张表页允许具有多个非聚簇索引。因为InnoDB的非聚簇索引叶子存储的是主键值，因此根据非聚簇索引检索数据需要二次查找（也称回表），即先通过非聚簇索引找到主键，然后通过聚簇索引找到该主键对应的行记录。
image.png

注意： 当根据辅助索引查询到聚簇索引的key值后，再去聚簇索引中查询所有行数据，称之为回表。如下图所示： 索引的实现 - 图14 回表的效率会稍微低一点，因此可以尽量索引覆盖。所谓的索引覆盖就是当sql语句的所求查询字段（select列）和查询条件字段（where子句）全都包含在一个索引中，可以直接使用索引查询而不需要回表，就是索引覆盖。 索引是高效找到行的一个方法，当能通过检索索引就可以读取想要的数据，那就不需要再到数据表中读取行了。

这里稍微说一下InndoDB和MyISAM二者对主键索引、辅助索引实现的不同方式。假设Id作为聚簇索引，Name作为辅助索引，下图展示了二者的区别：
image.png
可以看到，MyISAM无论是主键索引还是辅助索引，都是非聚簇索引，即索引和数据分开存储，因此MyISAM的辅助索引检索数据并不需要进行回表操作。

思考： InnoDB中为什么非聚簇索引为什么存储主键值，不存储磁盘地址？ 因为增、删的时候，如果地址发生变化，则我们要对辅助索引也进行维护，如果存储的是主键值，可以不用维护。