MySQL:索引如何加速查询执行

Question

我读过多篇关于MySQL索引的文章。下面是一些重要的页面：http://dev.mysql.com/doc/refman/5.6/en/mysql-indexes.html https://stackoverflow.com/questions/3567981/how-do-mysql-indexes-work

正确的是，使用索引的查询执行速度要快得多，因为不需要遍历所有记录。但是作为一个刚开始使用RDBMS的人，其他所有的列都依赖于确实的列。在有数千条记录的表中，系统需要首先遍历索引(一个接一个，按我不知道的任何定义顺序)。

为了避免大范围的描述，我把这个问题的范围限制在

• MySQL如何遍历索引？
• 索引的排列方式(B-树、散列等)已经下定决心了？
• 逐行遍历与遍历索引列值有什么区别？

Answer 1

这里你有一个浅谈索引的基本内部结构和内部工作。我建议你全看一遍。

基本上，索引是磁盘上的有序结构(尽管它们可以被缓存，并且通常会获得更好的性能)，这将允许更快地完成某些操作。特别是在MySQL中，B树/B+树(最常见的树)将允许您：

• 使用像a=3这样的条件执行更快的过滤，其中a是索引列。这是可能的，因为您可以使用较少的读取操作来定位为3的值。
• 获得有序的结果(按a排序)：由于索引中的值是有序的，在某些情况下，不需要使用排序算法重新排序，因为我们已经按照正确的顺序读取了它们
• 读取值而不访问整行(覆盖索引)：SELECT a ... WHERE a = 3;作为索引较小，读取的字节较少，操作减少，通常是缓存的，从而提高了读取性能。
• 加速某些操作，如max(a)或min(a)：优化器只需读取索引结构上的第一个或最后一个值

对于B-树，(看看这张幻灯片)，如果它正在查找值1，它只需要读取根节点。因为1在3之前，它知道它在左边的节点上。在一个步骤中，它丢弃了50%的读取。想象一下数百万节点的优势，它是指数级(或实际上，对数)更好。如果所有的行都必须读取，那么读取可能不会更快，事实上，它可能会更慢。这就是为什么当选择性很低时，MySQL拒绝使用索引并执行FULL TABLE SCAN。然而，即使在某些情况下，执行完整的索引扫描可能是一种优势(如果必须读取的数据总体上较少)，但它不会像我们执行高选择性过滤一样有效。

在哈希索引的情况下，优势来自于使用哈希表。在某些情况下，这可能会更快，但不能在所有情况下使用(例如，用于>或<比较)。MySQL上的主要引擎(InnoDB，MyISAM)不支持它，但它们在某些结构哈希映射中内部使用。

MySQL不会自动选择索引类型，它是在创建时间(ADD INDEX my_index (col_a, col_b) USING BTREE)上选择的，但默认为BTREE。

MySQL和其他DBRMSs也支持其他类型的索引，如R-树、全文、空间等。