索引是帮助数据库高效获取数据的数据结构。简而言之,索引是数据结构
哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。
为何能够通过 key 快速取出 value呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 value 对应的 index，找到了 index 也就找到了对应的 value。
但是！哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
为什么MySQL 没有使用其作为索引的数据结构呢？
- Hash 冲突问题 ：我们上面也提到过Hash 冲突了，不过对于数据库来说这还不算最大的缺点。
- Hash 索引不支持顺序和范围查询(Hash 索引不支持顺序和范围查询是它最大的缺点： hash索引中存储的就是Hash码，hash 码彼此之间是没有规律的，且 Hash 操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。
有很多树可以作为索引的数据结构，但mysql的InnoDB使用b+树
- B+ 树
单来说就是一种为磁盘或者其他存储设备而设计的一种平衡二叉树,在B+tree中所有记录都按照key的大小存放在叶子结点上，各叶子结点直接用指针连接 - 二叉搜索树
二叉搜索树的规则是父节点大于左孩子节点，小于右孩子节点 - 平衡二叉树
首先是一个二叉搜索树，但是要求任意一个节点的左右孩子节点的高度差不大于1 - B树
首先是一个平衡二叉树，但是又要求每个叶子节点到根节点的距离相等
那么B树和B+树的区别是什么呢？- B+树的叶子节点可以包含一个指针，指向另一个叶子节点
- B+树键值的拷贝存在非叶子节点；键值+记录存储在叶子节点
2.2.1 B 树& B+树
B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。
目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。
B 树& B+树两者有何异同呢？
- B 树的所有节点既存放键(key) 也存放 数据(data)，而B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
- B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
- B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
2.2.2 为什么要用b+树?
数据库存储的数据实际上是存在磁盘中的，之所以选择b+树也和这个有关。
2.2.2.1 磁盘
下面我们简单了解一下磁盘是如何工作的。
磁盘大概长这个样子：
磁盘主要由磁盘盘片、传动手臂、读写磁头和马达组成。
为了存储容量,主轴像穿糖葫芦一样把多个磁盘片组成一个阵列。通过马达驱动主轴转动以及传动手臂移动，使读写磁头在磁盘片上读写数据。大概如下：
磁盘片由很多半径不等的同心圆组成，这些圆被称为磁道，数据就是写在这些磁道上。
每个磁道又划分成块称为扇区。
如果磁盘是一记事本，那么一张磁盘片就是本子的一页纸，而主轴就是本子的装订线；磁道就是纸页的行，而扇区可以看作是很宽的列。
如果在磁盘中存储一首诗,想象中大概这个样子。
磁盘的读 I/O 操作,需要找到数据所在的磁盘片，以及对应的磁道和扇区。这些操作类似于从一本书中找到数据所在的页，行，列。
因为每个磁盘片都对应一个磁头，所以性能的关键就在于找行和列，即寻道和磁盘旋转。寻道即通过磁头找到数据所在的磁道，相当于换行到数据所在行。由于磁头只能水平移动，即只能换行寻道，无法在指定磁道上移动，因此需要磁盘高速旋转移动到指定扇区，类似写春联时，笔不动，纸动。
综上所述，磁盘的读写是通过机械运动来定位数据所在位置，而 cpu 是通过电信号进行数字运算。粗略的认为，机械查询数据，与光速处理数据的性能完全不是在一个量级，总之一句话就是磁盘处理太慢太慢了。
虽然磁盘处理数据太慢了，但是它是目前相对廉价且稳定的存储设备，所以又不能舍弃不用，但大致可以通过以下方法进行优化。
- 尽量减少 I/O 次数，比如可以使用缓存
- 每次 I/O 尽量获取更多的数据
- 每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数
2.2.2.2 为什么用b+树不是b树
上文为了解决磁盘处理数据太慢的问题，我们可以从：尽量减少 I/O 次数，比如可以使用缓存；每次 I/O 尽量获取更多的数据；每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数；这三点出发。可以发现b树很符合磁盘处理，它加载一次节点，可以加载很多路径数据，同时把查询范围缩减到更小。大大减少了 I/O 次数或者寻道次数。
但是b树仍然有一个致命的缺陷，那就是它的索引数据与业务绑定在一块，而业务数据的大小很有可能远远超过了索引数据，这会大大减小一次 I/O 有用数据的获取，间接的增加 I/O 次数去获取有用的索引数据。
因为业务数据才是我们查询最终的目的，但是它又是在「二分」查找中途过程无用的数据，因此，如果只把业务数据存储在最终查询到的那个节点是不是就可以了？这其实就是b+树。
B+ 树中，非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据。这样即保证了叶子节点的简约干净，数据量大大减小，又保证了最终能查到对应的业务数。既提高了单次 I/O 数据的有效性，又减少了 I/O 次数，还实现了业务。
2.2.3 不同引擎下B+树的区别
在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。（下面的内容整理自《Java 工程师修炼之道》）
MyISAM 引擎中，B+Tree 叶节点的 data 域存放的是数据记录的地址。在索引检索的时候，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”。
InnoDB 引擎中，其数据文件本身就是索引文件。相比 MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按 B+Tree 组织的一个索引结构，树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这被称为“聚簇索引（或聚集索引）”，而其余的索引都作为辅助索引，辅助索引的 data 域存储相应记录主键的值而不是地址，这也是和 MyISAM 不同的地方。在根据主索引搜索时，直接找到 key 所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，在走一遍主索引。 因此，在设计表的时候，不建议使用过长的字段作为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。
3.1.1 主键索引
数据表的主键列使用的就是主键索引。
一张数据表有只能有一个主键，并且主键不能为 null，不能重复。
在 MySQL 的 InnoDB 的表中，当没有显示的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。
3.1.2 二级索引(辅助索引)
二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。
唯一索引，普通索引，前缀索引等索引属于二级索引。
- 唯一索引(Unique Key) ：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL，一张表允许创建多个唯一索引。建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
- 普通索引(Index) ：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
- 前缀索引(Prefix) ：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小， 因为只取前几个字符。
- 全文索引(Full Text) ：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。
3.2.1 聚簇索引
聚簇索引即索引结构和数据一起存放的索引。主键索引属于聚簇索引。
如果表设置了主键，则主键就是聚簇索引
如果表没有主键，则会默认第一个NOT NULL，且唯一（UNIQUE）的列作为聚簇索引
以上都没有，则会默认创建一个隐藏的row_id作为聚簇索引
聚簇索引的优点
聚簇索引的查询速度非常的快，因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。
聚簇索引的缺点
- 依赖于有序的数据 ：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
- 更新代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚簇索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。
3.2.2 非聚簇索引
非聚簇索引即索引结构和数据分开存放的索引。二级索引属于非聚簇索引。
非聚簇索引的优点
更新代价比聚簇索引要小 。非聚簇索引的更新代价就没有聚簇索引那么大了，非聚簇索引的叶子节点是不存放数据的
非聚簇索引的缺点
跟聚簇索引一样，非聚簇索引也依赖于有序的数据
可能会二次查询(回表) :这应该是非聚簇索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。
如果还不清楚聚簇索引和非聚簇索引。看了下面回表和覆盖索引就知道了。
第一次先通过非聚簇索引搜索得到主键，然后再通过主键去搜索取得所需要的数据，进行了两次搜索所以叫回表。理解不了看一下下面的例子就知道了。
示例
建表
id 字段是主键索引，属于聚簇索引，age 字段是普通索引（二级索引）
填充数据
索引存储结构
id 是主键，所以是聚簇索引，其叶子节点存储的是对应行记录的数据
聚簇索引（ClusteredIndex）
聚簇索引即索引结构和数据一起存放的索引。对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。
普通索引（secondaryIndex）
age 是普通索引（二级索引），非聚簇索引，其叶子节点存储的是聚簇索引的的值
索引查找过程
聚簇索引查找过程
如果查询条件为主键（聚簇索引），则只需扫描一次B+树即可通过聚簇索引定位到要查找的行记录数据。
普通索引查找过程
如果查询条件为普通索引（非聚簇索引），需要扫描两次B+树，第一次扫描通过普通索引定位到聚簇索引的值，然后第二次扫描通过聚簇索引的值定位到要查找的行记录数据。
- 先通过普通索引 age=30 定位到主键值 id=1
- 再通过聚集索引 id=1 定位到行记录数据
4.2.1 什么是覆盖索引
只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。覆盖索引是一种优化手段。
示例
还是之前的搜索过程，但是通过普通索引 age=30 定位到主键值 id=1时已经是所需的所有列数据了，因此无需回表
4.2.2 如何实现覆盖索引
将被查询的字段，建立到联合索引里去
explain分析：因为age是普通索引，使用到了age索引，通过一次扫描B+树即可查询到相应的结果，这样就实现了覆盖索引
创建联合索引
explain分析：age是普通索引，但name列不在索引树上，所以通过age索引在查询到id和age的值后，需要进行回表再查询name的值。此时的Extra列的NULL表示进行了回表查询。
这个时候可以创建组合索引
explain分析：此时字段age和name是组合索引idx_age_name，查询的字段id、age、name的值刚刚都在索引树上，只需扫描一次组合索引B+树即可，这就是实现了索引覆盖，此时的Extra字段为Using index表示使用了索引覆盖。
4.2.3 什么时候使用覆盖索引
全表count查询优化
此时
使用索引覆盖优化：创建age字段索引
列查询回表优化
前文在描述索引覆盖使用的例子就是
例如：select id,age,name from user where age = 10;
使用索引覆盖：建组合索引idx_age_name(age,name)即可
分页查询
例如：select id,age,name from user order by age limit 100,2;
因为name字段不是索引，所以在分页查询需要进行回表查询，此时Extra为Using filesort文件排序，查询性能低下。
使用索引覆盖：建组合索引idx_age_name(age,name)
1.添加 PRIMARY KEY（主键索引）
2.添加 UNIQUE(唯一索引)
3.添加 INDEX(普通索引)
4.添加 FULLTEXT(全文索引)
5.添加多列索引
6.查看索引
7.删除索引
8.强制走索引的一种方式
最左匹配原则：最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。
索引的底层是一颗B+树，那么联合索引当然还是一颗B+树，只不过联合索引的健值数量不是一个，而是多个。构建一颗B+树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建B+树。
假如创建一个（a,b)的联合索引，那么它的索引树是这样的
可以看到a的值是有顺序的，1，1，2，2，3，3，而b的值是没有顺序的1，2，1，4，1，2。所以b = 2这种查询条件没有办法利用索引，因为联合索引首先是按a排序的，b是无序的。
同时我们还可以发现在a值相等的情况下，b值又是按顺序排列的，但是这种顺序是相对的。所以最左匹配原则遇上范围查询就会停止，剩下的字段都无法使用索引。例如a = 1 and b = 2 a,b字段都可以使用索引，因为在a值确定的情况下b是相对有序的，而a>1and b=2，a字段可以匹配上索引，但b值不可以，因为a的值是一个范围，在这个范围中b是无序的。
6.1.1 全值匹配查询时
用到了索引
where子句几个搜索条件顺序调换不影响查询结果，因为Mysql中有查询优化器，会自动优化查询顺序。
=、in会自动优化顺序
6.1.2 匹配左边的列时
都从最左边开始连续匹配，用到了索引
这些没有从最左边开始，最后查询没有用到索引，用的是全表扫描
如果不连续时，只用到了a列的索引，b列和c列都没有用到，无法跳过某个列使用后续索引列
6.1.3 匹配列前缀
如果列是字符型的话它的比较规则是先比较字符串的第一个字符，第一个字符小的哪个字符串就比较小，如果两个字符串第一个字符相通，那就再比较第二个字符，第二个字符比较小的那个字符串就比较小，依次类推，比较字符串。
如果a是字符类型，那么前缀匹配用的是索引，后缀和中缀只能全表扫描了
6.1.4 匹配范围值
可以对最左边的列进行范围查询
多个列同时进行范围查找时，只有对索引最左边的那个列进行范围查找才用到B+树索引，也就是只有a用到索引，在1<a<3的范围内b是无序的，不能用索引，找到1<a<3的记录后，只能根据条件 b > 1继续逐条过滤
6.1.5 精确匹配某一列并范围匹配另外一列
如果左边的列是精确查找的，右边的列可以进行范围查找
a=1的情况下b是有序的，进行范围查找走的是联合索引
6.1.6 排序
一般情况下，我们只能把记录加载到内存中，再用一些排序算法，比如快速排序，归并排序等在内存中对这些记录进行排序，有时候查询的结果集太大不能在内存中进行排序的话，还可能暂时借助磁盘空间存放中间结果，排序操作完成后再把排好序的结果返回客户端。Mysql中把这种再内存中或磁盘上进行排序的方式统称为文件排序。文件排序非常慢，但如果order子句用到了索引列，就有可能省去文件排序的步骤
因为b+树索引本身就是按照上述规则排序的，所以可以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了
order by的子句后面的顺序也必须按照索引列的顺序给出，比如
这种颠倒顺序的没有用到索引
这种用到部分索引
联合索引左边列为常量，后边的列排序可以用到索引
- 选择合适的字段创建索引：
- 不为 NULL 的字段 ：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
- 被频繁查询的字段 ：我们创建索引的字段应该是查询操作非常频繁的字段。
- 被作为条件查询的字段 ：被作为 WHERe 条件查询的字段，应该被考虑建立索引。
- 频繁需要排序的字段 ：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
- 被经常频繁用于连接的字段 ：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。
- 被频繁更新的字段应该慎重建立索引。
虽然索引能带来查询上的效率，但是维护索引的成本也是不小的。 如果一个字段不被经常查询，反而被经常修改，那么就更不应该在这种字段上建立索引了。 - 尽可能的考虑建立联合索引而不是单列索引。
因为索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。 - 注意避免冗余索引。
冗余索引指的是索引的功能相同，能够命中索引(a, b)就肯定能命中索引(a) ，那么索引(a)就是冗余索引。如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的。 在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。 - 考虑在字符串类型的字段上使用前缀索引代替普通索引。