面试题：
- 索引底层使用了什么数据结构和算法？
- 为什么 MySQL InnoDB 选择 B+Tree 作为索引的数据结构？
- 什么时候适用索引？
- 什么时候不需要创建索引？
- 什么情况下索引会失效？
- 有什么优化索引的方法？
索引是帮助存储引擎快速获取数据的一种数据结构，形象的说：索引是数据的目录，是以空间换时间的设计思想，索引和数据位于存储引擎中
索引的分类
可以按照四个角度来分类索引：
- 按「数据结构」分类：B+Tree 索引、HASH 索引、Full-Text 索引
- 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）
- 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引
- 按「字段个数」分类：单列索引、联合索引
按数据结构分类
| InnoDB 引擎 | MyISAM 引擎 | Memory 引擎 | |
|---|---|---|---|
| B+Tree 索引 | Yes | Yes | Yes |
| HASH 索引 | No（不支持， 但在内存结构中有一个自适应 hash 索引） | No | Yes |
| Full-Text 索引 | Yes（5.6 版本后支持） | Yes | No |
在创建表时，InnoDB 会根据不同的场景选择不同的列作为索引：
- 如果有主键，默认会使用主键作为聚簇索引的索引键
- 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键
- 上面两个都没有，将自动生成一个隐式自增 id 列作为聚簇索引的索引键
其它索引都属于辅助索引（Secondary Index），也称为二级索引或非聚簇索引
创建主键索引和二级索引默认使用的是 B+Tree 索引
B+Tree 是一种多叉树，叶子节点存放数据，非叶子节点只存放索引，而且每个节点中的数据按主键顺序存放。每一层父节点的索引值都会出现在下层子节点的索引值中，因此在叶子节点中，包括了所有的索引值和数据，每个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表
其实，InnoDB 里的 B+Tree 中的每个节点都是一个数据页：
B+Tree 的特点：
- 只有叶子节点才存放数据，非叶子节点仅用来存放索引
- 非叶子节点分为不同层次，通过分层来降低每一层的搜索量
- 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询
在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽），最后在分组内进行遍历查找
- 由于数据在物理上只会保存一份，所以聚簇索引只能有一个
- 二级索引可以有多个
通过主键查询数据
比如：
select * from product where id = 5;B+Tree 会自顶向下逐层进行查找：
- 将 5 与根节点的索引数据 (1, 10, 20) 比较，5 在 1 和 10 之间，所以找到第二层的索引数据 (1, 4, 7)
- 在第二层的索引数据 (1, 4, 7) 中进行查找，5 在 4 和 7 之间，所以找到第三层的索引数据 (4, 5, 6)
- 在叶子节点的索引数据 (4, 5, 6) 中进行查找，找到了索引值为 5 的行数据
数据库的索引和数据都存储在硬盘，可以把读取一个节点当作一次磁盘 I/O 操作。那么上面的整个查询过程一共经历了 3 个节点，也就是进行了 3 次 I/O 操作
B+Tree 存储千万级的数据只需要 3-4 层高度就可以满足，这意味着从千万级的表查询目标数据最多需要 3-4 次磁盘 I/O，所以 B+Tree 相比于 B 树和二叉树来说，最大的优势在于查询效率很高，因为即使在数据量很大的情况，查询一个数据的磁盘 I/O 依然维持在 3-4 次
为什么说 MySQL 单表不要超过 2000W 行？
根据大部分单行数据的大小，可以计算出大概 2000W 行左右，B+Tree 树层级会由 3 变为 4，会明显降低查询效率
当然，2000W 只是个预估值，实际要根据单行数据的大小适当调整
通过二级索引查询数据
- 主键索引的 B+Tree 叶子节点存放的是实际数据
- 二级索引的 B+Tree 叶子节点存放的是主键值，而不是实际数据
二级索引的 B+Tree 如下图：
通过二级索引查询数据会先检二级索引的 B+Tree 索引值，找到对应的叶子节点获取主键值，然后再通过主键索引的 B+Tree 树查询到对应的叶子节点，然后获取整行数据。这个过程叫「回表」，也就是说要查两个 B+Tree 才能查到数据
不过，当查询的数据能在二级索引的 B+Tree 叶子节点里查询到，就不用再查主键索引查，比如：
select id from product where product_no = '0002';这种在二级索引的 B+Tree 就能查询到结果的过程就叫作「覆盖索引」，也就是只需要查一个 B+Tree 就能找到数据
为什么选择 B+Tree
B+Tree VS. B Tree
- B+Tree 只在叶子节点存储数据，而 B Tree 的非叶子节点也要存储数据，所以 B+Tree 的单个非叶子节点能存储更多的索引，在相同的磁盘 I/O 次数下，能查询更多的节点
- 插入和删除数据时，B 树可能发生复杂的树的变形；B+Tree 不会
- B+Tree 叶子节点采用双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点
B+Tree vs 二叉树
- 对于有 N 个叶子节点的 B+Tree，其搜索复杂度为 O(logdN)，其中 d 表示节点允许的最大子节点个数。在实际应用中， d 值大于 100，保证了即使数据达到千万级别，B+Tree 的高度依然维持在 3
4 层左右，也就是说一次数据查询只需要做 34 次的磁盘 I/O - 而二叉树的每个节点最多只能有两个字节点，其搜索复杂度为 O(logN)，比 B+Tree 高出很多，检索到目标数据所经历的磁盘 I/O 次数很多
B+Tree vs Hash
- Hash 在做等值查询的搜索复杂度为 O(1)
- 但是 Hash 表不适合做范围查询
按物理存储分类
从物理存储的角度来看，索引分为聚簇索引（主键索引）、二级索引（辅助索引）
这两个区别在前面提到过：
- 主键索引的 B+Tree 叶子节点存放的是实际数据
- 二级索引的 B+Tree 叶子节点存放的是主键值，而不是实际数据
按字段特性分类
从字段特性的角度来看，索引分为主键索引、唯一索引、普通索引、前缀索引
主键索引
建立在主键字段上的索引，通常在创建表时一起创建，一张表最多只有一个主键索引，索引列不允许有空值
CREATE TABLE table_name (
...
PRIMARY KEY (index_column_1) USING BTREE
);唯一索引
建立在 UNIQUE 字段上的索引，一张表可以有多个唯一索引，索引列的值必须唯一，但是允许有空值
建表时，创建唯一索引：
CREATE TABLE table_name (
...
UNIQUE KEY(index_column_1, index_column_2, ...)
);建表后，创建唯一索引：
CREATE UNIQUE INDEX index_name
ON table_name(index_column_1 ,index_column_2, ...);普通索引
建立在普通字段上的索引，既不要求字段为主键，也不要求字段为 UNIQUE
建表时，创建普通索引：
CREATE TABLE table_name (
...
INDEX(index_column_1, index_column_2, ...)
);建表后，创建普通索引：
CREATE INDEX index_name
ON table_name(index_column_1, index_column_2, ...);前缀索引
对字符类型字段的前几个字符建立索引，而不是在整个字段上建立索引，前缀索引可以建立在字段类型为 char、 varchar、binary、varbinary 的列上
建表时，创建前缀索引：
CREATE TABLE table_name (
column_list,
INDEX(column_name(length))
); 建表后，创建前缀索引：
CREATE INDEX index_name
ON table_name(column_name(length));按字段个数分类
从字段个数的角度来看，索引分为单列索引、联合索引（复合索引）
- 建立在单列上的索引称为单列索引，比如主键索引
- 建立在多列上的索引称为联合索引
联合索引
将多个字段组合成一个索引，是二级索引
CREATE INDEX index_product_no_name ON product(product_no, name);联合索引的 B+Tree：
可以看到，联合索引的非叶子节点用两个字段的值作为 B+Tree 的 key 值。当在联合索引查询时，先按 product_no 字段比较，在 product_no 相同的情况下再按 name 字段比较
也就是说，联合索引查询的 B+Tree 是先按 product_no 进行排序，然后再 product_no 相同的情况再按 name 字段排序
因此，使用联合索引时，存在最左匹配原则，在使用联合索引进行查询时，如果不遵循「最左匹配原则」，联合索引会失效，无法利用到索引快速查询的特性
比如，一个 (a, b, c) 联合索引，如果查询条件是以下这几种，就可以匹配上联合索引：
where a=1where a=1 and b=2 and c=3where a=1 and b=2
注意：因为有查询优化器，所以 a 字段在 where 子句的顺序并不重要
但是，如果查询条件是以下这几种，因为不符合最左匹配原则联合索引就会失效:
where b=2where c=3where b=2 and c=3
利用索引的前提是索引里的 key 是有序的，b 和 c 是全局无序，局部相对有序，所以在没有遵循最左匹配原则的情况下，无法利用到索引
索引区分度
建立联合索引时的字段顺序对索引效率有很大影响。越靠前的字段被用于索引过滤的概率越高，实际开发工作中建立联合索引时，要把区分度大的字段排在前面，这样区分度大的字段越有可能被更多的 SQL 使用到
区分度 = 某个字段 column 不同值的个数 / 表的总行数
比如，性别的区分度就很小，不适合建立索引或不适合排在联合索引列的靠前位置，而 UUID 这类字段就比较适合
因为如果索引的区分度很小，假设字段的值分布均匀，那么无论搜索哪个值都可能得到一半的数据。在这些情况下，还不如不要索引，因为 MySQL 的查询优化器发现某个值出现在表的数据行中的百分比很高时（惯用界线是 30%），会忽略索引，进行全表扫描
联合索引进行排序
针对下面这条 SQL，怎么通过索引来提高查询效率？
select * from order where status = 1 order by create_time asc有的同学会认为，单独给 status 建立一个索引就可以了
但是更好的方式是给 status 和 create_time 建立一个联合索引，利用索引的有序性，根据 status 筛选后的数据就是按照 create_time 排好序的，这样可以避免 MySQL 数据库发生文件排序
在查询时，如果只用到 status 的索引，但是这条语句还要对 create_time 排序，这时就要用文件排序，在 SQL 执行计划中，Extra 列会出现 Using filesort
是否需要创建索引
索引最大的好处是提高查询速度，但是也有缺点：
- 需要占用物理空间，数量越大，占用空间越大
- 创建索引和维护索引要耗费时间，这种时间随数据量的增加而增大
- 会降低表的增删改效率，因为每次增删改索引，B+Tree 为了维护索引有序性，都需要进行动态维护
需要索引的情况：
- 字段有唯一性限制，如：id、商品编码
- 经常用于
WHERE查询条件的字段，如果查询条件不是一个字段，可以建立联合索引 - 经常用于
GROUP BY和ORDER BY的字段，在查询时就不需要再去做一次排序
无需索引的情况：
WHERE、GROUP BY、ORDER BY中用不到的字段- 索引区分度低的字段，如：存在大量重复数据
- 表数据太少时，不需要创建索引
- 经常更新的字段不用创建索引
优化索引的方法
这里说一下几种常见优化索引的方法：
- 前缀索引优化；
- 覆盖索引优化；
- 主键索引最好是自增的；
- 防止索引失效；
前缀索引优化
如果某个字段中字符串很长，而且需要索引，则使用前缀索引。可以减小索引字段大小，有效提高索引的查询速度
不过，前缀索引有一定的局限性：
order by无法使用前缀索引- 无法把前缀索引用作覆盖索引
覆盖索引优化
覆盖索引是指查询的所有字段，在二级索引 B+Tree 的叶子节点上都能找得到，而不需要通过聚簇索引查询获得，可以避免回表的操作
假设需要查询商品的名称、价格，有什么方式可以避免回表？
可以建立一个「商品 ID、名称、价格」的联合索引，如果索引中存在这些数据，查询将不会再次检索主键索引，从而避免回表
主键索引最好是自增的
InnoDB 创建主键索引默认为聚簇索引，同一个叶子节点内的各个数据是按主键顺序存放的，每当有一条新的数据插入时，数据库会根据主键将其插入到对应的叶子节点中
- 使用自增主键：每次插入的新数据会按顺序添加到当前索引节点的最后位置，不需要移动已有的数据，当页面写满，自动开辟一个新页面
- 使用非自增主键：每次插入新的数据时，可能会插入到现有数据页中间的某个位置，这将不得不移动其它数据来满足新数据的插入，甚至需要从一个页面复制数据到另外一个页面。这种情况称为页分裂，有可能造成大量的内存碎片，导致索引结构不紧凑，影响查询效率
另外，主键的长度不要太大，因为长度越小，非叶子节点存储的索引就越多，二级索引的叶子节点也越小
因此，如果没有特别的业务需求（如：反爬虫），建议使用自增字段作为主键
索引最好设置为 NOT NULL
索引列存在 NULL 会导致优化器在做索引选择时更复杂、更加难以优化，因为可为 NULL 的列会使索引、索引统计和值比较都更复杂，如：进行索引统计时，count 会省略值为 NULL 的行