mysql-索引

按数据结构分类

1. B树索引-NOSQL使用较多
2. B+树索引
3. hash索引-KV数据库上比较常见
4. 位图索引

hash索引

利用hash表实现，一般用于等值查询。innodb引擎下不支持自定义hash索引，但innodb引擎有一种优化索引-自适应hash索引。

当innodb引擎发现除主键以外的索引，即二级索引，经常被使用，那么innodb引擎会给这个索引建立自适应hash索引，加快查询。所以innodb引擎的自适应索引是建立在索引上的hash索引。

树结构 vs hash结构

之所以使用树形结构索引而不使用hash结构索引，主要和sql的需求有关：

在单行查询的场景下，hash性能更好，因为只查一条记录。但对于排序查询的需求，hash索引的性能会从O(1)退化到O(n)，而树依然保持O(logN)。

二叉搜索 vs vs B vs B+

二叉搜索树

二叉搜索树为什么不适合做索引？

1. 当数据量大的时候，树高会比较高，导致查询变慢
2. 每个节点只存储一个记录，可能导致一次查询会有多次磁盘IO

B树

B树树特点：

1. m叉搜索
2. 叶子节点和非叶子节点都存储数据
3. 中序遍历可获得所有节点

B树适合作为索引的一个特性：局部性原理

局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO;（利用page cache特性）

使用局部性原理的根本原因：

1. 内存读写块，磁盘读写慢，而且慢很多;
2. 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘IO，提高效率;（page cache）

通常，操作系统一页数据是4K，MySQL的一页是16K。

所以B树之所以能作为索引：

1. 由于是m分叉的，高度能够大大降低;
2. 每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO;

B+树

在B树基础上做了改进：

1. 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上

B+树中根到每一个节点的路径长度一样，而B树不是这样。

2. 叶子节点间形成链表结构，获取所有叶子节点不再需要中序遍历

基于改进，B+树具有更优特性：

1. 范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯; 范围查询在SQL中用得很多，这是B+树比B树最大的优势。
2. 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储;非叶子节点存储记录的PK，用于查询加速，适合内存存储;
3. 非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引;

mysql为什么使用B+树

关键点：高度低，叶子节点是链表结构，查询时间可预测性，节点大小等于页大小

1. 很适合磁盘存储，能够充分利用局部性原理，磁盘预读;
2. 很低的树高度，能够存储大量数据;（与其他二叉搜索树相比）
3. 索引本身占用的内存很小;
4. 能够很好的支持单点查询，范围查询，有序性查询

按功能分类

1. 覆盖索引-查询列全部命中索引
2. 前缀索引-利用数据前几个字符的索引（如果前几个字符区分度不够大的话不建议使用）
3. 全文索引-很少使用，推荐使用中间件代替（比如ES）
4. 联合索引-使用多个列组成的索引。一般会将区分度最高的列放在最左边，因为有最左匹配原则。比如枚举值属于区分度较差的值类型
5. 唯一索引-要求该索引字段值唯一，一般用于保证唯一性
6. 主键索引-一般该索引的叶子节点会存放两种数据：1. 数据本身 2.指向数据的本身

主键索引

一般该索引的叶子节点会存放两种数据：

1. 数据本身
2. 指向数据的本身

在MYSQL的innodb引擎里，主键索引存放的是数据本身；在MYSQl的myisam引擎里存放的是数据地址。

主键索引也是聚簇索引

按是否存放数据

1. 聚簇索引-存放数据本身
2. 非聚簇索引-存放主键

MySQL的innodb来说，它的行锁是利用索引来实现的，所以如果查询的时候没有索引，那么会导致表锁。

聚簇索引和非聚簇索引

主要区别是他们是否存放数据本身。由于非聚簇索引只存放了主键，所以会带来回表的问题。如果查询的列不在非聚簇索引里，这时就需要根据非聚簇索引中的主键去聚簇索引里找到查询列，这一步骤就是回表，回表会带来额外的IO开销，所以在设计索引时要尽量考虑避免回表问题。

如何优化回表？

只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。即覆盖索引。

如何实现索引覆盖?

常见的方法是：将被查询的字段，建立到联合索引里去。

最左匹配原则

（大概匹配过程）多重循环

innodb索引 vs myisam索引

myisam索引

MyISAM的索引与行记录是分开存储的，叫做非聚集索引(UnClustered Index)。

其主键索引与普通索引没有本质差异：

1. 有连续聚集的区域单独存储行记录;
2. 主键索引的叶子节点，存储主键，与对应行记录的指针;
3. 普通索引的叶子结点，存储索引列，与对应行记录的指针;

所以myisam的表可以没有主键。

主键索引与普通索引是两棵独立的索引B+树，通过索引列查找时，先定位到B+树的叶子节点，再通过指针定位到行记录。

其B+树的索引构造：

1. 行记录单独存储;
2. id为PK，有一棵id的索引树，叶子指向行记录;
3. name为KEY，有一棵name的索引树，叶子也指向行记录;

innodb索引

InnoDB的主键索引与行记录是存储在一起的，故叫做聚集索引(Clustered Index)：

1. 没有单独区域存储行记录;
2. 主键索引的叶子节点，存储主键，与对应行记录(而不是指针);

所以innodb的PK索引查询非常快

因为这个特性，InnoDB的表必须要有聚集索引：

1. 如果表定义了PK，则PK就是聚集索引;
2. 如果表没有定义PK，则第一个非空unique列是聚集索引;
3. 否则，InnoDB会创建一个隐藏的row-id作为聚集索引;

聚集索引，也只能够有一个，因为行数据在物理磁盘上只能有一份聚集存储。

innodb为什么使用自增索引

InnoDB由于数据行与索引一体，如果使用趋势递增主键，插入记录时，不会索引分裂，不会大量行记录移动。

索引是不是越多越好

索引维护是需要开销的。在对数据做dml操作时，数据库需要对相应的索引作修改，修改需要开销；索引过多，会导致内存无法装下所有索引，那么访问索引本身就会触发IO。

索引下推