mysql索引
帮助数据库高效获取数据的排好序的数据结构
WHO
- 主键索引：也是一种唯一性索引，必须指定为primary key，每个表只能有一个主键（并不一 定是一个列，主键索引也可以是有多个列组成的组合索引）
- 唯一索引：索引列的所有值只能出现一次，即必须唯一，值可以为空
- 普通索引：基本所有类型，值可以为空，没有唯一性限制
- 全文索引：索引类型为fulltext，可以在char，varchar，text类型的列上创建，一般不用，可以用ES
- 组合索引：多列组成的索引，专门用于组合搜索
几个概念
聚簇索引
或者叫聚集索引，是将索引和数据放在一起存放，如innodb的b+tree结构
非聚簇索引
或者叫非聚集索引，是将索引和数据分开存放，如myisam的b+tree结构，最后的叶子节点里存放的是索引和数据的磁盘地址，要想查询数据，还得从.MYD文件中查找
回表
先通过普通索引在b+tree下查找主键，再通过主键索引在b+tree下查找内容，这个过程，叫回表。
如：
Select * from table where name=’zhangsan’;
Select id from table where name=’zhangsan’;
其中，id是主键，第一条查询需要做回表操作；
而第二条查询，因为b+tree里的name索引里本来存的就是主键id，不需要再回表通过主键去找主键了，直接拿主键索引返回就行了，这个操作叫索引覆盖。
索引覆盖
如：
Select * from table where name=’zhangsan’;
Select id from table where name=’zhangsan’;
其中，id是主键，第一条查询需要做回表操作；
而第二条查询，因为b+tree里的name索引里本来存的就是主键id，不需要再回表通过主键去找主键了，直接拿主键索引返回就行了，这个操作叫索引覆盖。
最左匹配
因为索引是先按序的
如：
有一个组合索引(name, age)，判断下面sql是否会用到该索引
Select * from user where name=’zhangsan’; //会，第一位匹配，可以
Select * from user where age=18; //不会，直接匹配第二位，不可以
Select * from user where name=’zhangsan’ and age=18; //会，完美匹配，肯定可以
Select * from user where age=18 and name=’zhangsan’; //会，sql优化器会根据已有索引，将sql优化成 select * from user where name=’zhangsan’ and age=18;也是一个完美匹配
谓词下推
先过滤出要查询的字段，再将要执行的操作放在下一步执行，叫谓词下推。
如：
Select t1.name, t2.name from t1 inner join t2 on t1.id=t2.id;
- 先把所有字段做表关联，然后再从关联好的表中选择需要的4个字段
- 先取出需要的4个字段，再做表关联，这个叫谓词下推
组合索引的索引下推
如：组合索引(name, age)
直接从存储引擎拉取数据的时候直接按照name和age做判断，将符合的结果返回，这叫索引下推
正常人脑流程（mysql中不是这个流程）
- 先根据name将所有满足条件的数据取出
- 再根据age过滤
索引匹配方式
- 全值匹配
- 匹配最左前缀
- 匹配列前缀
- 匹配范围值
- 精确匹配某一列并范围匹配另一列
- 只访问索引的查询
数据结构
二叉树
演示地址：https://www.cs.usfca.edu/~galles/visualization/BST.html
缺点
- 对于顺序的数据，二叉树是链式增长，没有效果
- 当数据量比较大的时候，树的高度会比较深（有几层深度，就会至少要查几次，即需要多次读入内存，而操作系统每次读取都是读4k整数倍大小的页，比如mysql就是每次读取16k）
红黑树
又叫二叉平衡树
演示地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
缺点
当数据量比较大的时候，树的高度会比较深（有几层深度，就会至少要查几次，即需要多次读入内存，而操作系统每次读取都是读4k整数倍大小的页，比如mysql就是每次读取16k）
B-Tree
B树，针对红黑树深度太深问题，可以考虑横向扩充每个节点的大小，于是，B树有了
特点
- 叶节点具有相同的深度，叶子节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左往右递增排列
- 所有键值分布在整棵树中
- 搜索有可能在非叶子节点结束
- 每个节点拥有多个子节点
缺点
当data比较大时，单个节点存的索引量较少，会导致树深度加深
B+Tree
特点
- 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高访问性能，特别是顺序查找的时候
B+tree相较于b-tree
因为最后的叶子节点之间有一个指针连接，当查询范围查找的时候，很方便
Hash表
基于哈希表实现，只有匹配所有列的查询才有效。对于每一行数据，存储引擎都会对所有索引列计算一个哈希码，哈希码是一个较小的值，不同键值的行计算出的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时保存指向每个数据行的指针。
如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中去。
将字段做一次hash运算，然后存一个映射表，查找的时候可以一次立马定位到对应的数据。
通常用于memory存储引擎中，速度非常快
优点
特别适合精确查找，一般用于那种不需要范围查找的字段上，如订单号
缺点
- Hash存储需要将所有的数据添加到内存，比较消耗内存空间
- 不适合范围查找，因为hash码是顺序的，但对应的数据行是乱序的，如：age>18。
- 对于联合索引，不支持部分查找。因为hash是按所有索引列来计算hash的，如（name, age），只用name来查询是不支持的
