背景
在MYSQL的常用的DML中，包括查询，分组，排序，索引都具有举足轻重的作用，而且加锁都是加在索引上，扫描到的行才会加锁，今天我们一起熟悉索引的基本原理并学习构建高效的索引；
追根溯源-从源头讲起
我们先了解计算机中数据是如何加载的
磁盘IO和预读
磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS（Million Instructions Per Second）的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行约450万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然就是灾难级别的了
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了预读的优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)，具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO。
那我们想要优化数据库查询，就要尽量减少磁盘的IO操作，所以就出现了索引。
我们这次主要学习InnoDB中的B+Tree索引
B+Tree
先看数据结构
通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
聚集索引与辅助索引
InnoDB是索引组织表，聚集索引是的非叶子节点存储的是主键值，叶子节点存储的是实际的数据，其中数据顺序是按照create table语句中的顺序排列；辅助索引非叶子节点存的是索引或者联合索引的第一个列，叶子节点存的是排序好的索引和主键值，当查询一个辅助索引时，需要在辅助索引树上搜索到主键值，并拿着主键值去聚集索引处找到具体的数据，这一过程叫做回表。
构建高效的InnoDB索引
索引的优点
大大减少了服务器需要扫描的数据量
帮助服务器避免排序和临时表
将随机I/O变为顺序I/O
想要构建高效的InnoDB索引，就要先回答一个问题，怎样的索引才能叫做高效的索引呢？
这里《relational database index design and the optimizers》给出一个三星索引的定义;
1星 索引将相关记录放到一起获得一星
2星 索引中的数据顺序和查找中的排序顺序一致获得二星
3星 索引中的列包含了查询中的全部列则获得三星
索引失效
最佳左前缀法则
如果索引了多列，要遵守最左前缀法则，指的是查询从索引的最左前列开始，不跳过索引中间的列。在多列索引中，如果 没有满足最佳左前缀原则，那么会造成中间断层部分的后边失效，这要从索引的数据结构说起
手绘了一个普通索引的结构，非叶子节点是第一个索引列，叶子节点存储排好序的所有索引和主键，如果中间发生断层，那么后边的数据将无法利用，InnoDB会把全部数据返回，让MYSQL的服务端过滤，但是新版本的MYSQL已经可以使用索引下推的功能在引擎中过滤了；
索引上使用函数或者计算会造成索引失效
select * from user where age+1 = 27;
存储引擎不能使用索引中范围条件右边的列
若中间索引列用到了范围（>、<、like等），则后面的所以全失效。
IS NULL和IS NOT NULL也无法使用索引
隐式类型转换
比如 字符串不加单引号索引失效 select * from user where id=10; id这个字段是varchar(10),是有索引的，但是explain显示走了全表扫描，输入的参数却是整型，所以需要做 类型转换。那我有个好问题
数据类型转换的规则是什么?
为什么有数据类型转换，就需要走全索引扫描?
一个简单的方法判断 select “10” > 9
如果规则是“将字符串转成数字”，那么就是做数字比较，结果应该是1;
如果规则是“将数字转成字符串”，那么就是做字符串比较，结果应该是0。
所以你就能确认MySQL里的转换规则了:在MySQL 中，字符串和数字做比较的话，是将字符串转换成数字。
就知道对于优化器来说，这个语句相当于: select * from tradelog where CAST(id AS signed int) = 110717; 而 对索引字段做函数操作，优化器会放弃走树搜 索功能。
构建高效的字符串索引
alter table user add index index1(email)
alter table user add index index1(email(6))
MYSQL是支持前缀索引的，上边两种创建索引的方式都支持，由于email(6)这个索引结构中每个邮箱字段都只取前6个字节(即:
zhangs)，所以占用的空间会更小，这就是使用前缀索引的优势。由于索引数据是不完全的，索引可能在辅助索引会有多个数据满足，要一一回表来过滤掉不满足条件的数据，索引选择前缀索引的长度是一个讲究
在这个例子中email选择长度8就满足了，在增加长度，选择性提升就很小了
另外注意，如果使用前缀索引，那么会造成索引覆盖无法使用，得不偿失
如果数据已经存储在索引中，那么单独遍历普通索引树，就可以得到需要的值，避免了回表的I/O操作，大大提高了效率
如果存储的前缀没有区分度怎么办？
比如，我们国家的身份证号，一共18位，其中前6位是地址码，所以同一个县的人的身份证号前 6位一般会是相同的。假设你维护的数据库是一个市的公民信息系统，这时候如果对身份证号做长度为6的前缀索引的 话，这个索引的区分度就非常低了。按照我们前面说的方法，可能你需要创建长度为12以上的前缀索引，才能够满足区分度要求。但是，索引选取的越长，占用的磁盘空间就越大，相同的数据页能放下的索引值就越少，搜索的 效率也就会越低。
方案1 采用倒叙前缀索引，入库和查询前 都用reverse函数，处理数据，在取前6位 方案2 模拟hash索引，使用crc32函数生成身份证号的hash值，已生成的hash值作为索引字段 方案3，中间截取索引 比如身份证号18位 我截取位两个字段 前6位和后12位，字段名位left,last;以 （last(6)）为索引；
join的索引选择
经常说join效率低，应该避免使用，那在什么情况下可以使用，如何优化 其实如果被驱动表上有索引，那么是可以使用join的，尽量让小表驱动大表
那我有个好问题，为什么要小表驱动大表，怎么样的表算小表，怎么样的表算大表
select * from t1 join t2 on (t1.a=t2.a)
看这条sql
我们在t2表的a字段构建一个普通索引
从表t1中读入一行数据 R;
从数据行R中，取出a字段到表t2里去查找;
取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分;
重复执行步骤1到3，直到表t1的末尾循环结束。
如果分成多条sql呢 ，扫描条数是不变的，但是会多一次交互，还不如join好 在这个join语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。
假设被驱动表的行数是M。每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引。每 次搜索一棵树近似复杂度是以2为底的M的对数，记为log2M，所以在被驱动表上查一行的时间复 杂度是 2log2M。假设驱动表的行数是N，执行过程就要扫描驱动表N行，然后对于每一行，到被驱动表上匹配一 次。因此整个执行过程，近似复杂度是 N + N2*log2M。显然，N对扫描行数的影响更大，因此应该让小表来做驱动表。
那怎样的表算小表？其实不是说数据量少就是小表 比如t2有1万条，t1有1千条，但是join后边的where限制t2.id<100,那么即使t2的总数据量比t1多，那在这次查询中也是t2是小表，需要让t2驱动t1；
在join中，原则是被驱动表关联的字段需要有索引，单实际上这个索引使用很少，可以这么优化 原始sql
小结
今天 我们聊了索引的数据结构，一些索引失效的原因，最后我们讨论了字符串索引的构建与join语句中驱动表的选择与优化；故事的最后 ，我们出个简单的思考题
答案 我们下回分解
