Database -- 索引

Posted on May 13, 2020 By Guanzhou Song

什么是索引

索引的定义

索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。

更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。

在没有索引的情况下，数据库会遍历全部数据后选择符合条件的；

而有了相应的索引之后，数据库会直接在索引中查找符合条件的选项。

磁盘IO与B+树

执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

B树中每个节点包含了键值和键值对于的数据对象存放地址指针，所以成功搜索一个对象可以不用到达树的叶节点。

成功搜索包括节点内搜索和沿某一路径的搜索，成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

在B树中查找给定关键字的方法是：首先把根结点取来，在根结点所包含的关键字K1,…,kj查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；

否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的下一层索引节点块继续查找，直到找到，或指针Pi为空时查找失败。

浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示）

如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。

真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。

非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

  • 图上蓝色的块为关键字，我们发现所有的关键字最终都会被包含在叶子节点当中。

    • 图上的黄色区块表示的是子树的指针域，比如根节点下的P2指向的就是28-65之间的索引。

  • 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)

  • 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

查找数据 60 的 查找过程，如下所示:

  1. I/O第一次：读入5、28、65 数据块，在此同级别节点块上，60在28到65之间(其实是二分查找)，那走P2指针指向的子树。
  2. I/O第二次：读入28、35、56 数据块，在此同级别节点块上，60大于56，所以走P3指针指向的子树(上图中就是叶子节点)。
  3. I/O第三次：读入叶子节点，在这个叶子节点中，使用二分查找算法找到目标值60。

由上述查找过程所示统共需要三次I/O就能查到目标值，性能大大提升。

为什么需要索引

数据在磁盘上是以块的形式存储的。为确保对磁盘操作的原子性，访问数据的时候会一并访问所有数据块。

磁盘上的这些数据块与链表类似，即它们都包含一个数据段和一个指针，指针指向下一个节点（数据块）的内存地址，而且它们都不需要连续存储（即逻辑上相邻的数据块在物理上可以相隔很远）。

鉴于很多记录只能做到按一个字段排序，所以要查询某个未经排序的字段，就需要使用线性查找，即要访问N/2个数据块，其中N指的是一个表所涵盖的所有数据块。

如果该字段是非键字段（也就是说，不包含唯一值），那么就要搜索整个表空间，即要访问全部N个数据块。（在某些情况下，索引可以避免排序操作。）

然而，对于经过排序的字段，可以使用二分查找，因此只要访问log2 N个数据块。

同样，对于已经排过序的非键字段，只要找到更大的值，也就不用再搜索表中的其他数据块了。这样一来，性能就会有实质性的提升。

聚簇索引与非聚簇索引

InnoDB 主键使用的是聚簇索引，MyISAM 不管是主键索引，还是二级索引使用的都是非聚簇索引。

索引分为聚簇索引和非聚簇索引两种，聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了；

聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快。

  1. 对于非聚簇索引表来说（右图），表数据和索引是分成两部分存储的，主键索引和二级索引存储上没有任何区别。使用的是B +树作为索引的存储结构，所有的节点都是索引，叶子节点存储的是索引+索引对应的记录的地址。

  2. 对于聚簇索引表来说（左图），表数据是和主键一起存储的，主键索引的叶结点存储行数据(包含了主键值)，二级索引的叶结点存储行的主键值。使用的是B+树作为索引的存储结构，非叶子节点都是索引关键字，但非叶子节点中的关键字中不存储对应记录的具体内容或内容地址。叶子节点上的数据是主键与具体记录(数据内容)。

聚簇索引的优点

  1. 当你需要取出一定范围内的数据时，用聚簇索引也比用非聚簇索引好。

  2. 当通过聚簇索引查找目标数据时理论上比非聚簇索引要快，因为非聚簇索引定位到对应主键时还要多一次目标记录寻址,即多一次I/O。

  3. 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

  4. 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。

  5. 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

  6. 在使用分组和排序 子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

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

