MySQL 索引数据结构
MySQL 的索引是B+ Tree 结构
B+ Tree 是多路查找树，其在每一个节点的孩子数可以多于两个，且每一个节点的孩子数可以多于两个，每一个节点处可以存储多个元素；
B+ Tree 的高度一般都是在2-4 这个高度，IO读写次数不多；
三层树结构 – 支撑的数据可以达到20G，四层树结构 – 支撑的数据可以达到几十T;
B+ 树只有叶子节点才会存储数据，而且存储的数据都是在一行上，而且这样数据都是有指针指向的，也就是有顺序的。这个按顺序去除数据 order by id，则不用做全表扫描。
hash: 虽然可以快速定位，但没有顺序，IO复杂度高
二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），而且IO 代价高。
红黑树：树的高度随着数据量的增加而增加，IO 代价高。
为什么采用自增主键
结合B+ Tree 的特点，自增主键是连续的，在插入的过程中尽量减少分页，即使要进行页分裂，也只会分裂很少一部分。并且能够减少数据的移动，每次插入都是插入到最后。
B+ Tree 在叶子节点是所有数据构成的双向链表，并且是有序的。
在分布式环境下采用snowflake 算法生成主键，保证其唯一性并且是有序的。
B+ Tree 结构
索引（index）的定义是存储引擎用于快速查找记录的一种数据结构。
索引是物理数据页，可以加快检索速度。
叶子节点包含所有索引字段和数据。
B+ Tree 检索方式
B+ Tree 索引能够快速访问数据，就是因为存储引擎可以不再通过全表扫描来获取数据，而是从索引的根节点开始进行二分查找。根节点的槽中都存放了指向子节点的指针，存储引擎根据这些指针能够快速遍历数据。
InnoDB 与 MyISAM 索引的不同
InnoDB 和 MyISAM 的索引都是B+ Tree 结构的。
不同点：
- InnoDB 的主键索引的hi聚集索引（聚簇索引），即主键和数据都位于叶子节点
- MyISAM 的主键索引是非聚集索引（非聚簇索引），MyISAM 数据表的索引文件和数据文件是分开的
覆盖索引
只需在一颗索引树上就能获取所需的所有列数据，无需回表，速度更快，这就叫做覆盖索引。
实现索引覆盖最常见的方法就是：将被查询的字段，建立组合索引
在全表扫描时加上order by 主键，可以不扫描全表而是只是查询叶子节点。
InnoDB 索引
- 聚簇索引
如果表定义了PK, 则PK 就是聚集索引；
如果表没有定义PK, 则第一个非空unique 列是聚集索引；
否则，InnDB 会创建一个隐藏的row_id 作为聚集索引。
- 辅助索引
二级索引
根据索引列构建B+ Tree，但B+ Tree 的每一行都存了主键和索引列的信息
MyISAM 索引
- 非聚集（聚簇）索引
与InnoDB 表的存储不同，MyISAM 数据表的索引文件和数据文件是分开的，被称为非聚簇索引结构。
- 主键索引
存储主键，叶子节点存储主键和地址
- 辅助索引
存储索引列，叶子节点存储所有列和地址 、
组合索引
在多个列上建立索引，这种索引叫做组合索引(复合索引)。组合索引在数据库操作期间所需的开销更小，因为建立一-颗索引树，可以代替多个单一索引。
CREATE INDEX <索引的名字> ON tablename (字段名1， 字段名2...);
最左前缀原则
在组合索引使用上要遵守最左前缀原则，就是最左优先，即查询中使用到最左边的列，那么查询就会使用到索引。
在使用时，应该尽量让组合索引做到全匹配，这样查询效率最高。
索引失效
- 如果从索引的第二列开始查找，索引将失效。
- 从左向右匹配直到遇到范围查询> < between索引失效 。
- A or B A 和B 中有一个不包含索引，索引失效。
- 索引字段不要参与运算，否则索引失效；from_unixtime(index) = ‘2021-01-08’
- 不要让索引字段发生隐式转换，否则类型失效，常见类似’1’ 隐式转换为1；
- like 模糊查询 以% 开头索引失效。