数据库 索引部分 以MySql为例

什么是索引？

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

索引是一种数据结构。数据库索引，是对数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。

索引的实现通常使用B树以及变种B+树

索引相当于目录。为了方便查找书中的内容，通过对内容建立索引形成目录。索引是一个文件，它是要占据物理空间的。

索引有哪些优缺点？

索引的优点

• 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
• 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点

• 时间方面：创建索引和维护索引要耗费时间，具体地，党对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率
• 空间方面：索引需要占物理空间

索引使用场景（重点）

where
select * from innodbl where id<20
id 查询记录，因为id字段进建立了主键索引，因此此SQL执行可选的索引只有主键索引，如果有多个，最终会选一个较优的作为检索的依据。

# 建立索引
alter table 表名 add index（字段名）；

order by
当我们使用order by将查询结果按照某个字段排序时，如果该字段没有建立索引，那么执行计划会将查询出的所有数据使用外部排序（将数据从硬盘分批读取到内存使用内部排序，最后合并排序结果），这个操作是很影响性能的，因为需要将查询涉及到的所有数据从磁盘终读到内存。
但是如果我们对该字段建立索引 alter table 表名 add index（字段名），那么由于索引本身是有序的，因此直接按照索引的顺序和映射关系逐条去除数据即可。而且如果分页的，那么只用取出索引表莫格范围内的索引对应的数据，而不用像上述那取出所有数据进行排序在返回莫格范围内的数据。（从磁盘取数据是最影响性能的）

join
对join语句匹配关系 on涉及的字段建立索引能够提高效率

索引覆盖

如果要查询的字段都建立过索引，那么引擎会直接在索引表中查询而不会访问原始数据（否则只要有一个字段没有建立索引就会做全表扫描），这叫索引覆盖。因此我们需要尽可能的在select后只写必要的查询字段，以增加索引覆盖的几率

注意：不要想为每个字段建立索引，因为优先使用索引的优势就在于其体积小

索引有哪几种类型？

主键索引：数据列不允许重复，不允许为NULL,一个表只能有一个主键。
唯一索引：数据列不允许重复，允许为NULL值，一个表允许多个列创建唯一索引。

• 可以通过 ALTER TABLE 表名 ADD UNIQUE column；创建唯一索引
• 可以通过 ALTER TABLE 表名 ADD UNIQUE column1,column2;创建唯一组合索引
  普通索引：基本的索引类型，没有唯一性的限制，允许为NULL值
• 可以通过 ALTER TABLE 表名 ADD INDEX 索引名 （column）；创建普通索引
• 可以通过 ALTER TABLE 表名 ADD INDEX 索引名 （column1，column2，column3）；创建组合索引
  全文索引： 是目前搜索引擎使用的一种关键技术
• 可以通过 ALTER TABLE 表名 ADD FULLTEXT （column）；创建全文索引

索引的数据结构（B树，HASH）

索引的数据结构和具体存储引擎的实现有关。在MySQL中使用较多的索引有Hash索引，B+索引等，而我们经常使用的InnoDB存储引擎的默认索引实现为：B+树索引。对于哈希索引来说，底层的数据结构就是哈希表，因此在绝大多数需求为单挑记录查询的时候，可以选择哈希索引，查询性能最快，其余大部分场景，建议选择BTree索引

B树索引

MySQL 通过存储引擎取数据，InnoDB ，按照实现方式 InnoDB的索引类型目前只有两种：BTREE B树索引 和 HASH索引。B树索引是MySQL数据库中使用最频繁的索引类型，基本所有存储都支持BTree索引，通常我们说的索引不出意外指的就是B树索引 B+树实现的

查询方式：

主键索引区：按主键查询

普通索引区：关联的id的地址，然后在到达上面的地址。按住键查询，速度快

B+tree性质：

1. n课子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。
2. 所有的叶子节点中包含了全部关键字信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
3. 所有的非终端节点可以看成时索引部分，节点中仅含其子树中的最大关键字。
4. B+树种，数据对象的插入和删除仅在叶节点上进行。
5. B+树有两个头指针，一个时树的根节点，一个是最小关键码的叶节点。

