概述

MySQL官网对于索引的定义：索引是存储引擎用于快速找到记录的一种数据结构。
可以简单的理解为：索引就是排好序的帮助快速查找的数据结构。

索引是一种特殊的数据文件：

• MyISAM引擎中，索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
• InnoDB引擎中，表数据文件本身就是按照B+Tree组织的一个结构，这棵树的叶子节点中保存的就是完整的数据记录，非叶子节点保存的是索引，在innodbDB引擎中索引和数据都在.ibd文件中。

索引是一种数据结构：

• 索引是一个单独的、物理的数据结构，它是某个表中一个根据一个字段或者多个字段创建的一个集合。
• 数据库索引是数据库管理系统中一个排好序的数据结构。

MySQL默认使用的是B+Tree结构管理索引。

从二叉树到B+树

参考：

https://www.fanruan.com/blog/article/301411/

二叉树
二叉查找树的特点：

• 左子树的键值小于根键值
• 右子树的键值大于根键值
• 每个节点分别保存字段数据和一个指向对应数据记录的物理地址的指针

如图所示是一个二叉查找树示例，比将表数据加载到内存再全表扫描来说显然要高效：

为什么不用二叉查找树？
二叉查找树的缺点：
MySQL索引底层没有采用二叉查找树，因为在存储有序数据时，使用二叉查找树会进行排序，最终会排列成一个单向链表，对于获取链表尾部的数据，效率就会比较低，即存在不平衡的问题：

当数据是顺序或近似顺序插入时，二叉树会退化成链表，导致查找和插入操作的时间复杂度变为O(n)。这对于数据库这种需要高效操作的大规模数据系统来说，是不可接受的。

其次，二叉树在内存中的表现也并不理想。每个节点都需要额外的存储空间来保存左、右子节点的指针，这会增加内存的开销。而且，二叉树节点的访问也可能会导致大量的指针跳转，这在现代处理器中会导致缓存不命中，从而影响性能。

平衡二叉树
平衡二叉树：
二叉树存在不平衡的问题，平衡二叉树可以通过叶子节点的自动旋转来进行调整，保证树的基本平衡。
平衡二叉树在满足二叉查找树的条件下，还满足了任何节点的两个子树的高度差最大为1。

下图是一个简单的比较：

常见的是一些平衡二叉树的变种，如红黑树和AVL树。

AVL平衡二叉树的优点：

• 叶子节点的层数减少
• 形态上能够保持平衡
• 查询效率提升了，大量的顺序插入也不会导致查询性能下降

为什么不用平衡二叉树？
AVL平衡二叉树的缺点：

• 一个节点最多分裂出两个子节点，树的高度还是太高，导致I/O次数过多
• 节点中只保存了一个关键字，保存的内容太少
• 维护二叉树平衡性的算法增加了实现和维护的复杂性。AVL树需要更多的旋转操作来保持平衡，红黑树需要在插入和删除操作后进行颜色调整和旋转操作。这些额外的操作不仅增加了编程的复杂性，还增加了运行时的开销。

B树
减少磁盘I/O是数据库性能提示的关键，因此每个节点应该保存尽可能多的数据。B-Tree（B树，即为平衡树Balance Tree的意思）就是这样设计的，它是一种平衡的多路查找树，允许一个节点存放多个数据（把瘦高变成矮胖）。

B-Tree中所有的节点的子树最大的值成为B-Tree的阶，用m表示。一棵m阶的树，必须满足以下条件：

• 树中每个节点，最多有m棵子树，存储最多m-1个关键字
• 根节点至少有两棵子树
• 分支节点至少有m/2棵子树
• 所有叶子节点在同一层（平衡），且以升序排序
• 有k棵子树的分支节点，存在k-1个关键字，关键字也是按递增顺序进行排序的

如图所示是一个B树示例：

图中的p节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。图中的每个节点称为页，页就是我们上面说的磁盘块，在mysql中数据读取的基本单位都是页，所以我们这里叫做页更符合mysql中索引的底层数据结构。
从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。
基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。

假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：
1.先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。
2.将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。
3.将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。

B-Tree首先定义了一条记录，为一个键值对。以聚簇索引为例，key就是记录的键值，value就是一行记录，含除主键以外的数据（data）。
B-Tree结构存储索引的特点：

