MySQL有哪些索引结构（按数据结构分类）

B+树结构：B+树索引是一种平衡树数据结构，它将数据按照索引键值有序地存储在叶子节点上，非叶子节点只存储索引键值的范围和指向下一层结点的指针。因此查找、排序的效率很高。保存千万级别的数据，B+树一般只需要3-4层，也就是查询一条记录，只需要3-4次的磁盘IO
哈希索引：通过哈希表实现，查询时间复杂度是O（1），但不支持排序，模糊查询，范围查询等
全文索引：用于全文搜索的索引技术，可以对文本内容进行搜索，支持关键词的模糊匹配和搜索

InnoDB存储引擎支持的索引数据结构

支持B+树数据结构：

数据组织索引：B+树非叶子节点存储索引范围和指向下一层的节点，叶子节点存储索引键值和行数据，因此B+树索引属于聚簇索引
叶子节点链表：所有叶子节点通过指针相连，形成一个双向链表，支持快速的顺序访问和范围查询
平衡树结构：所有叶子节点在同一层上，数的高度平衡，即使是千万级数据，也只有3-4层，查询、排序的效率高

从数据页角度看B+树

InnoDB 的数据是按「数据页」为单位来读写的，默认数据页大小为 16 KB。每个数据页之间通过双向链表的形式组织起来，物理上不连续，但是逻辑上连续
数据页内包含用户记录，每个记录之间用单向链表的方式组织起来。为了加快在数据页内高效查询记录，设计了一个页目录，页目录存储各个槽（分组），且主键值是有序的，于是可以通过二分查找法的方式进行检索从而提高效率
为了高效查询数据页，InnoDB采用B+树作为索引，每个节点都是一个数据页
如果叶子节点存储的是实际数据的就是聚簇索引，一个表只能有一个聚簇索引；如果叶子节点存储的不是实际数据，而是主键值则就是二级索引，一个表中可以有多个二级索引
在使用二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是「索引覆盖」操作，如果查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫作「回表」

B+树的特性是什么

数据组织索引：B+树非叶子节点存储索引范围和指向下一层的节点，叶子节点存储索引键值和行数据，因此B+树索引属于聚簇索引
叶子节点链表：所有叶子节点通过指针相连，形成一个双向链表，支持快速的顺序访问和范围查询
平衡树结构：所有叶子节点在同一层上，数的高度平衡，即使是千万级数据，也只有3-4层，查询、排序的效率高

B+树和B树的区别是什么

数据存储：B+树叶子节点才会存储数据，而B树非叶子节点也存储数据。因此存储数据量相同的情况下，B+树非叶子节点存储的索引数量大于B树，B+树比B树更矮胖，查询效率更高
范围查询：B+树叶子节点构成了双向链表，因此范围查询更有帮助。B树只能通过中序遍历来范围查询，需要更多的磁盘IO，范围查询效率不如B+树
查询效率：B树的优势是查找到的数据恰好在一个非叶子节点时，由于该节点也包含数据，可以直接返回，最快在O（1）就可以查到。而B+树相对来说更稳定，每次查询都是相同的IO延迟

MySQL为什么使用B+树

B+树是多叉树，平衡树、红黑树是二叉树，高度更高，磁盘IO更大，查询速度更慢
相比跳表,跳表在极端情况下会变成链表，平衡性差，而数据库需要一个可预期的查询时间，并且跳表需要更多的内存
B树的数据存储在全部节点中，由于存储在非叶子节点，导致内存可能放不下，如果内存放不下，就意味着查询非叶子节点的时候就需要磁盘IO。此外B+树叶子节点构成了双向链表，对范围查询很友好

为什么索引用B+树而不用红黑树

B+树是多叉树，红黑树是二叉树，高度更低，在查询大量数据时候，磁盘IO更少
B+树叶子节点采用了双向链表结构，范围查询很方便

为什么索引用B+树而不用B树

磁盘读写代价：B+树叶子节点才会存储数据，而B树非叶子节点也存储数据。因此存储数据量相同的情况下，B+树非叶子节点存储的索引数量大于B树，B+树比B树更矮胖，查询效率更高
范围查询：B+树叶子节点构成了双向链表，因此范围查询更有帮助。B树只能通过中序遍历来范围查询，需要更多的磁盘IO，范围查询效率不如B+树
B+树增删查改效率更加稳定：B+树有大量冗余节点（所有非叶子节点都是冗余索引），比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化,比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化。除此之外，B+树每次查找都需要走到最后一层，查询更稳定

为什么索引用B+树而不用哈希表

哈希表的数据是散列分布的，不具备有序性，不能进行范围查找和排序，不支持联合索引最左匹配原则
哈希表存储哈希冲突的问题，哈希冲突严重的情况下会降低查询效率

B+树有什么优点和缺点

优点：

叶子节点链表：所有叶子节点通过指针相连，形成一个双向链表，支持快速的顺序访问和范围查询
平衡树结构：所有叶子节点在同一层上，数的高度平衡，即使是千万级数据，也只有3-4层，查询、排序的效率高

缺点：

产生大量的随机IO：随着数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点物理上不连续，做范围查询时会产生大量随机读IO

聚簇索引和非聚簇索引（也叫二级索引）有什么区别

先说聚簇索引和非聚簇索引叶子节点存放内容的区别，再引出回表查询和覆盖索引查询

聚簇索引叶子节点存放的是主键值和完整的数据
非聚簇索引叶子节点存放的是索引值+主键值

什么是覆盖索引

当查询到的数据能在二级索引的叶子节点查询到，就不用回主键索引查了。这种不需要回表的过程，叫覆盖索引

什么情况下会回表

在使用二级索引进行查询时，如果查询的列，不能在二级索引中全部查询到，就会发生回表。先通过二级索引的值查询到主键索引（即主键id），再通过聚簇索引的值定位到行记录的数据，需要扫描两次B+树。

insert操作对B+树结构的改变是怎么样的

如果我们使用的主键是递增的，每次插入数据只会插入到叶子节点最右边的节点中，如果改页面满了，就会开辟一个新页面，将新数据插入到新页面中。因为每插入一条记录，不需要重新移动数据，因此这种插入方式高效
如果如果我们使用的主键不是递增的，就有可能插入到现有数据页的中间，为了保证B+树的有序性，要移动其他数据满足新数据的插入。如果页面满了，就会发生页分裂，这时候要从一个页面复制数据到另一个页面，目的是保证B+树的有序性，页分裂可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率。

假如有一张两千万的数据，B+树的高度是多少？怎么算的？

具体要看数据库字段多不多，以及字段的类型，假设一行记录是1kb大小，那么2000万的数据表，B+树大概是三层高度。其次MySQL数据页的大小是16KB，去掉一些头信息，大概有15KB可以存储数据

在索引页中，也就是非叶子节点，假设主键id类似是bigint，占8字节，页号固定为4字节，那么索引页的一条数据是12字节。一个索引页可以存储15*1024/12 ≈ 1280个页号
叶子节点存放的是真正的数据行，假设一个记录是1kb，那么一页可以存放15条记录。
由公式，x是1280，y 是 15，Total 是 2KW，因此z = 3