索引的数据结构
主要说两种：
B+Tree（最核心，InnoDB 默认）
叶子节点按键有序，天然支持范围查询和排序。
非叶子节点只存键和指针，扇出大，树高低，磁盘 IO 少。
InnoDB 主键索引是聚簇索引：叶子节点直接存整行数据。
InnoDB 二级索引叶子节点存“索引列 + 主键值”，再通过主键回表取整行。
Hash（等值查找快，不支持范围）
适合 =、IN，不适合 > < BETWEEN ORDER BY。
InnoDB 不提供用户可控的 Hash 索引，但有自适应哈希索引（AHI，内部优化）。
MEMORY 引擎支持 Hash 索引。
B+树
B+ 树是一种多路平衡查找树（m-ary balanced tree），满足：
所有叶子节点在同一层（严格平衡）
非叶子节点只存“键（key）+ 子指针”，不存实际记录数据
所有数据（或记录指针）都在叶子节点
叶子节点之间有链表指针（通常是双向链表），方便范围扫描
图示：
[ 17 | 35 ]
/ | \
[ 5 | 9 | 12 ] [ 20 | 26 ] [ 40 | 48 | 60 ] <- 非叶子节点（只存键+指针）
/ | \ ... ...
[1,3,4] [5,7,8] [9,10,11] ... [40,41] [48,50] [60,70] <- 叶子节点（存数据）
<------ 叶子节点之间有双向链表，按 key 有序连接 ------>
索引设计成B+树有这么几个原因：
为什么mysql的索引使用B+树？
mysql的索引目的是为了更快的将磁盘上的数据查询出来，此时思路有树和哈希表，但是哈希表不能做范围查询和排序。
那就考虑树，二叉搜索树（包含红黑树）树节点最多只有两个，当数据量比较多的时候高度很大，并且有退化成链表的风险。需要查询多次
那就考虑B-树和B+树，B+树的优势是非叶子节点只存索引值以及对应的指针。这样整个树就会变得更矮。并且B+树叶子节点数据是一个天然有序的双向链表，非常适合范围查询，只需要找到起点往后查即可（是顺序IO）。所以B+树在查找速度、范围查询和磁盘读取次数做到了非常好的平衡。
为什么非叶子节点数据量少树的高度就会矮呢？
innoDB每次从磁盘中读一页出来是16kb，数据量越少页里就能查询出更多的索引，查询次数就会变少。
就很像一本书的目录里如果记录了大段的正文内容那一页存储的目录也就少了，你得多翻几页。
索引的类型
普通索引
索引建立没有限制
唯一索引
索引字段的非空值必须唯一，可以为null。索引中有Null标志位，用于记录是否为null，并且参与排序，会把null当成一个特殊的最小值
唯一索引会比普通索引好一点点，因为是唯一的查找到对应的值MYSQL会停止扫描。
主键索引（聚簇索引）
特殊的唯一索引，不能有null，创建或者修改表时产生，每个表只能有一个，不主动设置会默认生成一个。
因为InnoDB索引的叶子节点都需要存主键索引值，所以表必须有一个主键索引。非主键索引都叫二级索引
联合索引
多个列上创建索引
复合索引可以代替多个单一索引，相比多个单一索引复合索引需要的开销更小
全文索引
给正文进行倒排索引，不推荐，可以使用专门的搜索引擎。
当数据量比较小，查询条件不复杂，质量要求一般的字段可以考虑。
覆盖索引
查询需要的列全部在同一棵索引里，不需要回表
前缀索引
字符串只索引前 N 位，省空间但可能降精度
联合索引的最左匹配原则
联合索引在使用时，必须从最左边的字段开始连续匹配，才能命中索引。
原理：
联合索引 (a,b,c) 在 B+ 树里是按“字典序”排的：先比 a，a 相同再比 b，再比 c
where a = 1：能快速定位到 a=1 的起点和终点。在叶子页上只扫这一段连续区间，很高效
where a=1 and b=2：在 a=1 的区间里继续缩小到 b=2 子区间，很高效
where a=1 and b=2 and c=3：同上很高效
where a = 2：b=2 的记录分散在很多不同 a 段里，不连续。不高效
where a=1 and c=3 ：效果差于 a,b 连续匹配
where a=1 and b>2 and c=3 到 b 截断，此时a=1 and b>2 会形成一个范围，不连续。不高效
索引 (a,b,c) 像按“省-市-区”排序的通讯录。
你先给“省”，很快。
给“省+市”，更快。
只给“市”，就得翻很多省，慢。
给“省+区”但没有“市”，也要在该省里大量翻页。