• 索引值和data数据是分布在整棵树中的
• 存着指针，记录了子节点的地址信息
• 每个节点可以存放多个索引值以及对应的数据
• 树节点中多个索引值从左到右升序排序

B-Tree的每个节点元素，可视为一次I/O，树的高度表示最多的I/O次数。
B树的优点：
节点即存储索引也存储数据，因此如果频繁访问根节点附近，就会大大提高查询效率。
B树的缺点：
当data数据比较大时，每个节点存储的key就变少了，就会导致B树层数变高，增加I/O次数。
此外B树更适用于随机访问，顺序查找时B树的查找方式不太适合。
因此一般用于文件系统，或者部分数据库索引，如MongoDB。大部分关系型数据库都使用优化后的B+Tree。

B+树
如下图是一个四阶的B+树：

其在B树基础上做了优化，更适用于关系型数据库的查询。

B+树

B+树的定义
一棵m阶的B+树要满足如下要求：

• 每个分支节点至多有m棵子树
• 根节点要么无子树，要么至少两棵子树
• 除了根节点外，其他每个分支节点至少有m/2棵子树，即至少有2棵子树
• 有n棵子树的节点，恰好有n个关键字，即子树的个数与该节点的关键字个数相同。（注：B树是n个关键字对应n+1棵子树）
• 所有叶子节点包含全部关键字及指向相应记录的指针，且叶子节点按关键字大小自小到大顺序链接，将所有叶子节点链接起来
• 所有分支节点中仅包含它的各个子节点（也就是下级索引的索引块）中最大关键字及指向子节点的指针
• B+树中只有叶子节点保存数据，其余中间节点仅仅是索引，没有数据关联

B+树对比B树有哪些差别
从MySQL数据页的角度看B+Tree存储索引的特点：
MySQL设计者将B+树的节点的大小设置为等于一页(16kb)，目的是每个节点只需要一次I/O就可以完全载入。

• 1.分支节点的数据页存放的是“关键字+指针”，可以看作是索引的索引
• 2.叶子节点的数据页存放的是“全部的关键字+全部记录”（单指聚簇索引）
• 3.B+Tree的根节点是保存在内存中（只有第一次加载的时候需要从磁盘读到内存），子节点存储在磁盘上
• 4.所有节点按照索引键值大小排序，构成一个双向的链表，便于进行范围查询

B+树查找操作的特点：
B+Tree的好处就是体现在查询性能上的，有两种查找方式：

• 第一种：与B-Tree相同，通过指针实现随即查找，从根节点开始
• 第二种：根据叶子节点进行顺序查找，在一个节点的内部是可以实现折半查找的，但是如果是在多个节点之间，因为通过指针连接的，所以就要使用顺序查找。

单个元素查询参考下图：

范围查询则会自顶向下现查找范围的下限，通过链表指针遍历元素直到范围上限后结束。
范围查询时B+Tree所使用的I/O次数更少，查询也更简便。

参考：

https://blog.csdn.net/u014571143/article/details/129395219

B+Tree的优势

• 1.B+Tree中间节点没有数据，所以同样大小的磁盘页，B+Tree可以容纳更多的节点元素（即能保存更多的索引），在相同数据量的情况下，B+Tree比B-Tree更加的矮胖，因此I/O次数就更少。
• 2.B+Tree的查询效率更加稳定。B+Tree查询时必须要到达叶子节点，B-Tree特点是匹配到元素即可，因此B-Tree的查找性能是不稳定的，最好的情况是要找的数据在根节点上，最坏的情况是查找到了很靠后的叶子节点。
• 3.B+Tree扫库和扫表的能力更强，如果我们要根据索引进行数据表的扫描，选择B-Tree进行扫描则需要把整棵树遍历一遍，B+Tree只需要遍历叶子节点(有指针连接)。
• 4.B+Tree排序能力更强，在范围查询例子中可以看出B+Tree天然具备排序功能。

一棵B+Tree能存放多少数据？
MySQL设计者将一个B+Tree的节点大小设置为一个页大小，（innodb一个页大小是16kb）
假设一个B+树高度是2，存在一个根节点和若干个子节点，哪么这棵树存放的总记录数为：
根节点指针的数量*单个叶子节点记录行数

计算根节点指针数：假设表的主键是int类型，占用的就是4个字节，指针的大小为6个字节，一个页大概可以存储1638个索引指针。（16384个字节/(4B+6B)）