哈希索引

简单说下，类似于数据结构中简单实现的HASH表一样，当我们在mysql中使用哈希索引使，主要就是通过Hash算法，将数据库字段数据转换成定长的Hash值，与这条数据的行指针一并存入Hash表中对应位置；如果发生Hash碰撞，则对应Hash建下以链表形式存储。

B树和B+树的区别

• B树种，你剋将键和值存放在内部节点和叶子节点；但在B+树种，内部节点都是键，没有值，叶子节点同时存放键和值。

• B+树的叶子节点有一条链项链，而B树的叶子节点各自独立

  

  使用B树的好处

  B树可以在内部节点同时存储键和值，因此，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率，这种特性使得B树在特定数据重复多次查询的场景中更加高效

  使用B+树的好处

  由于B+树的内部节点只存放键，不存放值。因此，一次读取，可以在内存页中获取更多的键，有利于更加快速缩小查找范围。B+树的叶子节点由一条链相连，因此，当需要进行一次全部遍历的时候，B+树只需要使用O（logN）时间找到最小的节点，然后通过链进行O（N）的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会更需要更多的内存置换次数，消耗时间。

  Hash索引和B+树所有有什么区别或者说优劣呢？

  首先要知道Hash索引和B+索引的底层实现原理：

  hash索引底层就是hash表，进行查找时，调用一次hash函数就可以获取到相应的键值，之后进行回表查询获得实际数据。B+树底层实现是多路平衡查找树。对于每一次的查找都是从根节点出发，查找到叶子节点方可以获得所查键值，然后根据查询判断是否需要回表查询数据。

  • hash索引进行等职查询更快，但却无法进行范围查询。

    因为hash索引中经过hash函数建立索引之后，索引的顺序与原顺序无法保持一致，不能支持范围查询，而B+树的所有节点皆遵循（左节点小于父节点，右节点大于父节点，多叉树也类似）。

  • hash索引不支持使用索引进行排序，原理同上。

  • hash索引不支持模糊查询以及多列索引的最左前缀匹配。因为相互之间索引没有相关性

  • hash索引任何时候都避免不了回表查询数据，而B+树在符合某些条件（聚簇索引，覆盖索引等）的时候可以只通过索引完成查询。

  • hash索引虽然在等值查询上较快，但是不稳定，性能不可预测，当莫格键值存在大量重读的时候，发生hash碰撞。而B+树的查询效率比较稳定。

    因此大多数情况下，直接选择B+树索引可以获得稳定且较好的查询速度。而不需要Hash索引。

数据库为什么使用B+树而不是B树

• B树知识和随机检索，而B+树同时支持随机检索和顺序检索；

• B+树空间利用率高，可减少I/O次数，磁盘读写代价更低。一般来说，索引本身也很大，不可能存储在内存中，因此索引往往可以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗。B+树的内部节点并没有指向关键字具体信息的指针，知识作为索引使用，其内部节点比B树小，盘块能容纳的节点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素

• B+树的查询效率更加稳定。B树搜索有可能会在非叶子节点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找，而B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从个节点到叶节点的路。所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。

• B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下问题。B+树的叶子节点使用指针顺序链接在一起，只要遍历叶子节点就可以实现整颗树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作

• 增删文件时，效率更高。因为B+树的叶子节点会包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。

什么时聚簇索引？何时使用聚簇索引与非聚簇索引

• 聚簇索引：将数据存储与索引放到一块，找到索引也就找到了数据。一般情况下，一张表只允许存在一个聚簇索引。
  聚簇索引，实际存储的循序结构与数据存储的物理机构是一致的，所以通常来说物理顺序结构只有一种，那么一个表的聚簇索引也只能有一个，通常默认都是主键，设置了主键，系统默认就为你加上了聚簇索引，当然有人说我不想拿主键作为聚簇索引，我需要用其他字段作为索引，当然这也是可以的，这就需要你在设置主键之前自己手动的先添加上唯一的聚簇索引，然后再设置主键，这样就木有问题啦。
