mysql 索引基础学习
问题
- 1为什么加索引能提高查询效率？
- 2索引的数据结构都有那些？
- 3为什么mysql选择的是B+树数据结构，而不是其他的数据结构？
- 4常常说的索引最左匹配，为什么是最左？
索引
什么是索引？
老师说：索引就像是书的目录。但是随着学习的深入就会觉得，索引是提高查询效率的一种数据结构。
数据类型
-
哈希表
就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
-
红黑树
和二叉树类似，有一个根节点，有两个子节点，左侧子节点比根节点小，右侧子节点比根节点大，分左子树和右子树。
-
B树
B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素。
-
B+树
同样的元素，B+树的表示要比B树要“胖”，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。
数据类型对比
哈希表：
通过散列可以快速获取磁盘文件指针，对于指定索引查找文件非常快，但是对于范围查找没法支持。
二叉树：
左边子节点的数据小于父节点数据，右边子节点的数据大于父节点数据。如果col2是索引，查找索引为89的行元素，那么只需要查找两次，就可以获取到行元素所在的磁盘指针地址。当数据量有几百万是，数的层级过多，导致IO过多，所以查询慢。
红黑树：
本质二叉树，属于二叉平衡树。二叉树特点。左小右大，所以可以范围查找，但是每个节点只能存储一个值，导致树的层级过多，导致IO过多，所以查询慢。（树的高度比而二叉树高度低，查询效率比二叉树高）
B树：
B树每个节点都存储数据。
任何一个关键字出现且只出现在一个结点中；（树的高度高度相对于红黑树降低，查询效率提高）
B+树
非叶子节点不存储数据，只存储索引(冗余)和指针，可以放更多的索引，树高降低 ；叶子节点包含所有索引字段；叶子节点比b树增加了指针连接；叶子节点有双向指针链接(首尾子节点还通过指针连接)，提高区间访问的性能，范围查找。（树的高度再次降低，在查询效率再次提高）
mysql 选择B+树作为索引的数据结构原因：
1.hash虽然查询快，但是不支持范围查询。（当数据量大，hash过多，查询效率不一定比B+树快）
2.树类结构里，同等条件下，B+树的树最低（IO最少），所以B+树最快。
存储引擎
常用的存储引擎有两个 MyISAM、InnoDB。
MyISAM：
MyISAM索引文件和数据文件是分离的（非聚集或稀疏）；
frm文件：存储这张表的表结构MYD文件：存储这张表的所有数据行
MYI文件：存储这张表的索引字段（索引里存储的是磁盘地址）如下图
InnoDB：
frm文件：存储这张表的表结构
ibd文件：存储这张表的所有数据行和索引字段聚集(聚簇)索引----叶节点包含完整数据记录。如下图
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
刚学习mysql 的时候，老师一定讲过这句话。但是为什么呢？
Innodb中的主键索引和实际数据时绑定在一起的，也就是说Innodb的一个表一定要有主键索引。不指定主键，InnoDB会找出不重复的一列作为主键索引，如果没找到不重复的一列，InnoDB会在后台增加一列rowId做为主键索引（rowid列用户不可见，用过Oracle比较熟悉）。
每个索引页是16K大小，bigint占用空间为8B，InnoDB指针6B，那么一页里就可以存储16K/14=1170个(主键+指针)。，另一方面整型比较比字符串比较更快速，字符串比较是先转换为ASCII码，然后再比较的。
主键索引不自增，后续增加会引起其他节点分裂和平衡。如果是自增主键，只用在尾节点做增加就可以。
说了这么多都是主键索引，那么非主键索引呢？
主键索引和非主键索引大部分都一样。只是非主键索引叶子节点存储的是主键值（这里单指InnoDB，MyISAM，存储的还是地址），而不是数据行。为什么这样？
1.节省空间
2.一份数据，不用担心事务问题，否则要维护两份数据
最左前缀原理
以前只是知道最左前缀，不知道原理那么下面就给大家揭秘
我们模拟数据建立一个联合索引select *, concat(right(emp_no,1), "-", right(title,1), "-", right(from_date,2)) from employees.titles limit 10;
-
select * from employees.titles where emp_no = 1；
-
select * from employees.titles where title = '1'；
-
select * from employees.titles where title = '1' and emp_no = 1
上面是三个sql那三个可以使用到索引？？
根据最左匹配发现 1和3可以。（3可以使用是因为mysql会对这个sql进行优化，优化之后会将emp_no=1这个条件放到第一位，从而可以利用索引）
那么2为什么不行呢。原因就是和第一节点进行比较时，没有emp_no这个字段的值，不能确定到底该去左子树还是右子树继续进行查询。
