索引（含B树、B+树）

1、索引（index）

索引是在数据库表的字段上添加的，是为了提高查询效率存在的一种机制。
一张表的一个字段可以添加一个索引，当然，多个字段联合起来也可以添加索引。
索引相当于一本书的目录，是为了缩小扫描范围而存在的机制。

索引检索（效率高）：先通过目录（索引）去定位一个大概的位置，然后直接定位到这个位置，做局部性扫描，缩小扫描范围，快速查找

如果某个字段（name字段）没有添加索引（目录），或者说没有name字段创建索引，MySQL会进行全扫描，会将name字段上的每个值都比对一遍

MySQL：1、全表扫描；2、根据索引检索

2、索引结构

B树——多路平衡查找树
以最大度数为5的B树为例：

树的度数：一个节点的子节点个数。

每个节点有4个key，5个指针
为什么4个key，有5个指针？
比如：key（4）：20，30，62，89
那么：指针（5）：<20，20-30，30-62，62-89，>89

中间元素向上分裂

B树：所有节点存放key-value
B+树：所有数据都会出现在叶子节点；叶子节点形成一个单向链表

MySQL索引结构对经典的B+树进行优化，在原B+树的基础上，增加了一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+树。变成了循环双向链表

3 索引分类

聚集索引

必须有，且只有一个：数据存储和索引放在一块，索引结构的叶子节点保存了行数据

二级索引

可以存在多个：数据存储和索引分开，索引结构的叶子节点关联的是对应的主键

存在主键，主键索引就是聚集索引
没有主键，第一个唯一索引就是聚集索引
没有主键也没有唯一索引，InnoDB存储引擎自动生成rowid作为隐藏的聚集索引。

回表查询：根据二级索引找到主键值，再根据主键值根据聚集索引拿到行数据

索引使用原则

最左前缀法则