• 非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向数据的对应行，非聚簇索引的物理顺序与逻辑顺序没有必然的联系，与数据的存储物理结构没有关系，一个表对应的非聚簇索引可以又很多。

索引的基本原理

索引用来快速的查找哪些特定的记录，如果没有索引，一般来说执行查询时遍历整张表
索引的原理很简单，就是把无序的数据变为有序的查询

1. 建立索引的列内容进行排序
2. 对排序结果生成倒排表
3. 在倒排表内容上拼上数据地址链接
4. 在查询的时候，先拿出倒排表内容，在取出数据地址链，从而拿到具体数据

索引的算法有哪些？

索引算法 BTree BTree+ Hash算法
BTree树是InnoDB引擎默认的索引算法，因为它可以被用在比较运算符和brtween操作符上，而且可以用like操作符，只要它的查询条件是一个不以通配符开头的常量

Hash算法
Hash算法 Hash索引只能用于对等比较，例如=，<=,>=操作符。由于是一次定位数据，不想BTree索引需要根节点到枝节点，最后才能访问到叶节点这样多次IO操作，所以检索效率远高于BTree索引。

索引设计的原则？

1. 适合索引的列是出现在where字句中的列，或者链接自子句中的指定的列
2. 基数较小的类，索引效果较差，没有必要在此列建立索引
3. 使用短索引，如果对长字符串进行索引，应该指定一个前缀长度，这样能够节省大量索引空间
4. 不要过度索引。索引需要额外的磁盘空间，并且降低写操作的性能。在修改表内容的时候，索引会进行个更新甚至重构，索引列越多，这个时间越常，所以只保持需要的索引有利于查询即可。

最左前缀原则

实例 ：现在我们想查出满足以下条件的用户id：
SELECT uid FROM people WHERE Iname =‘liu’ AND fname=‘zhiqun’ AND age=26;
因为不想扫描整表，故考虑使用索引

单列索引：
ALTER TABLE people ADD INDES Iname(Iname);
将Iname列建索引，这样就把范围限制在Iname=‘liu’的结果集上，之后在扫描满足 fname=‘zhiqun’的结果集，在扫描age=26的结果集，即最终结果。

由于建立了Iname列的索引，与执行表的完全扫描相比，效率提高了很多，但我们要求扫描的记录数量仍就远超了实际所需要的。虽然我们可以删除Iname列上的索引，在创建fname或者age列的索引，但是无论哪个列，索引效率仍然相似。

多列索引：
ALTER TABLE people ADD INDEX Iname_fname_age(Iame,fname,age);
为了提高搜索效率，我们需要考虑运用多列索引，由于索引文件以BTree格式保存，所以我们不用扫描任何记录，即可得到最终结果。
注：在mysql中执行查询时，只能使用一个索引，如果我们在Iname，fname，age上分别建索引，执行查询时，只能使用一个索引，mysql会选择一个最严格（获得结果集最少）的索引

最左前缀：最左优先，上列我们在Iname_fname_age多列索引，相当于创建了（Iname）单列索引，（Iname，fname）组合索引以及（Iname，fname，age）组合索引。

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

创建索引的原则

1. 最左前缀：最左优先 将使用最频繁的放在最左边
2. 较频繁作为查询条件的字段才去创建索引
3. 更新频繁字段不适合创建索引
4. 若是不能有效区分数据的列不适合左索引（如性别，男女未知，最多三种，区分度低）
5. 尽量的扩展索引，不要新建索引。比如表中有a索引 再在要加（a，b）索引，那么只需要修改原来的索引即可。
6. 定义有外键的数据列一定要建立索引。
7. 对于哪些查询中很少涉及的列，重复值比较多的列不要建立索引。
8. 对于定义为text、image和bit的数据类型的列不要建立索引。

创建索引的三种方式，删除索引

