什么是索引

索引是一种能提高数据库查询效率的数据结构，使用它可以快速找到要查询的相应记录。
索引一般存储在磁盘的文件中，它是占用物理空间的。
适当的索引能提高查询效率，但是过多的索引会影响数据库表的插入和更新性能。
SQL优化的主要手段是利用索引查找，那为什么用上索引就这么高效？

索引种类

MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引、哈希索引、二叉树索引、全文索引等等。

哈希索引

哈希索引，是一种哈希表结构的索引。想理解它，只需要理解好HashMap的结构功能就行。HashMap有以下特点：

①HashMap存的是key-value键值对，即等值查找。所以哈希索引的特点是适合于等值查找的场景。
②HashMap使用hash算法的方式存放数据，导致它的数据不是顺序的，所以HashMap无法提供按key的范围直接查找数据，即哈希索引的缺点是无法范围查找。

二叉树索引

二叉树，是一种二叉树结构的索引。几种树的概念：

1.二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。
2.平衡二叉树：实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法，称为“平衡二叉树”。如何保持B树结点均匀分布的平衡算法是平衡二叉树的关键，而平衡算法是一种在二叉搜索树中插入和删除结点的策略。平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。
3.红黑树也属于平衡二叉树，但在每个节点增加一个存储位表示节点的颜色，非红即黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。
4.B树全名叫多路平衡树，是为磁盘等外存储设备设计的一种平衡查找树。

二叉树有以下特点：

①搜索二叉树特点是 左节点<父节点<右节点，可以范围查找；
②一颗平衡的二叉树，查找的时间复杂度相当于折半查找；
③一颗极度不平衡的二叉树会退化成一条链表，查找的时间复杂度最大；
④在数据越来越多的情况下，二叉树的深度越来越深，查找也会越来越困难。

二叉树索引的高度越来高，数据库只能将其压缩存储在磁盘中，每次在使用索引的时候，需要从磁盘取出，这样就增加了磁盘IO，拖慢查询速度。
综上，虽然说二叉树索引解决了哈希索引无法范围查找的问题。但是其平均情况下的等值查找比哈希索引还要慢，甚至在极端的情况还不如用哈希索引。

BTree索引

BTree(B-Tree)即B树，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树。BTree，它是一种叫多路（搜索）平衡树。

B树特性

B树的特性如下：

   1.关键字集合分布在整颗树中；
   2.任何一个关键字出现且只出现在一个结点中；
   3.搜索有可能在非叶子结点结束；
   4.其搜索性能等价于在关键字全集内做一次二分查找；
   5.自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的最少利用率，其最低搜索性能为O(logn)， 其中，M为设定的非叶子结点最多子树个数，N为关键字总数。

所以，B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题。
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

从上图可以看出，第三层最左边的叶子结点存放了3和5两个数据，（第二层的）非叶子节点子树指针P与关键字个数不相同。

B树与二叉树区别

B树与普通二叉树的区别是：
 ①B树并不是二叉的，并且其节点可以存放多个数据。
 ②B树每个结点存放至少M/2-1（取上整）和至多M-1个关键字（至少2个关键字），而二叉树每个节点存放一个关键字（M为设定的非叶子结点最多子树个数）。
 ③B树的所有叶子结点位于同一层，而二叉树的叶子结点可以不在同一层。

B树与红黑树区别

B树与红黑树的区别是：
 ①BTree的平衡不是通过旋转变色来实现，而是通过向下分裂来实现。

B树索引相较二叉树索引优点

B树相对于二叉树索引，有以下几个优势：
 ①B树由于一个树节点可以存储多个数据，有效地缩小了树的深度。
 ②B树通过向下分裂，保持平衡，避免退化成一条链表。
 
***在Mysql数据库中，BTree索引一般是MyISAM数据引擎在使用。并且，为了节省空间，MyISAM数据引擎对索引的值进行压缩存储。***比如有个数据为 string，第二个数据strgda在索引中会存储为 3,gda，以达到节约空间的目的。

B+树索引

B+树是B-树的变体，也是一种多路搜索树。

B+树定义

其定义基本与B-树同，除了：
1.非叶子结点的子树指针与关键字个数相同；
2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
3.B+树为所有叶子结点增加一个链指针；
4.所有关键字都存放在叶子结点中；

B+树与B树区别

B+Tree也是多路平衡树。它和BTree的区别是：
 ①在结构上，B+树的所有叶子节点是一条链表，而B树的叶子节点就是单纯的叶子节点。
 ②在数据存储上，B+树的叶子节点链表存储着所有的节点数据，从小到大排序；而B树，非叶子节点也存放数据。
 ③ B+树的搜索与B树基本相同，区别是B+树只有达到叶子结点才命中，而B树可以在
非叶子结点命中，其性能也等价于在关键字全集中做一次二分查找。

B+的特性

   1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
   2.不可能在非叶子结点命中关键字；
   3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
   4.更适合文件索引系统；

B*树

B树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。 B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3，代替B+树的1/2的利用率。因此，B树分配新结点的概率比B+树要低，空间使用率更高。

二叉搜索树、B树、B+树、B*树区别

1.二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
2.B（B-）树：多路搜索树，每个结点存储M/2到M（非叶子节点最多有M个子节点）个关键字，非叶子结点存储的是指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
3.B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
4.B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

