第一章、按数据结构分类

数据结构是计算机存储、组织数据的方式。根据数据结构分类主要可以分为B树结构，Hash结构等

1.1）树型数据结构索引

二叉树
接下来我将通过最简单的树形结构二叉树引出一些诸如根节点，节点，树，B树之类的概念。
二叉树（Binary tree）如图：树形结构，许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
①节点：包含一个数据元素及若干指向子树分支的信息
②节点的度：一个节点拥有子树的数目称为节点的度
③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点
④分支节点：也称为非终端节点，度不为零的节点称为非终端节点
⑤树的度：树中所有节点的度的最大值
⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层
⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成

B树
索引会用到更复杂的树形数据结构如B-tree：
1、B-tree也就是B树允许每个节点有更多的子节点，树的节点增多后树的层级比原来的二叉树少了，且能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。

2、 B 树应用到数据库中的时候，充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为 4K，每次 I/O 进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制在磁盘块大小范围。

B树查找数据过程
一个节点上存有主键关键字和多个指针p，指针存储的是子节点所在磁盘块的地址。
模拟查找关键字29的过程：
1、根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2、比较关键字29在区间（17,35），找到指针P2。
3、根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4、比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5、根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6、在磁盘块8中的关键字列表中找到关键字29。
7、分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。

注意：B树的非叶子节点也存储数据，每个节点中有key，也有data。而B+树只在叶子节点存储数据
而每个节点的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

B+ 树
B+ 树是B 树的升级版，InnoDB存储引擎就是用B+Tree实现MySQL索引结构。 存储引擎就是数据库底层软件组件, 数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。

1、B+树在叶子节点存储key和数据，非叶子节点只存储key不存储数据所以非叶子节点可以包含更多的节点，这样做可以降低树的高度。还能将数据范围变为多个区间，区间越多，数据检索越快。以 InnoDB 的一个整数字段索引为例，每个节点大概有 1200各分叉。当树高为 4 时，大概可以存储17亿条数据【1200^3 ≈ 17亿】。考虑到树根的数据块总是在内存中的，从17亿条数据中查找一个值，最多只用访问3次磁盘；而树的第二层也有很大概率在内存中，那么访问磁盘的平均次数会更少。

2、B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等
B+树更适合外部存储（存储磁盘数据）。由于内节点无data域，每个节点能索引的范围更大更精确。

3、B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。B+树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

4、B+ 树叶子节点的关键字从小到大有序排列，所有节点关键字是按递增次序排列，并遵循左小右大原则；就是说如果有重复元素，父节点 20，子节点 20，那么子节点应当位于右侧，即：子节点＜父节点≤右子节点

5、B+树所有的叶子节点数据构成了一个有序链表，左边结尾数据都会保存右边节点开始数据的指针。这个特性在范围查找（区间访问）时非常有用，数据紧密性很高，缓存的命中率也会比 B 树高。。

1.2）Hash数据结构索引

1、Hash表是一种key-value的存储结构，通过key计算出下标，然后将value添加到该下标对应的链表中去。哈希表这种结构适用于只有等值查询的场景（比如 Memcached 及其他一些 NoSQL 引擎），不适合区间查询，另外 Hash 表还存在 Hash 函数选择和 Hash 值冲突等问题。

2、哈希索引是一种基于哈希表实现的索引，它支持全值匹配，但不支持范围查询和前缀匹配。在MySQL中，哈希索引主要应用于MEMORY存储引擎。也是 Memory 引擎表的默认索引类型，Memory 引擎同时也支持 B-Tree 索引。

3、哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。

4、哈希索引不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。

5、哈希索引只支持等值比较查询，包括 =、IN()、<=>；不支持任何范围查询，例如 WHERE price>100。

6、访问哈希索引的数据非常快，除非有很多哈希冲突(不同的索引列值却有相同的哈希值)。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。

7、如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

注意事项：基于 Hash 索引的表还是能够支持范围查找，只不过其通过遍历实现，不能利用索引进行查询优化。