聚簇索引的缺点

  1. 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键。

  2. 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。

  3. 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。 二级索引的叶节点存储的是主键值，而不是行指针（非聚簇索引存储的是指针或者说是地址），这是为了减少当出现行移动或数据页分裂时二级索引的维护工作，但会让二级索引占用更多的空间。

  4. 采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多，因为插入要保证主键不能重复，判断主键不能重复，采用的方式在不同的索引下面会有很大的性能差距，聚簇索引遍历所有的叶子节点，非聚簇索引也判断所有的叶子节点，但是聚簇索引的叶子节点除了带有主键还有记录值，记录的大小往往比主键要大的多。这样就会导致聚簇索引在判定新记录携带的主键是否重复时进行昂贵的I/O代价。

关于聚集索引以及非聚集索引的几个问题：

一）聚集索引的约束是唯一性，是否要求字段也是唯一的呢？

一般我们指定一个表的主键，如果这个表之前没有聚集索引，同时建立主键时候没有强制指定使用非聚集索引，SQL会默认在此字段上创建一个聚集索引，而主键都是唯一的，所以理所当然的认为创建聚集索引的字段也需要唯一。

聚集索引可以创建在任何一列你想创建的字段上，这是从理论上讲，实际情况并不能随便指定，否则在性能上会是恶梦。 二）|主键就是聚集索引？？？ 这样有时会对聚集索引的一种浪费。Innodb将通过主键聚集数据，如果没有定义主键，Innodb会选择第一个非空的唯一索引代替，如果没有非空唯一索引，Innodb会隐式定义一个6字节的rowid主键来作为聚集索引。innodb只聚集在同一个页面中的记录，包含相邻键值的页面可能会相距甚远。 因为每个表中只能有一个聚集索引的规则，这使得聚集索引变得更加珍贵。 使用聚集索引的最大好处就是能够根据查询要求，迅速缩小查询范围，避免全表扫描。在实际应用中，因为 ID号是自动生成的，我们并不知道每条记录的ID号，所以我们很难在实践中用ID号来进行查询。这就使让ID号这个主键作为聚集索引成为一种资源浪费。其次，让每个ID号都不同的字段作为聚集索引也不符合“大数目的不同值情况下不应建立聚合索引”规则；当然，这种情况只是针对用户经常修改记录内容，特别是索引项的时候会负作用，但对于查询速度并没有影响。 三）是不是聚集索引就一定要比非聚集索引性能优呢？？？ 如果想查询学分在60-90之间的学生的学分以及姓名，在学分上创建聚集索引是否是最优的呢？ 答：否。既然只输出两列，我们可以在学分以及学生姓名上创建联合非聚集索引（也就是多列索引），此时的索引就形成了覆盖索引，即索引所存储的内容就是最终输出的数据，这种索引在比以学分为聚集索引做查询性能更好。 四）在数据库中通过什么描述聚集索引与非聚集索引的？ 索引是通过二叉树的形式进行描述的，我们可以这样区分聚集与非聚集索引的区别：聚集索引的叶节点就是最终的数据节点，而非聚集索引的叶节仍然是索引节点，但它有一个指向最终数据的指针。 五）在主键是创建聚集索引的表在数据插入上为什么比主键上创建非聚集索引表速度要慢？ 在有主键的表中插入数据行，由于有主键唯一性的约束，所以需要保证插入的数据没有重复。我们来比较下主键为聚集索引和非聚集索引的查找情况：聚集索引由于索引叶节点就是数据页，所以如果想检查主键的唯一性，需要遍历所有数据节点才行，但非聚集索引不同，由于非聚集索引上已经包含了主键值，所以查找主键唯一性，只需要遍历所有的索引页就行，这比遍历所有数据行减少了不少IO消耗。这就是为什么主键上创建非聚集索引比主键上创建聚集索引在插入数据时要快的真正原因。

索引分类

普通索引：

基本的索引，它没有任何限制。 创建方式： ```sql //标准语句： ALTER TABLE table_name ADD INDEX index_name (column_list) CREATE INDEX index_name ON table_name (column_list);  //还有建表的时候创建亦可 CREATE TABLE table_name (  ID INT NOT NULL,  column_listVARCHAR(16) NOT NULL, INDEX [index_name ]  (column_list(length))  );   ```

