索引数据结构
二叉树
跳跃表
红黑树
哈希
B树（B-Tree）
B+Tree（B-Tree变种）
MySQL 索引
非叶子节点不存储数据，只存储索引（冗余）
叶子节点包含所有字段，且叶子节点通过指针连接，提高区间查询性能
对于索引而言，降低树的高度有利于提高查询效率；相比于B树而言，因为B+树非叶子节点只包含索引信息，所以同样大小的存储块B+树能创建更高的度同时数据的结构层级更少
（B树叶子节点深度相同，无指针，所有节点索引元素不重复，全层节点数据从左向右递增）
查询 MySQL 页大小 16384 => 16KB (磁盘数据读取是按块的,而不是位,索引减少扫描表的次数减少I/O)
SHOW GLOBAL STATUS LIKE ‘INNODB_PAGE_SIZE’
存储引擎索引：如果未建索引，MySQL会选取数据唯一列作为索引列，如果不存在符合条件的列，则会创建一个隐藏列作为索引列，用于构建B+树
MyISAM（非聚集）：索引叶子节点存储数据地址，查找索引拿到 MYD 数据文件地址，再根据地址去取数据（索引文件和数据文件分离）
InnoDB（聚集）：索引叶子节点存储完整数据，推荐使用整形自增数据为主键；叶子节点值是从左向右递增的，利用范围取值；非主键索引结构叶子结点存储的是主键值，保证结果一致性且节省存储空间（索引和数据文件不分离，自增有利于减少构建B+树时节点分裂和平衡的次数）
Hash：对索引键进行一次Hash计算直接定位，缺点，仅支持“=”、“IN”等明确值得查询，无法进行范围查询，同时主键数据可能会存在Hash冲突
联合索引：最左前缀匹配，依次生效
EXPLAIN
SQL 分析结果表说明，如：EXPLAIN SELECT * FROM tbl_user;
ID：ID值为SELECT语句序号，值越大越先执行，ID相同则从上到下执行，ID为NULL的最后执行
SELECT_TYPE：simple 简单查询 primary 复杂查询的最外层 subQuery 子查询（不包含在From子句中的） derived 子查询（包含在From子句中的，查询结果会放在一个派生表/临时表）
TABLE：表名
TYPE：关联或访问类型，从最优到最差依次为 system > const > eq_ref > ref > range > all ; null表示优化后不需要在执行时再次访问表或索引
system/const 常量查询
eq_ref 基于主键索引的关联
ref 基于普通索引或唯一索引的部分前缀（如联合索引第一个字段）
range 基于索引的范围查找
index 二级索引扫描
all 全表扫描（主键索引）
POSSIBLE_KEY：可能用到的索引
KEY：用到的索引
KEY_LEN：键长度
ROWS：结果集大概行数
EXTRA：Using Index 表示使用覆盖索引，即所需查询字段都可以从索引树中直接获取，不需要在回表查找其他字段值，一般针对二级索引而言
Using temporary 一般为 select distinct column from 使用临时表，需要优化，即为 column 创建索引
Using file sort 一般为 order by 语句，小数据量可以通过内存完成排序，大数据量则需要通过磁盘完成，可以通过建立索引优化
索引失效情况：!= 或 <> ；is null 或 is not null ；like 以通配符开头 ；用函数处理列 ；字符串不加单引号 ；or 或 in 可能导致失效 ；范围扫描优化导致不走索引
常见 SQL 优化
1.联合索引，第一个字段为范围检索时，不走索引（如果满足覆盖索引，仍会走索引）；如果是等于，则走索引，MySQL 会根据数据量等参数评估
2.如下 like ‘val%’ 语句，通配符在右侧，类似查询常量，一定会走索引
3.索引下推：即如SQL where column1 like ‘val%’ and column2 = ‘30’ and column3 = 20 存在联合索引 column1_column2_column3 优化前把过滤到符合 column1 条件的数据都回表在判断其余字段；下推优化后会在索引 column1 时同时把不符合其余索引字段的数据过滤掉再回表，以减少回表次数，优化查询性能
4.order by / group by 优化：
– MySQL 开启 Trace 跟踪执行计划生成过程
SET SESSION OPTIMIZER_TRACE = ‘ENABLED=ON’ ,END_MARKERS_IN_JSON=ON;
– 执行完 SQL 语句后立即执行
SELECT * FROM information_schema.OPTIMIZER_TRACE;