mysql索引
我想一想到mysql索引，大家可能都会想到B+树之类的。但是不知道有没有想过，为什么需要用b+树，如果是让你来设计mysql的索引的数据结构，你又会如何来设计呢？
我可以想到的数据结构可能是hash表、有序数组、树等等。
首先来看hash表，hash表的优势是等值查询，当我们查询某个值的时候可以在常数时间复杂度O（1）完成。所以查询很快，但是hash表有个缺点，就是无法满足范围查询，sql查询还是会有很多范围查询的，所以这个可能就不太合适了。
再来看有序数组，有序数据可以保证单个值查询时间复杂度在O(log(N)），而且对范围查询也很友好，可以根据二分法查询到值后，继续往后遍历就可以。但是有序数组在数据更新的时候，会出现性能问题，因为更新的时候要保证整个数据还是有序的，所以需要进行数组的数据搬移，这个过程会比较消耗性能。
那如果是用树呢？如果用二叉树，那么可以让更新和查询都控制在O(log(N)），当然是在平衡二叉树的情况下。除了二叉树，还有多叉树，由于mysql的数据是存储的磁盘上面的，为了减少磁盘的IO，就要减少数的高度，所以mysql就用了b+树来构建索引。
再来讲mysql索引，索引为了主键索引和非主键索引，主键索引也称为cuzhusuoyin。（用了拼音 - -）
主键索引和非主键索引的区别是，主键索引保存了表里面的行，也就是保存了所有的数据。非主键索引保存的是主键索引的建值。
也就是说，用主键索引查找需要遍历一次主键索引。用非主键索引查询数据，需要遍历非主键索引，还有主键索引。需要遍历两次是因为，非主键所以没有保存数据，只保存了主键索引的所以值，还需要根据这个索引值，在回到主键索引在做一次查找，这个被称为回表。所以非主键索引的查询会比直接用主键索引的查询来的慢。
还有值得一提的是，通常主键索引都是使用自增id，这又是为什么呢？这是因为如果使用自增的id，那么每次都是自增长，这样数据就会比较紧凑。也是为了防止数据分页合并带来的性能损耗。
所以通常会使用自增id来做主键索引。
举个例子：
上图为主键id索引，当来了一个主键id为600时，由于500和800刚好是一个数据页已经满了，所以600来了就需要进行页分裂，导致性能下降。