MySQL索引的实现

1、MySQL索引的实现原理：

索引本质上就是一种通过减少查询需要遍历行数，加快查询性能的数据结构，避免数据库进行全表扫描，好比书的目录，让你更快的找到内容。（一个表最多16个索引）

1.1、索引的优缺点：

（1）索引的优点：

减少查询需要检索的行数，加快查询速度，避免进行全表扫描，这也是创建索引的最主要的原因。

如果索引的数据结构是B+树，在使用分组和排序时，可以显著减少查询中分组和排序的时间。

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

（2）索引的缺点：

当对表中的数据进行增加、删除和修改时，索引也要进行更新，维护的耗时随着数据量的增加而增加。

索引需要占用物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

1.2、索引的使用场景：

（1）在哪些列上面创建索引：

WHERE子句中经常出现的列上面创建索引，加快条件的判断速度。

按范围存取的列或者在group by或order by中使用的列，因为索引已经排序，这样可以利用索引加快排序查询时间。

经常用于连接的列上，这些列主要是一些外键，可以加快连接的速度；

作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

（2）不在哪些列建索引？

区分度不高的列。由于这些列的取值很少，例如性别，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。

在查询中很少的列不应该创建索引。由于这些列很少使用到，但增加了索引，反而降低了系统的维护速度和增大了空间需求。

当添加索引造成修改成本的提高 远远大于 检索性能的提高时，不应该创建索引。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。

定义为text, image和bit数据类型的列不应该增加索引。这些列的数据量要么相当大，要么取值很少。

1.3、 索引的分类：

（1）普通索引、唯一索引、主键索引、全文索引、组合索引。

普通索引：最基本的索引，没有任何限制

唯一索引：但索引列的值必须唯一，允许有空值，可以有多个NULL值。如果是组合索引，则列值的组合必须唯一。

主键索引：一种特殊的唯一索引，不允许有空值。

全文索引：全文索引仅可用于 MyISAM 表，并只支持从CHAR、VARCHAR或TEXT类型，用于替代效率较低的like 模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。

组合索引：主要是为了提高mysql效率，创建组合索引时应该将最常用作限制条件的列放在最左边，依次递减。

（2）聚簇索引与非聚簇索引：

如果按数据存储的物理顺序与索引值的顺序分类，可以将索引分为聚簇索引与非聚簇索引两类：

聚簇索引：表中数据存储的物理顺序与索引值的顺序一致，一个基本表最多只能有一个聚簇索引，更新聚簇索引列上的数据时，往往导致表中记录的物理顺序的变更，代价较大，因此对于经常更新的列不宜建立聚簇索引

非聚簇索引：表中数据的物理顺序与索引值的顺序不一致的索引组织，一个基本表可以有多个聚簇索引。

1.4、索引的数据结构：

常见的索引的数据结构有：B+Tree、Hash索引。

（1）Hash索引：MySQL中只有Memory存储引擎支持hash索引，是Memory表的默认索引类型。hash索引把数据以hash值形式组织起来，因此查询效率非常高，可以一次定位。

2、hash索引的缺点：

（1）Hash索引：

当创建组合索引时，不能只使用组合索引的部分列进行查询。因为hash索引是把多个列数据合并后再计算Hash值，所以对单独列数据计算Hash值是没有意义的。

当发生Hash碰撞时，Hash索引不能避免表数据的扫描。因为仅仅比较Hash值是不够的，需要比较实际的值以判定是否符合要求。

（2）B+Tree索引：

B+Tree是mysql使用最频繁的一个索引数据结构，是Innodb和Myisam存储引擎模式的索引类型。B+Tree索引在查找时需要从根节点到叶节点进行多次IO操作，在查询速度比不上Hash索引，但是更适合排序等操作。

B+Tree索引的优点：

页内节点不存储内容，每次IO可以读取更多的行，大大减少磁盘I/O读取次数

带顺序访问指针的B+Tree：B+Tree所有索引数据都存储在叶子结点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针，这样做是为了提高区间查询效率。

（3）为什么使用B+Tree作为索引：

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

局部性原理与程序预读：

由于磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页的整倍数。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

（2）B+Tree索引的性能分析：

上文说过一般使用磁盘I/O次数评价索引结构的优劣。我们先从B树分析，B树检索一次最多需要访问h个节点，同时，数据库巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，即每次新建节点时，直接申请一个页的空间，这样就保证一个节点在物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，这样就实现了每个节点只需要一次I/O就可以完全载入。B树中一次检索最多需要h-1次I/O（根节点常驻内存），时间复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小。综上所述，用B树作为索引结构效率是非常高的。

而红黑树这种结构，虽然时间复杂度也为O(h)，但是h明显要深的多，并且由于逻辑上很近的节点，在物理上可能很远，无法利用局部性，所以IO效率明显比B树差很多。

另外，B+Tree更适合作为索引的数据结构，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度d的上限取决于节点内key和data的大小，由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，磁盘IO的次数也就更少了。

（3）B+树索引 和 B树索引 的对比？

根据B-Tree 和 B+Tree的结构，我们可以发现B+树相比于B树，在文件系统或者数据库系统当中，更有优势，原因如下：

（1）B+树有利于对数据库的扫描：B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以范围查询、排序等操作，B+树有着更高的性能。

（2）B+树的磁盘IO代价更低：B+树的内部结点的data域并没有存储数据，因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说I/O读写次数也就降低了。

（3）B+树的查询效率更加稳定：由于B+树的内部结点只是叶子结点中关键字的索引，并不存储数据。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

（4）MySQL的 InnoDB 和 MyISAM 存储引擎中B+Tree索引的实现？

MyISAM和InnoDB都是使用B+树索引，MyISAM的主键索引和辅助索引的Data域都是保存行的地址，但是InnoDB的主键索引保存的不是行的地址，而是保存该行的所有所有数据，而辅助索引的Data域保存的则是主索引的值。

索引的长度限制：

对于 Innodb 的组合索引，如果各个列中的长度超过767字节的，则会对超过767字节的列取前缀索引；对于 Innodb 的单列索引，如果列的长度超过767的，则取前缀索引（取前255字符）

对于 MyISAM 的组合索引，所创建的索引长度和不能超过1000 bytes，否则会报错，创建失败；对于 MyISAM 的单列索引，最大长度也不能超过1000，否则会报警，但是创建成功，最终创建的是前缀索引（取前333个字符）