01
—
常见索引模型
哈希表
哈希表这种结构适用于只有等值查询的场景，key-value 的存储结构，比如：Memcached。
有序数组
有序数组比较适合等值查询和范围查询。使用二分查找时间复杂度O(log(N))。缺点是更新成本太高，只适用于静态存储数据。
树
二叉搜索树，左儿子小于父节点，右儿子大于父节点，查询时间复杂度O(log(N))，为了维持查询时间复杂度，需要保证是一颗平衡二叉树，插入时间复杂度O(log(N))。
二叉树是树中搜索效率最高的，但实际上大多数数据库存储并不是用二叉树，是由于索引不仅在内存中，还要写入磁盘。
假设一个100w个节点的二叉树，树高20，在使用机械硬盘的时候，一次寻址需要10ms，这个时候就需要200ms，这样太慢了。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉 树，而是要使用“N叉”树。这里，“N叉”树中的“N”取决于数据块的大小。
以InnoDB的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个 值，这已经17亿了。
02
—
InnoDB 的索引模型
每一个索引在InnoDB里面对应一棵B+树
create table T(ID int primary key,k int not null,index (k))engine=InnoDB;复制
表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下。
如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树;
如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为 500，再到ID索引树搜索一次。这个过程称为回表。
索引维护
B+树在插入的时候要维护索引的有序性，如果是非顺序的插入会造成页分裂，影响插入的性能，所以一般推荐主键自增。
普通索引的叶子节点是主键，所以主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
覆盖索引
上述例子中如果是如下SQL就不需要回表
select ID from T where k=5复制
覆盖索引可以减少树的搜索次数，显著提升查询性能。
最左前缀原则
B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。
在建立联合索引的时候，如何安排索引内的字段顺序？
第一原则是，如果通过调整顺序，可以少维护一个索引，那么 这个顺序往往就是需要优先考虑采用的。
如果既有联合查询，又有基于a、b各自的查询呢?查询条件里面只有b的语句，是无法使用(a,b)这个 联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护(a,b)、(b) 这两个索引。
这时候，我们要考虑的原则就是空间了。比如上面这个市民表的情况，name字段是比age字段大的 ，那我 就建议你创建一个(name,age)的联合索引和一个(age)的单字段索引。
普通索引和唯一索引选择
查询过程：普通索引查找到第一个满足条件的记录后会继续再查找下一个记录。唯一索引查到第一条记录就停止继续往下查。InnoDB是按照页为单位来读取数据，所以这种性能影响微乎其微。
更新过程：如果更新的目标页不在在内存中。普通索引在写入的时候可以直接写入到 change buffer 中，change buffer 是在内存中保存的，效率非常高。唯一索引要将数据读到内存中，判断到没有冲突，插入这个值。
唯一索引用不上change buffer的优化机制，因此如果业务可以接受，从性能角度出发建议你优先考虑非唯一索引。
怎么给字符串字段添加索引？
直接创建完整索引，这样可能比较占用空间;
创建前缀索引，节省空间，但会增加查询扫描次数，并且不能使用覆盖索引;
倒序存储，再创建前缀索引，用于绕过字符串本身前缀的区分度不够的问题;
创建hash字段索引，查询性能稳定，有额外的存储和计算消耗，跟第三种方式一样，都不支持范围扫描。
以上内容摘自极客时间《MySQL实战45讲》，如果感兴趣可以扫描下方二维码订阅。
