主要内容：
一、 主键索引
二、 二级索引
三、 数学分析
四、 索引的作用
一、主键索引：
作为数据库的使用者，每天都需要跟数据库打交道，避免不了接触两个概念，一个是表，一个是索引。日常思维中，表是用来存储表中的数据，索引是用来加速查询访问。下面来看一下RDS for MySQL在InnoDB引擎下面，数据的物理组织是如何组织？
如上图所示这张表，它的主键是1个id、4个字节、id作为主键，后面跟着一个单字符的C1，然后还有一个int类型的c2，然后单字符的c3，同时在 c1字段上有索引，这是很简单的一张表。这个数据是如何组织？
在InnoDB引擎下，数据是存储在主键中，就是指数据是通过主建进行物理组织，跟Oracle本身默认的堆表不一样，Oracle本身默认创建的表如果不指定的话是一个堆表，真的有一个对象、物理结构、数据结构，一堆的数据结构来存储数据，同时主建是另外一个数据结构，是两份数据。对于MySQL在InnoDB引擎下面，本身数据是存储在主键的叶子节点中，如下图所示，“c1、c2、c3” 3列数据都存储在主键的叶子节点。
整个组建的数据结构是B-Tree，B指的是Balance Tree多路平衡树，而不是Binary tree二叉树。多路平衡树和二叉树之间区别在于：
·二叉树只有左分支和右分支，而且不限定左分支的深度和右分支的深度，也可以指树的高度，不限定左分支右分支的高度否是一致。
·多路平衡树指，从最上面的根节点到任何一个叶子节点是一致的，树高从任何一个维度来看，从任何一个叶子节点到根节点，从跟到任何一个业务节点，必须是一致的。多路指是每一个节点，不论分支节点、跟节点，下面可以挂多个此子节点。
同时在整个的结构里面，在Oracle的体系中，对于每个存储数据的基础单元叫块“block”，再MySQL中做称为页。在MySQL里面，如果不特意指定，默认都是16KB作为一页，从磁盘上访问,不管是读取一行数据，还是读取一个字节，都要读16KB的数据到内存中。
数据组织结构有几个关键点：
第一个关键点：数据是存储在主键中，必须显示定义主键，如果不显示定义主键会出现两种情况：
·第一种情况是在数据传输时，无法判断数据是不是重复，是不是唯一的。主键的定义是非空、唯一。
·第二种情况是把RDS for MySQL的备份还原到线下的数据时，没有主键的表，读取时字段对不上。因为阿里的SQL，为了避免出现没有定义主键，导致的问题，默认隐式的增加一个字段，把备份还原到物理备份或还原到本地时，这张表会多出一个字段，会导致恢复时这张表不可访问。
第二个关键点：表的每个数据块大小都是16KB，分支节点也是16KB，分支节点上的节点数越多，树越扁，树高越小，查询的越快。因为根和分支节点都需要内存运行，树高越高，需要读的16KB的块数就越多，导致查询会更慢。
第三个关键点：块的尺寸一定的情况下，里面带的条目数越多，树高越小，访问数据的代价越低。条目数取决于主键的数据类型，如下图所示，int类型4个字节，big int是8个字节，如果使用的是字符串，在uti8字符集的情况下，是char类型，至少要3个字节以上。所以关键点是主键尽量使int或者是big int这种整形，本身它很小，通常情况下一个16KB的块能放几百个int类型的条目，树高很容易控制在很小。
第四个关键点：本身它是一棵平衡树，平衡树的要求就在于，从根到任何一个叶子节点高度都要一样，树高是固定值，这棵树不断的被增、删、改的情况下，为了保证根与分支节点与叶子节点的一致性， 建议用auto_increment正向递增或者使用sequence，如果在有drds或者sequence引擎的情况下，可以用savings或者outer equipment这种单向递增，保证每次的写入的操作，尤其是插入操作，性能一致。
二、二级索引
除了主键以外的索引，其他都称之为二级索引。二级索引跟的主键索引一样，也是B-Tree。
二级索引在MySQL里与Oracle在设计上不一样，如下图所示，对“c1”字段做了一个索引，但实际上数据存储在主键中，所以数据寻址时，没有必要放数据的真正物理地址，在Oracle里，是数据的物理地址。在MySQL里面直接放主键的值，因为知道主键的值，就能定位到这行记录。虽然索引放的是“c1”，但是真正存储时，节点中是把主键的值都要存起来，这种数据类型导致主键的数据长度不能太长，否则会有问题。
补充一下，因为主键除了单项递增数据类型要小以外，如uuid、Md5不建议用来做主键，因为长度太长。如果长度太长，磁盘块里头放的会很小，树结构会变得很臃肿，相同存储相同的数据量，索引会占很大的空间。对于IO产生很大的影响，相同的硬件条件下,访问数据速度要慢，开销大、成本高。
三、数学分析
假设一张表里有一亿行记录，每一个磁盘页存放16KB的块，存放的条目数叫做平衡因子/分支因子（Balance factor）。
每个16KB分支节点可以存储的索引字段个数，取两个比较极限的情况，“b=2”每一个16KB的块里只能放两条记录，类似于二叉树,“b=100”每一个记录里能放100个条记录，就每一个16KB的块里能放100条记录。
树高(h)，树高影响物理IO，从磁盘上获取数据到内存，需要花多少个物业取IO访问到数据，数据库的增、删、改、查（select、interrupted，delete，replace），所有操作都是发生在内存。
索引B树高度：从叶子节点到根节点的节点个数。树高(h)固定的计算公式：
是跟 “b”和“n”相关的取两个的对数，“b”是平衡因子，在“b=2”的情况下，树高是27，在“b=100”的情况下，从定位1行记录的开销需要读27个16KB的块到内存，b定义成100，只需读4个16KB的块到内存，开销差异很明显。
存储空间的差异更明显，只说主键“b=2”情况下，需要花费781,250 MB的存储容量；“b=100”的情况下，花费15,625 MB的存储容量。
一般RDS内存正常情况下，最大的能到470GB内存，“b=100”时，770%~75%左右是分配给InnoDB用来缓存磁盘块， 770%~75%是可以保证数据完全缓存在内存中，表的核心数据都保存在内存里，也不会超出内存最大值。“b=2”时，只考虑了主健，不考虑任何二级索引，核心表数据也需要781GB，会需要出现物理IO换入换出数据，因为超出了内存空间。同样的存储，两种情况的代价是完全不一样，性能表现截然不同。
四、索引的作用
通过图书馆的模型介绍索引的作用，去图书馆内找一本书，正常的情况下，需要一个目录的，通过查目录，查询到所需的书在哪个书架上面的哪个位置上面，这样可以快速找到，这个目录就相当于索引，它是一个从空间换时间，通过提前做准备好其他空间，来缓解访问时间。需要注意的是这里只是寻找一本书，访问一个数据，如果访问的数据量，需要获取的数据量占总数据量的一定比例之后，就会引起质变。
优化是提高访问效率。
两个概念：TR、TS。
TR是随机访问一个16KB的块，TS是顺序的去读一个16KB的块需要的时间。
通过user用户表，(id int primary key, age int, fname char(1));
通过Select fname from users where age = 10进行一个简单的查询。
这里我们忽略树高，假设数据已经都在内存，因为不知道树读取的位置是在哪，那么下一次对根来说就是一个随机读，读到根在忽略树高且树高合理的情况下，需要画n减一个顺序图，把表编辑，因为没有索引。
位次条件下建索引，首先考虑位次条件， where后的条件是什么，根据什么条件去访问数据，根据规则去优化访问，如上图所示，age没有索引，就全面扫描，但在不同的情况下
TR = 10 ms
TS = 0.01 ms
RT = TR * 1 + TS * (n - 1)
= 10 ms * 1 + 0.01 ms * (900K -1)
= 10 ms + 9000 ms
= 9.01 Sec
RT = TR * 1 + TS * (n - 1)
= 10 ms * 1 + 0.01 ms * (9000 -1)
= 10 ms + 90 ms
= 100 ms
RT = TR * 1 + TS * (n - 1)
= 10 ms * 1 + 0.01 ms * (9 -1)
= 10 ms + 0.08 ms
= 10.08 ms
全表扫描不一定不是好事，取决于访问、目的、还有数据量的多少。
如果表里没太大的数据量，没有必要去访问索引，根据公式推理
结论就是访问的位次上面没有索引，全表扫描来获取数据，全面扫描不一定不好，不好的代价是在于表里的数据量，随着数据量的上升，TS的访问的代价会快速的增加，会导致时间快速增加。
随着数据量增加，上线时间加长，表的数据量越来越多，查询越来越慢，可以看在a制字段上面加一个索引，如下图所示：
由此推出，查询慢，在位次条件对应的情况下建索引，前提是获取的数据量是占总表的数据量很小的一部分，索引才是生效的。
实际上不管是oracle，还是MySQL的优化器也好，根据查询，先估访问的数据量大概会占总表的数据量的多少，包括根据版本不一样，会有略微变化。如果查询获取的数据量超过了总表数据量的一定比例之后，就不能再走这种索引访问形式，索引访问形式会带来大量的回表访问，会引起大量的随机读。
总结次位条件上面尽量建索引来加速访问，节省CPU，从时间来衡量，就是减少访问时间，减少查询的处理时间。
建索引前提下是访问的数据要占总表数据量很小的一部分。
如何进行优化，如下表所示，公式内头最大的开销是在4个随机读上面，来源于回表的3个随机读，产生三个随机读的原因是在于索引里没有fname，没有需要的数据，把fname放到我的索引里，Users (id int primary key, age int, fname char(1), key idx_age_fname (age,fname));这个时候访问就会变成了一个随机读，访问的根，三个顺序读，找到三个数据，通过扫索引的三行数据，就满足了查询，公式就会变成1个随机读加3个顺序读，出来是10个毫秒，这个索引叫做覆盖性索引，能够完全满足查询，不用回表，是在对于查询来说是最高效的一个访问形式。
如上图所示，从9秒钟优化到10 个毫秒，900倍的性能提升，最核心的表最频繁的查询建覆盖性索引。
建组合索引的时候，区分度越高的字段放在最前面，因为区分度越高，中间结果的索引片会越小越薄。目的就是只有在选择很小量的数据的时候，索引才是高效的。
反推就是中间生成的结果集或者中间的节点索引片越薄，包含的数据越小，索引对查询的加速是越高的。
最左原则，要求能匹配到的位次条件不能出现在第二个，位次条件一定要匹配到第一个字段才可以，就是在匹配索引跟查询的位次的时候，按照从左到右来匹配。如果已经有查询在建组合索引的时候，一定要把几个条件里区分度最高的放在最左边，其次，跟区分度类似的字段，尽量的往前放，经常被更新的字段尽量往后放，
最后，如果相同区分度都差不多，尽量把age看它的位次条件，如果是等值的，不管是等号大于等于小于等于都可以，只要带等号的尽量往前放，因为如果带着等号，条件会被用来生成中间的临时索引片或者中间的结果集。后面字段的条件依然能被用来生成中间的结果集。
fname是否能被用来生成结果集，需要看位次条件，第一个的位次条件，如果是等值带等号，第二个字段肯定能被用来，只要它后边位次加减中有，肯定能用来生成中间的结果集，生成重量级结构机，第三个能不能被用，要看第二个是不是带等值条件，就是说如果带等值条件，尽量往前放，归结起来就是：
1、 区分度越高的位次条件尽量往前放，如不是经常被更新的；
2、 带等值条件的尽量往前放；
举例，上图如果写的是不等于d那么age可以用来生成中间结果索引片，lname也能用来生成中间索引片，如果这里fname的位次条件，就不能用来生成索引片，只能用来做引擎下推的过滤，或者是server层的过滤，通过已经存储好的索引去生成中间结果集是基本上对CPU消耗是非常低的，但如果靠CPU去做过滤，生成结果集是非常耗CPU的，这是两种完全不同的访问方式。
还有如果前面的等值全是等值条件，排序之前所有的索引前置的字段都是等值的情况下，就可以直接通过索引来避免它的排序。
覆盖性索引并排序例子：
RDS for MySQL数据库的日常运维开发的使用的规范和建议