1.3） 其他数据结构索引

LSM树【Log-Structured Merge-Trees】
在B+树中，每次有数据写入时，可能要插入到不同的节点，即写入不同的数据块。大量的磁盘随机写操作会影响写入速度。因此B+树不适合写入量大的场景。针对这个问题，HBase引入了LSM树的概念，将随机写转变为顺序写，大幅提升了写入速度。和B+树相比，LSM牺牲了部分读性能，用来大幅提高写性能。目前HBase/LevelDB/RocksDB/ClickHouse这些NoSQL存储都是采用的LSM树。
LSM树的结构是横跨内存和磁盘的，包含memtable、immutable memtable、SSTable等多个部分。

第二章、按物理存储方式分类

根据物理存储分类可以分为聚簇索引（聚集索引）和非聚簇索引（非聚集索引）
聚集索引（InnoDB引擎）
主键索引属于聚簇索引的叶子节点会存储指针的值和数据行，也就是说数据和索引是在一起，这就是聚簇索引，InnoDB中也只有主键索引才能是聚簇索引。

非聚集索引（MyISAM引擎）
二级索引（辅助索引）属于非聚簇索引，叶子节点只会存储数据行的指针，简单来说数据和索引不在一起，就是非聚聚簇索引；

注意：主键索引和二级索引都会存储指针的值。

2.1）聚簇索引（聚集索引）

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式，InnoDB引擎使用的是聚簇索引，MySQL 的主键索引默认就使用到了聚簇索引。
1、MySQL 自动为主键字段创建一个索引（PRIMARY），按照每张表的主键构造一颗B+树，同时叶子节点中存放有行数据，所以说主键索引默认就使用到了聚簇索引。如果没有主键则选择非空唯一的索引作为聚簇索引，都没有则隐式创建一个索引作为聚簇索引

2、当表有聚簇索引时，它的数据行实际上存放在索引的叶子页(leaf page)中。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引，如果已经设置了主键为聚簇索引又希望再单独设置聚簇索引，必须先删除主键，然后添加我们想要的聚簇索引，最后恢复设置主键即可。

主键索引查询:
3、实际上索引顺序与物理存储顺序一致。因此，通过主键进行查找时的性能最好。InnoDB引擎使用的是聚簇索引，将主键组织到一棵B+树中，主键被作为聚簇索引，而行数据就储存在叶子节点上，id为主键我们使用“where id = 14”这样的条件查找数据，则按照B+树的检索算法即可查找到对应的叶节点，可以直接通过主键定位到数据并返回。

2.2）非聚簇索引（非聚集索引）

非聚簇索引也只是一种存储方式，MyIsam使用的是非聚簇索引，以 MyISAM 存储引擎存储的表不存在聚簇索引。二级索引(又称辅助索引)就属于非聚簇索引

1、当我们自己通过：CREATE INDEX语句或者相应的ALTER TABLE ADD INDEX语句创建其他索引就是二级索引，索引顺序与物理存储顺序不一致，二级索引包括普通索引，唯一索引，前缀索引等
二级索引属于非聚簇索引，但是我们不能说非聚簇索引就是二级索引，你可以说狗是动物，但是动物是狗就不对。

2、二级索引出现的原因：很多业务场景中，我们需要根据非主键列进行数据的检索，此时又不能一行一行全表查一遍，因为这样性能极差！
因此数据库的研发者想出了一种办法：多建立几棵B+树，其中只有一颗B+树是用主键索引建立的，这颗树的叶子节点包含了主键索引和完整的数据记录。其他B+树使用二级索引建立的叶子节点存放的是对应的非主键列+主键值，没有存储数据行

辅助(二级)索引查询：回表的概念
3、辅助索引中除了包含了索引对应字段值还有主键值，当我们不通过主键来搜索而通过二级索引搜索时，则需要两个步骤：
第一步在辅助索引B+树中检索Name（二级索引列），到达其叶子节点获取对应的主键。
第二步：二级索引在查询需要多扫描一棵索引树，也就是回表，使用主键在主索引B+树中再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。