MySQL索引原理

索引目的

索引的目的在于提高查询效率，可以类比字典，如果要查“mysql”这个单词，就需要先定位到m字母，然后从下往下找到y字母，再找到剩下的sql。

如果没有索引，那么你可能需要把所有单词看一遍才能找到你想要的，如果我想找到m开头的单词呢？或者ze开头的单词呢？是不是觉得如果没有索引，这个事情根本无法完成？

索引原理

所有索引原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也即通过同一种查找方式来锁定数据。

数据库也是一样，但显然要复杂许多，因为不仅面临着等值查询，还有范围查询(>、<、between)、模糊查询(like)、并集查询(or)、多值匹配（in【in本质上属于多个or】）等等。数据库应该选择怎么样的方式来应对所有的问题呢？

算法中，如果想要较快地查找到某个目标值，可以使用搜索树，其平均复杂度是lgN，具有不错的查询性能。

但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的，数据库实现比较复杂，数据保存在磁盘上，而为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。

索引结构

任何一种数据结构都不是凭空产生的，一定会有它的背景和使用场景，我们现在总结一下，我们需要这种数据结构能够做些什么

其实很简单，那就是：每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢？

就这样，b+树应运而生。

聚簇索引与非聚簇索引

每个InnoDB表有且仅有一个聚簇索引，一般以表的主键或唯一索引作为聚簇索引。所有的非聚簇索引，

聚簇索引

每个InnoDB表都需要一个聚簇索引。该聚簇索引可以帮助表优化增删改查操作。

聚簇索引的叶子节点就是数据节点，而非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。

聚簇索引是顺序结构与数据存储的物理结构一致的一种索引，并且一个表的聚簇索引只能有唯一的一条，一般为主键，没有主键的默认第一个组成唯一索引各列是NOT NULL的唯一索引。

如果数据表定义了一个主键，MySQL将使用主键作为聚簇索引。
如果没有为表指定一个主键，MySQL将第一个组成列都是NOT NULL的唯一索引作为聚簇索引。
如果InnoBD表没有主键且没有适合的唯一索引（没有构成该唯一索引的所有列都NOT NULL），MySQL将自动创建一个隐藏的名字为“GEN_CLUST_INDEX ”的聚簇索引。

因此，每个InnoDB表都有且仅有一个聚簇索引。

原文链接：https://blog.csdn.net/w605283073/article/details/95255618

非聚簇索引

非聚簇索引记录的物理顺序与逻辑顺序没有必然的联系，与数据的存储物理结构没有关系；一个表对应的非聚簇索引可以有多条，根据不同列的约束可以建立不同要求的非聚簇索引。

所有不是聚簇索引的索引都叫非聚簇索引或者辅助索引。

在InnDB存储引擎中，每个辅助索引的每条记录都包含主键，也包含非聚簇索引指定的列。

MySQL使用这个主键值来检索局促索引。

因此应该尽可能将主键缩短，否则辅助索引占用空间会更大。

一般来说用自增的整数型列作为主键列。

聚簇索引和非聚簇索引图解

下面举例聚簇索引和非聚簇索引的区别。

注意：这里的主键是非自增的。普通索引K表示普通的索引非唯一索引。

主键是采用B+Tree的数据结构（请看左图），根据上文可以知主键为聚簇索引，物理存储是根据ID的增加排序递增连续存储的。

普通索引K也是B+Tree的数据结构（请看右图），但是它不是聚簇索引，因此为非聚簇索引或者辅助索引（聚簇索引只可能是主键，或者所有组成唯一键的所有列都为NOT NULL的第一个唯一索引，或者隐式创建的聚簇索引这三种情况）。

他的叶子节点存储的是索引列的值，它的数据域是聚簇索引即ID。

假如普通索引k为非唯一索引，要查询k=3的数据。

需要在k索引查找k=3得到id=30。

然后在左侧的ID索引树查找ID=30对应的记录R3。

然后K索引树继续向右查找，发现下一个是k=5不满足（非唯一索引后面有可能有相等的值，因此向右查找到第一个不等于3的地方），停止。

整个过程从K索引树到主键索引树的过程叫做“回表”。

稀疏索引与稠密索引

这两者是用于形容索引里面的索引值是否密集或者稀疏。

稠密索引

「稠密索引」指的是一个索引值会对应一行数据记录。数据查找快，但是索引本身存储的成本高，比如 MySQL 的聚簇索引。

稀疏索引

「稀疏索引」指的是一个索引值会对应一块数据记录，并且要求数据是有序的，索引值对应的事这块数据记录的首行，查找数据时会通过首行数据记录向后查找。数据查找慢，但是索引存储的成本比较低，比如 kafka 中的文件存储机制。

参考

MySQL聚簇索引和非聚簇索引的理解
聚簇索引和非聚簇索引的区别
和刚入门的菜鸟们聊聊–什么是聚簇索引与非聚簇索引
干货篇：深入剖析 MySQL 索引和 SQL 调优实战
B+Tree原理、算法的解析和实现
B树、B-树、B+树、B*树之间的关系
二叉树、平衡二叉树、红黑树、BTree、B+Tree的区别和联系