计算叶子节点能存储的记录数：假设一行记录的数据大小1kb，那么一页就可以存储16行数据，16kb/1kb=16

一棵高度为2的B+树可以存放的记录为：163816=26208条数据记录。
以同样的方式就可以推算出高度为3的B+Tree可以存放16381638*16≈四千多万

所以innodb中B+树的高度一般就是1_{3层，就可以满足千万级别的数据的存储，在查找数据的时候一次页的查找代表一次I/O，所以通过主键索引查询通常情况只要1}3此I/O就可以查到数据。

Hash索引

MySQL中索引常用的数据结构有两种：B+Tree和哈希表。
Hash索引底层是Hash表，根据键值<key,value>存储数据的结构。
比较适合根据key查找value值，也就是单个key查询或等值查询。

Hash索引的优点：
因为索引自身只需要存储对应的hash值，所以索引的结构比较紧凑，如果只需要做等值查询，不包括范围查询，可以选择使用哈希索引。
在没有哈希冲突的情况下，等值查询访问hash索引的速度是比较快的

Hash索引的缺点：
hash索引只包含哈希值和行指针，不存储字段值，所以每次查询都要回表。
hash索引只支持等值比较查询，不支持任何的范围查询，也无法用于排序，因为hash索引中的数据不是按照索引顺序存储的。
因此应用的并不多，用户也无法手动创建，只存在自适应哈希索引。

聚簇与非聚簇

索引的分类：
1.按字段特性分类：主键索引、前缀索引、复合索引、普通索引等
2.按数据结构分类：B+Tree索引、hash索引
3.按物理存储分类可以分为：聚簇索引、辅助索引(二级索引)

聚簇索引
聚簇不是一种单独的索引类型，而是一种数据的存储方式。例如innodb的聚簇索引使用的是B+Tree结构存储索引和数据。聚簇的含义是数据行和相邻的键值紧凑的存储在一起。
聚簇索引的二级索引特点：叶子节点不会保存引用行的物理位置，而是只保存行的主键值。
在innodb引擎中默认是B+Tree，主键就是聚簇索引，就是表本身；而二级索引(辅助索引)保存的是主键值。

• 如果有主键，则主键就是聚簇索引
• 如果无主键，则第一个非空唯一的字段列将作为聚簇索引
• 如果都没有，则innodb会根据隐藏字段row_id创建聚簇索引

非聚簇索引
非聚簇索引则是将数据与索引分开存储，索引结构的叶子节点存储的是指向数据行对应的地址。
在myisam引擎中，默认索引也是B+Tree结构，但是主键索引和辅助索引都是非聚簇索引，其索引结构的叶子节点存储的都是一个指向数据行的地址，使用辅助索引无需访问主键索引。

索引覆盖

覆盖索引：如果一个索引包含了所有需要查询的字段值(不需要回表)，这个索引就是覆盖索引。
覆盖索引优化思路：只需要在一棵索引树上就能获取SQL所需的列数据，无须回表，速度更快。
具体实现方式：将被查询的字段建立联合索引，这样就可以避免回表，可以直接返回索引中的数据。

索引下推

索引下推（ICP，index condition pushdown）是在5.6版本推出，用于优化查询的。
索引下推：可以在索引遍历过程中，对索引包含的字段先进行判断，在存储引擎层就过滤掉不符合条件的记录，减少回表次数。
而在没有ICP的时候，先根据二级索引的首列去聚簇索引中拿完整的数据值（回表），而对索引包含的字段的筛选是在server层完成的。

索引下推适用条件：

• 需要整表扫描的情况。比如：range, ref, eq_ref, ref_or_null 。
• 适用于InnoDB 引擎和 MyISAM 引擎的查询。（5.6版本不适用分区表查询，5.7版本后可以用于分区表查询）。
• 对于InnDB引擎只适用于二级索引，因为InnDB的聚簇索引会将整行数据读到InnDB的缓冲区，这样一来索引条件下推的主要目的减少IO次数就失去了意义。因为数据已经在内存中了，不再需要去读取了。
• 引用子查询的条件不能下推。
• 调用存储过程的条件不能下推，存储引擎无法调用位于MySQL服务器中的存储过程。
• 触发条件不能下推。