通过覆盖索引避免回表
4、查询的字段中既有索引字段,又有非索引字段就会发生回表。那么把非索引字段建立索引，使你查的所有字段都是索引字段（即索引字段覆盖了需要查的字段，这就是覆盖索引）

比如当前的二级索引字段只有name

# 索引中只有name，但是却查询了所有字段，此时就会回表再通过主键获取其他字段的值
select * from table where name = 'a';   

不是所有类型的索引都可以成为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以 MySQL 只能使用 B-Tree 索引做覆盖索引。另外，不同的存储引擎实现覆盖索引的方式也不同，而且不是所有的引擎都支持覆盖索引。

通过索引下推(ICP)减少回表
5、索引下推简称ICP，在Mysql5.6的版本上推出，用于优化查询
在使用ICP的情况下，如果存在某些被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器 。
索引下推默认是开启的，关闭可以使用下面的语句

set optimizer_switch='index_condition_pushdown=off';索引下推使用条件：
1、只能用于range、 ref、 eq_ref、ref_or_null访问方法；
2、只能用于InnoDB和 MyISAM存储引擎及其分区表；
3、对InnoDB存储引擎来说，索引下推只适用于二级索引（非主键索引）;
4、引用了子查询的条件不能下推；
5、引用了存储函数的条件不能下推，因为存储引擎无法调用存储函数。

具体可以看这篇：Mysql性能优化：什么是索引下推？

不同存储引擎下的非聚簇索引实现有所不同：
MyISAM
1、MyISAM 存储引擎存储的表不存在聚簇索引，MyISAM 的非聚簇索引实现的叶子节点仍然是索引节点，MyISAM中无论是主键索引还是二级索引，叶子节点存放的都是主键和指向对应数据块的指针，叶子节点是不存储表数据的。保证可以通过索引查找到对应的数据行，只需要对索引进行一遍查找。但这样会存在页分裂问题。

2、在MyISAM 中，一个数据表table的存储文件，它是由table.frm、table.myd以及table.myi组成。table.myd记录了数据（数据行），table.myi记录了索引的数据。MyISAM 引擎的索引文件和数据文件是独立分开的，正好符合非聚簇索引的架构。

innodb
innodb的非聚簇索引实现，叶子节点存储的是主键值（不是主键地址）通过主键值，去聚簇索引进行索引操作，找到叶子节点，数据在该叶子节点上，这个就是前面说的回表。
InnoDB 的策略好处是：当出现行移动或者数据页分裂时二级索引的维护工作，不需要维护变动的指针；坏处是：使用主键值当作指针会让二级索引占用更多的空间。

第三章、按索引字段的特性分类

3.1）普通索引

MySQL中最基本的索引类型，没有任何限制，允许定义索引的列中插入重复值和空值

create index index_name on `TableName`(name(10))

alter table table_name add index index_name ( `column` )

3.2）唯一索引

UNIQUE 表示唯一索引，与普通索引类似，用于实现唯一约束；索引列中的值必须是唯一的，但是允许空值；如果是组合索引，则列值的组合必须唯一，创建方法和普通索引类似。

CREATE UNIQUE INDEX indexName ON tableName(columnName(columnLength))

alter table table_name add unique (`column`)

3.3）主键索引

主键和索引的关系
（1）主键索引是创建主键的时候系统自动创建的索引，
（2）主键要求不重复，不为空
（3）主键属于索引，是索引的一种
主键索引属于聚簇索引，但是我们不能说聚簇索引就是主键索引，聚簇索引会将索引和数据保存在同一个 B-Tree 中，所以通过主键索引可以直接查到需要查找的数据，
通过非聚集索引可以查到记录对应的主键值 ， 再使用主键的值通过聚集索引查找到需要的数据。因此从主键索引中获取数据通常比在二级中查找要快。

alter table table_name add primary key ( `column` )

