Mysql探索之索引详解，又能和面试官互扯了

　　前言索引是什么？有什么利弊？一旦在面试中被问道，对于新入门的小白可能是个棘手的问题。本篇文章将会详细讲述什么是索引、索引的优缺点、数据结构等等常见的知识。什么是索引索引就是一种的数据结构，存储表中特定列的值并对值进行排序，所以是在表的列上面创建的。索引将通过缩小一张表中需要查询的记录的数目来加快搜索的速度。如果没有索引，数据库不得不进行全表扫描。索引就好比一本书的目录，它会让你更快的找到内容。索引的优点通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。可以大大加快数据的检索速度，避免进行全表的数据扫描，大大减少遍历匹配的行数，这也是创建索引的最主要的原因。可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。索引的缺点创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。在哪些列建立索引在经常需要搜索的列上，可以加快搜索的速度；在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。不在哪些列建索引？对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。对于那些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。对于那些定义为text，image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。索引的数据结构
　　常见的索引的数据结构有：BTree、Hash索引、FullText索引、RTree索引。Hash索引
　　1。概述：
　　MySQL中，只有Memory存储引擎支持Hash索引，是Memory表的默认索引类型。hash索引把数据的索引以hash值形式组织起来，因此检索效率非常高，可以一次定位，不像BTree索引需要进行从根节点到叶节点的多次IO操作。
　　2。Hash索引的缺点：
　　Hash索引仅仅能满足等值的查询，不能满足范围查询。因为数据在经过Hash算法后，其大小关系就可能发生变化。Hash索引不能被排序。同样是因为数据经过Hash算法后，大小关系就可能发生变化，排序是没有意义的。
　　Hash索引不能避免表数据的扫描。因为发生Hash碰撞时，仅仅比较Hash值是不够的，需要比较实际的值以判定是否符合要求。
　　Hash索引在发生大量Hash值相同的情况时性能不一定比BTree索引高。因为碰撞情况会导致多次的表数据的扫描，造成整体性能的低下，可以通过采用合适的Hash算法一定程度解决这个问题。
　　Hash索引不能使用部分索引键查询。因为当使用组合索引情况时，是把多个数据库列数据合并后再计算Hash值，所以对单独列数据计算Hash值是没有意义的。FullText索引
　　1。概述：
　　全文索引，目前MySQL中只有MyISAM存储引擎支持，并且只有char、varchar、text类型支持。它用于替代效率较低的like模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。
　　2。存储结构：
　　同样使用BTree存放索引数据，但使用的是特定的算法，将字段数据分割后再进行索引（一般每4个字节一次分割），索引文件存储的是分割前的索引字符串集合，与分割后的索引信息，对应Btree结构的节点存储的是分割后的词信息以及它在分割前的索引字符串集合中的位置。BTree索引BTree是mysql使用最频繁的一个索引数据结构，是Innodb和Myisam存储引擎模式的索引类型。相对Hash索引，B树在查找单条记录的速度比不上Hash索引，但是更适合排序等操作。
　　1。BTree索引的优点：带顺序访问指针的BTree：BTree所有索引数据都在叶子结点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。这样做是为了提高区间查询效率，例如查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。大大减少磁盘IO读取次数。BTree索引：文件系统及数据库系统普遍采用BTree作为索引结构：一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘IO消耗，相对于内存存取，IO存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘IO操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘IO的存取次数。局部性处理与磁盘预读由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘IO。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高IO效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。BTree索引的性能分析上文说过一般使用磁盘IO次数评价索引结构的优劣。先从BTree分析，根据BTree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次IO就可以完全载入。为了达到这个目的，在实际实现BTree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次IO。BTree中一次检索最多需要h1次IO（根节点常驻内存），渐进复杂度为O（h）O（logdN）。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。综上所述，用BTree作为索引结构效率是非常高的。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的IO渐进复杂度也为O（h），效率明显比BTree差很多。另外，BTree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小，由于BTree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。（详细见本部分第3点）BTree与BTree的对比根据BTree和BTree的结构，我们可以发现B树相比于B树，在文件系统或者数据库系统当中，更有优势，原因如下：
　　1。B树的磁盘读写代价更低
　　B树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
　　2。B树的查询效率更加稳定
　　由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
　　3。B树更有利于对数据库的扫描
　　B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的rangequery，B树有着更高的性能。MySQL索引的实现在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本部分主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引的实现
　　1。主键索引
　　MyISAM引擎使用BTree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
　　这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primarykey）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
　　2。辅助索引
　　在MyISAM中，主索引和辅助索引（Secondarykey）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
　　同样也是一颗BTree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照BTree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做非聚集的，之所以这么称呼是为了与InnoDB的聚集索引区分。InnoDB索引的实现虽然InnoDB也使用BTree作为索引结构，但具体实现方式却不相同。
　　1。主键索引
　　与MyISAM第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按BTree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
　　上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
　　2。辅助索引
　　第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
　　这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。InnoDB表是基于聚簇索引建立的。因此InnoDB的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引也会包含主键列，所以，如果主键使用过长的字段，将会导致其他辅助索变得更大。如果想在表上定义、很多索引，则争取尽量把主键定义得小一些。InnoDB不会压缩索引。