MySQL索引的问题
关于B树、B+树
我们都知道数据库的索引是基于B树、B+树这样的数据结构，这里并不打算就树的数据结构展开说，我也是一直看一直忘。引用一篇文章B树与B+树，有兴趣的自行了解吧。
MySQL的存储引擎和索引
顺序查找在实际工程中的时间复杂度O(N)是不能容忍的，这是索引产生的原因。如果表中只有一个字段，在这个字段上建立主键，我们可以很轻松地脑补出这个字段关键字存储在B+树上的每个结点。但是如果是多字段，那么当我们检索非索引字段时，就又变成了顺序查找，除非此时我们再在其他被检索的字段上建立第二套索引，这个索引由另一个独立的B+树来组织。
有两种常见的方案用以解决多个B+树访问同一表数据的问题，也就是我们常听到的**聚合索引（Clustered Index）**和 非聚合索引（Secondary Index）。它们虽然读作索引，但其实是指一种数据存储方式。
聚合索引：对于聚合索引而言，行数据和主键一起存储在主键B+树种，辅助键B+树只存储辅助键和主键。
非聚合索引：主键B+树的叶子结点指向了真正数据行的指针，而非主键。
MySQL中有两种常用存储引擎：InnoDB和MyISM。
InnoDB：聚合索引，将主键存储在主键B+树中的非叶子结点上，行数据存储叶子结点上，按照标准的B+树检索算法即可查找到主键对应的行数据。而如果是检索非主键字段，那么就会先行在辅助B+树上查找索引字段值所对应的主键，再到主键B+树上继续查找，最终返回行数据。
MyISM：非聚合索引，非聚合索引的两棵B+树看上去没什么不同，结点的结构一致，只是存储的内容不同，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。
下图直观地表现了两者的区别：
我们可以看到聚合索引需要经过两次的B+树检索，而非聚合索引只需1次。但聚合索引有它独特的优势：
1.由于行数据都存储在叶子结点上，那么主键和行数据是会被一起载入内存的，意味着找到叶子结点即可立刻返回数据，在以主键组织数据时效率更高。
2.辅助索引使用主键而非地址值作为指针，减少了行移动或者数据页分裂时维护辅助索引的工作。
本文可以看做是下列引文的读书笔记。