3.4）多列索引（又称组合索引，复合索引，多字段索引，联合索引）

这里就不细说了在后文2.4.3会细说
在表中的多个字段组合上创建的索引，遵循最左前缀原则。
最左前缀原则：使用组合索引时在查询条件中使用了这些字段的左边字段时，索引才会被使用。
注意事项：在一次查询中，MySQL 只能使用一个索引。多列索引也被看作一个索引。

 create index index_name on `table_name`(`column1`, `column2`, `column3` ) 

alter table `table_name` add index index_name ( `column1`, `column2`, `column3` )

3.5）前缀索引，后缀索引

MySQL 允许基于 CHAR、VARCHAR、BINARY 以及 VARBINARY 字段的最前面一部分内容创建索引，同时对于 BLOB 和 TEXT 字段必须指定索引使用的字段长度。这一特性被称为前缀索引（prefix index）。
前缀索引是指对字符类型字段的前几个字符或对二进制类型字段的前几个 bytes 建立的索引，而不是在整个字段上建索引。
例如，可以对 persons 表中的 name(varchar(16))字段 中 name 的前 5 个字符建立索引。

 create index index_name on persons (name(5)) comment '前缀索引';

前缀索引是一种能使索引更小、更快的有效办法，但另一方面也有其缺点：MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY，也无法使用前缀索引做覆盖扫描。

后缀索引(suffix index)也有其用途( 例如，找到某个域名的所有电子邮件地址)。MySQL 原生并不支持反向索引，但是可以把字符串反转后存储，并基于此建立前缀索引。可以通过触发器来维护这种索引。

3.6）全文索引（FULLTEXT）

全文索引是一种用于文本数据模糊查询的特殊索引，它基于倒排索引实现。在MySQL中，全文索引主要应用于MyISAM和InnoDB存储引擎。全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。
只能在char、varchar、text 类型字段上才能使用。
对于大容量的数据表，生成全文索引是一个非常消耗时间非常消耗硬盘空间的做法。

CREATE FULLTEXT INDEX indexName ON tableName(columnName(columnLength))

alter table table_name add fulltext (`column` )

第四章、按索引的字段个数分类

4.1）单列索引

建立在单个列上的索引为单列索引，单列索引有：普通索引，唯一索引，主键索引

注意：多个单列索引与单个多列索引的查询效率不同，因为执行查询时，MySQL只能使用一个索引，会从多个索引中选择一个限制最为严格的索引。
测试具体的效率呢？

两种不同的建立索引方式：case 1：对c1,c2,c3三列按此顺序添加一个多列索引；case 2： 对c1,c2,c3分别建立三个单列索引；问题1：按c1搜索时，哪种索引效率快？答：单列索引case2快问题2：按C2搜索时，哪种索引效率快？答：单列索引case2快，并且，case1的索引无效问题3：按C1，C2搜索时哪种效率快？答：不知道问题4：按C1,C2,C3搜索哪种效率快？答：多列索引case1快问题5：按C2,C3,C1搜索时哪种效率快？答：单列索引case2快， 因为没有按“最左前缀” 规则实现

给三个列加上索引，不管是单列索引还是组合索引，查询时间都是相差不大。
但是如果组合索引没有按照 “最左前缀” 规则实现，查询时间会比单列索引时间要长。

4.2）重复索引

重复索引是指在相同的列上按照相同的顺序创建了相同类型的索引。应该避免这样创建重复索引，发现以后也应该立即移除

CREATE TABLE test(ID INT NOT NULL PRIMARY KEY,A INT NOT NULL,B INT NOT NULL,UNIQUE(ID),INDEX(ID)
)ENGINE = InnoDB;

一个经验不足的用户可能是想创建一个主键，先加上唯一限制，然后再加上索引以供查询使用。事实上，MySQL 的唯一限制和主键限制都是通过索引实现的，因此，上面的写法实际上在相同的列上创建了三个重复的索引。通常并没有理由这样做，除非是在同一列上创建不同类型的索引来满足不同的查询需求。

