细读MySQL实战45讲-深入浅出索引

常见类型

哈希表

添加数据，单个值查询都是Ologn时间复杂度

缺点：不是有序的，区间查找效率很低，只能遍历，适用于只有等值查询的场景，比如 Memcached 及其他一些NoSQL 引擎。

有序数组

缺点：只适用于静态存储引擎，因为一旦插入删除数据，有序数组就要往前或者后移位

二叉/多叉树

二叉树为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

缺点：索引不止存在内存中，还要写到磁盘上，树越高查询时间越久，用多叉树可以有效降低树高

InnoDB 的索引模型 B+ 树

• 每一个索引在 InnoDB 里面对应一棵 B+ 树。

• 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

  非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

  也就是说采用非主键进行查找时实际会有一个回表的过程，用得到的主键再次查询，因此查询时建议用主键

• 建议使用主键自增，由于 B+ 树是有序，通过最左前缀原则可以快速找到对应的数据，B+树不用调整数据顺序。

覆盖索引

由于key关联到主键，所以查询主键时不需要回表，这就是一种覆盖索引

select ID from T where k between 3 and 5
这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了

复合索引

• 遵循最左侧原则

  从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持a a,b a,b,c 3种组合进行查找，但不支持 b,c进行查找。当使用最左侧字段时，索引就十分有效。

• 遇到范围查找失效

• 索引下推

  索引下推在非主键索引上的优化，可以有效减少回表的次数，大大提升了查询的效率，5.6之前是一个一个验证复合索引，遇到一个索引就回表一次，而索引下推直接验证所有索引符合条件才回表

原文地址：https://www.cnblogs.com/crisliu/p/14781898.html