如果是CHAR，VARCHAR类型，length可以小于字段实际长度；如果是BLOB和TEXT类型，必须指定 length。 例子：假如length为10，也就是索引这个字段的记录的前10个字符。

唯一索引：

与前面的普通索引类似，不同的就是：MySQL数据库索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。

它有以下几种创建方式：

ALTER TABLE table_name ADD UNIQUE (column_list)
CREATE UNIQUE INDEX index_name ON table_name (column_list)
//还有建表时创建
CREATE TABLE table_name (
 ID INT NOT NULL, 
 column_list VARCHAR(16) NOT NULL, 
 UNIQUE [index_name ]  
 (column_list(length)) 
 );

主键索引：

它是一种特殊的唯一索引，不允许有空值。一般是在建表的时候同时创建主键索引：

CREATE TABLE table_name ( 
ID INT NOT NULL,
 [column] VARCHAR(16) NOT NULL,
 PRIMARY KEY(ID)  
 );

全文索引：（FULLTEXT）

定义：

全文检索是对大数据文本进行索引，在建立的索引中对要查找的单词进行进行搜索，定位哪些文本数据包括要搜索的单词。因此，全文检索的全部工作就是建立索引和在索引中搜索定位，所有的工作都是围绕这两个来进行的。

此索引关键：

建立全文索引中有两项非常重要，一个是如何对文本进行分词，一是建立索引的数据结构。分词的方法基本上是二元分词法、最大匹配法和统计方法。索引的数据结构基本上采用倒排索引的结构。分词的好坏关系到查询的准确程度和生成的索引的大小。

应用：

FULLTEXT索引仅可用于 MyISAM 表；他们可以从CHAR、VARCHAR或TEXT列中作为CREATE TABLE语句的一部分被创建，或是随后使用ALTER TABLE 或CREATE INDEX被添加。

但是要注意：

对于较大的数据集，将你的资料输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把资料输入现有FULLTEXT索引的速度更为快。

不过切记对于大容量的数据表，生成全文索引是一个非常消耗时间非常消耗硬盘空间的做法。因为！！插入修改删除表的同时也要针对索引做一系列的处理。

多列索引

多列索引（也叫组合索引）：

相关概念（适用多列索引的原因）：

MySQL能在多个列上创建索引。一个索引可以由最多15个列组成。（在CHAR和VARCHAR列上，你也可以使用列的前缀作为一个索引的部分)。

一个多重列索引可以认为是包含通过合并(concatenate)索引列值创建的值的一个排序数组。

多个单列索引与单个多列索引的查询效果不同，因为执行查询时，MySQL只能使用一个索引，会从多个单列索引中选择一个限制最为严格（获得结果集记录数最少）的索引。

当你为在一个WHERE子句索引的第一列指定已知的数量时，MySQL以这种方式使用多重列索引使得查询非常快速，即使你不为其他列指定值。

适用场景：

  1. 全字段匹配
  2. 匹配部分最左前缀
  3. 匹配第一列
  4. 匹配第一列范围查询(可用用like a%,但不能使用like %b)
  5. 精确匹配某一列和和范围匹配另外一列

例子：

//假设只使用单列索引名字
 ALTER TABLE people ADD INDEX name (name);
 //使用多列索引：
  ALTER TABLE people ADD INDEX height_name_age (height,name,age);
  //相当于创建了(height)单列索引，(height,name)组合索引以及(height,name,age)组合索引
/*
注意：
注：在mysql中执行查询时，只能使用一个索引，如果我们在name,age上分别建索引,执行查询时，只能使用一个索引，mysql会选择一个最严格(获得结果集记录数最少)的索引。
*/

在创建多列索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。

组合索引（多列索引）的原则：

最左前缀：顾名思义，就是最左优先

平时用的SQL查询语句一般都有比较多的限制条件，所以为了进一步榨取MySQL的效率，就要考虑建立组合索引（多列索引）。

例如上面使用的例子就相当于创建了(height)单列索引，(height,name)组合索引以及(height,name,age)组合索引。