4.3）多列索引（又称组合索引，复合索引，多字段索引，联合索引）

多列索引介绍
多列索引：一个索引包含多个列，一个联合索引是一个有序元组<a1, a2, …, an>，其中各个元素均为数据表的一列，多列索引最多可以16列。
平时用的SQL查询语句一般都有多个的限制条件，如果一个表中的数据在查询时有多个字段总是同时出现则这些字段就可以作为复合索引，形成索引覆盖可以提高查询的效率。

建立多列索引
①MySQL组合索引“最左前缀”简单的理解就是只从最左面的开始组合。
演示建立一个普通多列索引：索引从左到右顺序为title,time,age

ALTER TABLE table_name ADD INDEX index_title_time_age (title(50),time(10),age(5))。
建立这样的组合索引，其实是相当于从左边开始组合分别建立了下面几个索引：
—title,time，age
–title,time
–title

②演示建表时设置多列索引

 create index index_id_name on table_name (id,name) comment '组合索引';

组合索引的非叶子节点保存了两个字段的值作为 B+tree 的 key 值，当 B+tree 上插入数据时，先按字段 id 比较，在 id 相同的情况下按 name 字段比较。
③多列唯一索引

ALTER TABLE table_name ADD unique index_name( userid, username );

④多列主键索引,主键一般都是自增长的ID，要先删除主键后再创建多列主键索引，不然会报错的，ERROR 1068 (42000): Multiple primary key defined；

ALTER TABLE table_name ADD primary key index_name( userid, username );

最左前缀原则
①最左前缀原则：使用组合索引时在查询条件中使用了这些字段的左边字段时，索引才会被使用。

比如建立了一个 (name,age,sex) 的联合索引：当 (张三,20,男)1 这样的数据来检索的时候，name是索引字段的最左边，所以会使用name来确定下一步的所搜方向，如果 name 相同再依次比较 age 和 sex，最后得到检索的数据；当 (20,男) 这样查询时没有使用name这个最左边的索引数据时，就不会使用索引。当 (张三,男) 这样的数据来检索时，先用 name 来指定搜索方向，但下一个字段 age 的缺失，所以只能把名字等于张三的数据通过索引都找到，后面的age索引无法使用，这个即索引的最左匹配特性。

②最左前缀匹配原则指的是 MySQL 会一直向右匹配直到遇到范围查询 (>、<、between、like) 就停止匹配，比如 a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d) 顺序的索引，d 是用不到索引的，如果建立(a,b,d,c) 的索引则都可以用到。

③当不需要考虑排序和分组时，将选择性最高的列放到索引最前列，这时候索引的作用只是用于优化 WHERE 条件的查找。但是有时可能需要根据那些运行频率最高的查询来调整索引列的顺序，让这种情况下索引的选择性最高。

4.4）冗余索引

冗余索引和重复索引有一些不同。如果创建了索引 (A, B)，再创建索引 (A) 就是冗余索引，因为这只是前一个索引的最左前缀列。因此索引 (A, B) 也可以当作索引 (A) 来使用(这种冗余只是对 B-Tree 索引来说的)。但是如果再创建索引 (B, A)，则不是冗余索引，索引 (B) 也不是，因为 B 不是索引 (A,B) 的最左前缀列。另外，其他不同类型的索引(例如哈希索引或者全文索引)也不会是 B-Tree 索引的冗余索引，而无论覆盖的索引列是什么。

冗余索引通常发生在为表添加新索引的时候。例如，有人可能会增加一个新的索引 (AB)而不是扩展已有的索引 (A)。还有一种情况是将一个索引扩展为 (A, ID)，其中 ID 是主键，对于 InnoDB 来说主键列已经包含在二级索引中了，所以这也是冗余的。

大多数情况下都不需要冗余索引，应该尽量扩展已有的索引而不是创建新索引。但也有时候出于性能方面的考虑需要冗余索引，因为扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询的性能。