一、索引
1、数据结构
1）哈希表：数组+链表
特点：在NoSQL常见，适用于只有等值查询的场景，范围查找需要扫描全表、效率低
2）有序数组
特点：适用于静态存储引擎（例如国家城市类型基本不会变动的数据），查询效率很高，但更新数据成本太大（加大了判断更新的数据在哪个数据库的操作）
3）搜索树
①二叉树，例：红黑树
特点：数据量多的情况下，数高太高，查询效率低，磁盘IO（从硬盘内加载数据）需多次
②多叉树，例：B树、B+树
特点：高度降低，查询效率高；做索引，应用最广泛
2、主键索引
1）字符串做主键索引（例如：日期加单号）
占用空间大，io效率低
2）数值做索引
占用空间小，io效率高，自增，无页分裂、聚合现象
问题1：B+树索引结构，主键自增的表，当表删除一条数据后，索引是如何变化的？
答：删除某条数据时（例如：id=7的数据），InnoDB引擎只是将该数据标记为删除，空间依然会保留。当新增数据时，会自动加入id为8的数据
问题2：新增数据时，自增id用完会出现什么情况
答：产生报错现象，插入数据时会出现主键冲突异常；从业务的角度来讲自增ID不可能用完，单表也支撑不了那么大的数据量。不用担心自增ID用完的情况
3、非主键索引
回表：回表就是先通过数据库索引扫描出数据所在的行，再通过行主键id取出索引中未提供的数据，即基于非主键索引的查询需要多扫描一棵索引树.因此，可以通过索引先查询出id字段，再通过主键id字段，查询行中的字段数据，即通过再次查询提供MySQL查询速度
4、覆盖索引、联合索引
1）最左前缀原则：
索引index1:(a,b,c)有三个字段，当执行select * from table where c = '1' 这个sql语句是不会走index1索引的，select * from table where b =‘1’ and c ='2' 这个语句也不会走index1索引；执行select * from table where a = '1'；select * from table where a = '1' and b = ‘2’ ；select * from table where a = '1' and b = ‘2’ and c='3'会走index1索引。
原因：索引是有序的，index1索引在索引文件中的排列是有序的，首先根据a来排序，然后才是根据b来排序，最后是根据c来排序
2）索引下推
问题：如果已经有了（a，b）这个联合索引，还需要单独建立a索引吗？
答：索引项是按照索引定义里的字段顺序来排序的，因此在创建联合索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边；当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。当创建 (a,b,c) 联合索引时，相当于创建了 (a) 单列索引、(a,b) 联合索引以及 (a,b,c) 联合索引。想要索引生效的话，只能使用 a 和 a,b 和 a,b,c 三种组合；a,c 组合也可以，但实际上只用到了 a 的索引，并没有用到 c。
