提纲：

🔥索引

• 概念

• 数据结构

• 建立索引

• 主键

🎈面试八股真题

• 1、简单介绍InnoDB索引

一、索引

1. 概念

• 索引本质上是一种数据结构，用于加快 MySQL 查询数据的效率

2.数据结构

• 1、HashMap：精确查找单条数据速度很快 O(1)，缺点是范围查找效率低 O(N)，并且索引必须唯一

• 2、B+ 树

  • 概念：B+ 树就是一个 m 叉平衡查找树，叶子节点会存放所有的 Key 以及对应的 data，每一个非叶子节点必须有 m/2 ~ m 个子节点和 Key，在添加元素时，根据 Key 的大小区间决定添加位置，当添加后子节点数超过 m 个时，就会向上分裂，将第 m/2 个子节点分裂到父节点去

  • 与红黑树和 AVL 树：B 树类天生就是为磁盘设计的数据结构，假设 B 树和 AVL 树都可以完全放入内存，B 树的时间复杂度是log(m) * logm(N)，log(m) 表示单个节点上对有序的 Key 进行二分查找，换底可得就是 log(N)，与 AVL 树似乎一样，然而，索引一般也是很大的，无法一次性加入内存，因此在 I/O 时，会一次 I/O 读取一个节点进入内存，如此一来 AVL 树要进行 log(N)次 I/O，而 B 树只需要 logm(N) 次，每个节点上的二分查找是在内存中进行，可以忽略不计

  • 与 B 树：一次磁盘 I/O 的大小是有限的，MySQL 中默认一次从磁盘中读取 16 kb，这对节点的大小就有了限制，假设 Key，Data，Point 各占一个单元，一次 I/O 可以读取 6 个单元，那 B 树一个节点一次只能读取 2 对数据，只能包含由 2 个 Key 确定的区间的信息，而 B+ 树可以包含 3 个，这就意味着 B+ 树的节点可以更大，包含更多的 Key，从而降低树的高度，虽然 B 树可以运气好，在根节点就找到 Key，但平均查询的 I/O 次数是不如 B+ 树的

    • #另外，B+ 树在叶子节点形成了双向链表，并且链表中相邻的节点在磁盘中连续存储，很适合系统的磁盘预读机制，即读取一个节点时，会将其之后一定范围的节点一起取出（局部性原理）

• B+ 树的增删改操作需要通过分裂维护一个 m 叉平衡查找树，并且也需要占据存储空间，因此索引不是越多越好

3.建立索引

• 通过 create/drop index on 或 alter table add/drop 的方式创建或删除索引

• 索引类型

  • 1、主键索引：MySQL 数据库表中必须有一个主键索引，若没有指定，会由 MySQL 自动生成一个隐藏的自增主键索引列

  • 2、普通索引

  • 3、唯一索引：索引值不能重复，通过唯一索引精确查找数据的访问过程 type 是 eq_ref，效率仅次于 const

  • 4、复合索引：形如（a，b，c）的索引，遵从最左前缀法则

  • 5、全文索引：full-text 索引，需要 like 的模糊查询的字段可以使用全文索引，效率高于 like

• 最左前缀法则：在创建复合索引（a，b，c）时，B+ 树的结构为，先根据 a 进行排序，当 a 相等时，根据 b 进行排序，当 b 相等时，根据c 进行排序，因此最左的字段是全局有序的，而 b、c 字段仅在左边的***定时才有序，是局部有序

  • #因此，当对 a 进行范围查找（>，<，!=，like 等）或是没有使用 a 索引时，此时 a 是不确定的，不能保证 b、c 的有序，因而索引失效；当使用 （a，c）组合的查询条件时，只会走 a 索引，因为 c 索引无效

• 建立索引原则

  • 1、对于经常要用做查询条件的字段

  • 2、索引长度最好不要太长，特别是主键索引

  • 3、遵