索引结构-B+树
B+树
m阶B+树满足一下条件：
- 根结点的分支数量[k]范围为[2，m]
- 每个分支结点包含的分支数[x]范围为[ceil(m/2), m]
- 分支结点的关键字数量[y]等于[x-1]，所以[y]的范围是[ceil(m/2)-1, m-1]，关键字顺序递增
- 所有叶子结点都在同一层，且形成一个有序链表
操作导致的结构变化
插入
- 所有节点都没有满，直接插入
- 节点满了，将节点拆分为左右两个节点，将中间的关键字提向上一节点
节点的拆分对性能影响较大(涉及磁盘的数据移动)，所以某些情况下会使用旋转操作代替节点拆分 当需要拆分的叶子节点左右节点存在未满的情况(一般优先检查左节点)，会将已满的叶子节点的关 键字分到未满的相邻节点，并替换上一级节点的关键字，确保排序正确
删除
删除根据填充因子(fill factor)判断是否变化节点
- 节点关键字数目满足要求，直接删除，如果该关键字还存在于非叶子节点中，用该关键字右边的关键字代替
- 节点关键字数目少，与其兄弟节点合并，并更新上一级节点关键字，确保排序正确
innoDB索引
聚簇索引与非聚簇索引
- 聚簇索引：索引项的顺序与表中记录的物理顺序一致，且叶子节点存储了对应数据行的数据。innoDB中主键即为聚簇索引
- 非聚簇索引：叶子节点存储的是对应逐渐的值，索引项的顺序与表中记录的物理顺序没有关联性。对非聚簇索引的查询最后都会落到聚簇索引的二次查询。
回表与索引覆盖
- 回表：通过非聚簇索引查询，先通过非聚簇索引定位到主键值，再通过聚簇索引得到行数据。因此走了两边B+树的遍历，被称为回表查询。
- 索引覆盖：针对组合索引来说，是指能在索引树中直接获取需要查询的全部数据，无需通过主键二次查询。避免了回表查询。
sql优化
执行计划explain
explain命令是对sql执行的分析，主要关注type和extra两个信息：
type： 使用索引的级别
1. all：全表扫描 2. index：全索引扫描，通常出现在查询数据可直接在索引树中获取到，不需要获取行数据 3. range：使用索引范围查询 4. ref：查找条件使用了索引但是部位主键或者唯一索引，存在重复的值 5. eq_ref：查找条件使用的索引为主键或者唯一索引 6. const：将主键放置到where后面作为条件查询，mysql优化器能对这次查询进行优化转为一个常量extra：重要补充信息
1. using filesort：进行额外的排序操作，无法使用索引排序 2. using temporary：使用临时表保存中间结果，通常由于排序，分组，多表join导致 3. using index：使用了索引覆盖，说明无需回表查询 4. using index condition ：条件包含索引和未索引的列，优化器将首先解析索引的列，并在表中查找 其他条件的行（将索引下推），MySql5.6的新特性 5. using where：使用where中的条件来进行表扫描 ‘using where; using index’ 与 ‘using condition’相比前者更好
索引分析show index from
对表中索引的相关分析，以下是相对重要的信息：
- seq_in_index：该列在索引中的位置，索引单列则为1，组合索引则为索引定义中的顺序
- collation：索引的存储顺序，A表示升序，NULL表示无分类
- cardinality：唯一值数目的估计值，数值越大越好
- sub_part：被编入索引的字符数量，NULL表示全被编入
- null：索引是否包含NULL，YES表示有，NO表示没有。通常不建议索引带有NULL值
建议
- 索引的创建应选择区分度高的列，且避免有NULL值(建表字段建议都设置为非null的并加上默认值)
- 控制索引的长度，对于varchar等类型的列新建索引时，在保证高区分度的前提下，尽量取最短的前缀作为索引值
- 通过对sql的explain结果针对性优化，通常需要保证type的级别高于index。且需要注意extra中
出现using filesort或using temporary，这都是低效率的象征。 - 避免复杂的联表查询，最好控制在三张表左右的关联(受表的数量级影响)
- 排序，分组等操作需要注意是否能使用到索引