第一种 在执行CREAT TABLE时创建索引
主键索引 唯一索引

CREAT TABLE user(id INT auto_increment PRIMARY KRY,first_name Varchar(16),last_name VARCHAR(16);id_card VARCHAR(18),information text,KEY name (first_name,last_name),FULLTEXT KEY (information),UNIQUE KEY (id_card))

第二种方式：使用ALTER TABLE 命令去增加索引

ALTER TABLE table_name ADD INDEX index_name(column_list);

ALTER TABLE 用来创建普通索引、UNIQUE 索引 或PRIMARY索引。
其中table_name 是要增加索引的表名，column_list指出对哪些列进行索引，多列时各列之间用逗号分隔。
索引名index_name可以自己命名，缺省时，MySQL将根据第一个索引列赋一个名称。另外，ALTER TABLE 允许在单个语句中更改多个表，因此可以在同时创建多个索引。

第三种方式： 使用CREATE INDEX命令创建

CREATE INDEX index_name ON table_name(column_list);

CREATE INDEX 可以对表增加普通索引或UNIQUE 索引。但是不能创建PRIMARY KEY索引。

删除索引
根据索引名删除普通索引、唯一索引、全文索引：alter table 表名 drop KEY 索引名
alter table user_index drop KEY name；
删除主键索引
因为主键只有一个。如果主键自增长，那么不能直接执行此操作（自增长依赖于主键索引）
alter table 表名 deop primary key；

取消自增长 在删除
alter table user_index
MODIFY id int,
drop PRIMARY KEY

创建索引需要注意什么？

• 非空字段，应该指定列为NOT NULL,除非你想存储NULL.在mysql中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算符复杂。应该使用0、一个特殊的值或者一个空船代替空值；
• 取值离散大的字段：变量各个取值之间的差异程度 的列放到联合索引的前面，可以通过count（）函数查看字段的差异值，返回值越大说明字段的唯一值越多字段的离散程度高。
• 索引字段越小越好：数据库的数据存储以页为单位，一页存储的数据越多一次IO操作获取的数据越大，效率越高。（id 一般为int 并且作为主键索引 就是这个原因）

使用索引查询一定能提高查询的性能吗?为什么

通常，通过索引查询数据比全表扫描要快。但需要损失空间存储，也需要定期维护。

• 索引需要空间来存储，也需要定期维护，每当有记录在表中增减或索引列被修改时，索引本身也会被修改。这意味着每条记录的INSERT,DELETE,UPDATE将为此多付出4，5次的磁盘II/O。因为索引需要额外的存储空间和处理，哪些不必要的索引反而会使查询反应时间变慢。使用索引查询不一定能提高查询性能，索引范围查询（INDEXRANGE SCAN)适用于两种情况：
• 基于一个范围的检索，一般查询返回结果集小于表中记录数的30%
• 基于非唯一性索引的检索

百万级别或以上的数据如何删除

关于索引：由于索引需要额外的维护成本，因为索引文件是单独存在的文件，所以当我们对数据的增加，修改，删除，都会产生额外的对索引文件的操作，这些操作需要消耗额外的IO，会降低增/改/删的执行效率。所以，在我们删除数据库白外级别数据的时候，查询MySQL官方手册得知删除数据的速度和创建的索引数量是成正比的。

1. 所以我们想要删除百万数据的时候，可以先删除索引
2. 然后删除无用数据
3. 删除完成后重新创建索引
4. 与之前的直接删除绝对是要快速很多，更别说万一删除中断，一切删除会回滚。

前缀索引

语法：index（filed（10）），使用字段值的前10哥字符建立索引，默认是使用字段的全部内容建立索引
前提：前缀的标识度高，比如密码就是和建立前缀索引，以内密码几乎各不相同
注意：前缀截取的长度
我们可以利用select count（*）/count（distinct left（password，prefixLen））；，通过从调整prefixLen的值（从1自增）查看不同前缀长度的一个平均匹配度，接近1时就可以了。