mysql索引原理(2)

1、索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

数据库查询最基本的查询算法是顺序查找（linear search）时间复杂度为O(n)，显然在数据量很大时效率很低。优化的查找算法如二分查找（binary search）、二叉树查找（binary tree search）等，虽然查找效率提高了。但是各自对检索的数据都有要求：二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织）。

所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

2、索引实现

MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址。在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。

InnoDB 也使用 B+Tree 作为索引结构,但具体实现方式却与 MyISAM 截然不同。

1. 第一个重大区别是 InnoDB 的数据文件本身就是索引文件。而MyISAM 索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。

   在InnoDB 中,表数据文件本身就是按 B+Tree 组织的一个索引结构,这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。

2. 第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说,InnoDB 的所有辅助索引都引用主键作为 data 域。

3、聚簇索引和非聚簇索引的差异

聚簇索引保证关键字的值相近的元组存储的物理位置也相同（所以字符串类型不宜建立聚簇索引，特别是随机字符串，会使得系统进行大量的移动操作），且一个表只能有一个聚簇索引。

InnoDB对主键建立聚簇索引。如果你不指定主键，InnoDB会用一个具有唯一且非空值的索引来代替。如果不存在这样的索引，InnoDB会定义一个隐藏的主键，然后对其建立聚簇索引。

InnoDB的二级索引的叶子包含primary key的值，而不是行指针(row pointers)，这减小了移动数据或者数据页面分裂时维护二级索引的开销，因为InnoDB不需要更新索引的行指针。

4、覆盖索引(Covering Indexes)

如果索引包含所有满足查询需要的数据的索引成为覆盖索引(Covering Index)，也就是平时所说的不需要回表操作。

覆盖索引用通俗的话讲就是在select的时候只用去读取索引而取得数据，无需进行二次select相关表。这样的索引的叶子节点上面也包含了他们索引的数据。

当发起一个覆盖索引的查询时，在explain的Extra列可以看到Using Index

1、覆盖索引查询时除了除了索引本身的包含的列，还可以使用其默认的聚集索引列
2、这跟InnoDB的索引结构有关系，主索引是B+树索引存储，也即我们所说的数据行即索引，索引即数据
3、对于InnoDB的辅助索引，它的叶子节点存储的是索引值和指向主键索引的位置，然后需要通过主键在查询表的字段值，所以辅助索引存储了主键的值
4、覆盖索引也可以用上InnoDB 默认的聚集索引
5、InnoDB引擎的所有储存了主键ID，事务ID，回滚指针,非主键ID，他的查询就会是非主键ID也可覆盖来取得主键ID

覆盖索引是一种非常强大的工具，能大大提高查询性能。只需要读取索引而不用读取数据有以下一些优点：
(1)索引项通常比记录要小，所以MySQL访问更少的数据；
(2)索引都按值的大小顺序存储，相对于随机访问记录，需要更少的I/O；
(3)大多数据引擎能更好的缓存索引。比如MyISAM只缓存索引。
(4)覆盖索引对于InnoDB表尤其有用，因为InnoDB使用聚集索引组织数据，如果二级索引中包含查询所需的数据，就不再需要在聚集索引中查找了。

注意
1、覆盖索引也并不适用于任意的索引类型，索引必须存储列的值
2、Hash 和full-text索引不存储值，因此MySQL只能使用B-TREE
3、并且不同的存储引擎实现覆盖索引都是不同的
4、并不是所有的存储引擎都支持它们
5、如果要使用覆盖索引，一定要注意SELECT 列表值取出需要的列，不可以是SELECT *，因为如果将所有字段一起做索引会导致索引文件过大，查询性能下降，不能为了利用覆盖索引而这么做

参考

1、Mysql聚簇索引和非聚簇索引原理（数据库）
2、MySQL索引实现原理分析
3、MySql数据库索引原理
4、MySQL索引背后的数据结构及算法原理
5、MySql索引原理与使用大全
6、[MySQL] 索引与性能（3）- 覆盖索引
7、mysql高效索引之覆盖索引
8、MySQL之高效覆盖索引