索引

数据库索引就是为了提高数据查询的效率而产生的。
常见的索引模型大致分为三类：
哈希表：适合等值查询的场景，但不适合范围查询。
有序数组:能够保证在O(logn)的时间复杂度内进行范围查询，但是更新的维护成本过高，所以适合在静态存储引擎中使用。
搜索树：二叉树搜索树能够保证在O(logn)的查询和O(logn)的插入，但是一次搜索进行的io次数可能过高，例如一颗100w节点的平衡二叉树的树高为20，需要20次io操作。N叉树更适配磁盘的访问模式。

根据索引与数据的存储位置可以将索引分为两类：

聚簇索引：数据与索引存储在一起，找到了索引也就找到了数据，叶子节点是页
非聚簇索引：数据与索引分开存储，找到了索引需要根据索引再次到磁盘上找到相应数据。

在InnoDB中，聚簇索引默认是主键，如果表中没有定义主键则会选择一个唯一的非空索引代替（uniq index），如果这样的索引也没有则会隐式定义一个主键来作为聚簇索引。

image.png

而MyISM使用的是非聚簇索引，无论是不是主键，叶子节点都存储的是键值以及指向数据的指针。

B+树的N（叉数）大小可以根据page大小进行调整，默认是16K，page（innodb_page_size参数）的大小关乎一个页能够存放多少个索引。例如一个页能够存储16条数据，能够存储键值+指针 1000个，则高度为2的B+树能够存储1000 * 16=16000数据，高度为3的B+树能够存储1000 * 1000 * 16 = 1600w行数据
B+树的高度为logBN（logB/logN）B（叉数）为底数,N（数据行数）为对数

在通过辅助索引找到主键值并在主键索引树种搜索的过程叫做回表

覆盖索引

如果普通索引中已经包括了查询需求所有的列，则不需要回表可以直接返回结果，这就叫做覆盖索引。

最左前缀原则

b+树这种索引结构支持最左前缀原则，当查询条件有多个时，并且有条件符合索引的最左前缀则可以使用索引进行查询。

索引下推

MySQL 5.6引入索引下推，可以在索引遍历过程中先对索引中包含的字段进行判断是否满足查询条件，如果可以判断出不满足则不需要回表操作。

重建主键索引

alter table T engine=InnoDB

普通索引和唯一索引

change buffer:适用于普通索引，在更新某行数据时，如果使用普通索引并且数据不在内存中时，可以直接将更新操作记录在change buffer里而不是读取磁盘并更新内存。而将该操作记录与原始数据进行merge的操作会在访问该数据时或后台线程定时merge。

唯一索引不能使用change buffer，因为唯一索引需要对数据的操作进行唯一性约束的检查，如果数据不在内存中需要将数据取出做判断，如果在内存中那么直接更新内存即可。

change buffer的作用：
为了降低随机的磁盘IO读取次数，但是如果在更新后马上进行访问的话还是需要进行IO读取数据，并且进行merge操作，这样反而增加了change buffer的维护代价。
changebuffer跟普通数据页一样也是存在磁盘里，区别在于changebuffer是在共享表空间ibdata1里
redolog有两种，一种记录普通数据页的改动，一种记录changebuffer的改动

change buffer 和redo log的区别
redo log是为了节省随机写磁盘的IO消耗，而change buffer是为了减少随机读取磁盘的IO消耗。