索引的主要作用就是告诉存储引擎如何快速找到我们所需要的数据,它是一种数据结构。MySQL的索引是在存储引擎层实现的，而不是在服务器层实现的，这就决定了不同的存储引擎的工作方式可能是不同的，同时也不是所有的存储引擎都支持所有的索引类型。即使是同一种索引在不同的存储引擎上其底层实现也不一定相同。

BTree索引

Btree索引以B+树这种数据结构
B+树数据结构

只有叶子节点才保存真正的信息（相关表的行位置），在索引的根节点中存放了指向下层子节点的指针，存储引擎根据指针向下层进行查找。通过比较节点的值和要查找的值就可以得到合适的指针进入到下层子节点，而这些指针实际上是定义了子节点中值得上下限。叶子节点的指针指向的是被索引的数据而不是其他的叶子节点。在InnoDB中，叶子节点指向的是主键，在MyISAM中，叶子节点指向数据的物理地址。

在DB中增加或者删除一行会导致B+树改变，B+树需要自我整理和自我平衡。B+树中插入和删除操作都是O(log(N))，所以添加过多索引减缓了快速插入、更新或者删除表中的某一行的操作，因为数据库要以昂贵的代价(O(log(N)))来更新索引

BTree索引可以帮助我们进行排序以避免使用磁盘临时表带来的IO消耗。

能够把随机IO变为顺序IO。

为什么使用BTree

红黑树其实也是能实现索引的，但是文件系统和DBMS普遍采用BTree作为索引结构的主要原因如下：

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

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

image.png

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个4 x 4的主存模型。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

磁盘整体结构

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）

磁盘结构

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理和磁盘预读

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

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小

适用范围

BTree索引适合范围查找，因此它的使用场景如下：

  1. 全值匹配的查询。例如：我们在订单号order_sn上建立的索引，然后查询编号为98763478976的订单记录。
  2. 匹配最左前缀的查询。如果我们在order_sn上并没有建立索引，而是建立了order_sn和order_date两个字段上的联合索引，对于查询订单编号为98763478976的记录，我们同样可以利用这个联合索引，也就是说如果联合索引的第一列符合查询条件，这个索引就会被用到，但是如果只是这个联合索引的第二列符合条件就无法利用索引，例如：查询order_date为2016-07-08的记录就无法利用到索引。
  3. 匹配列前缀的查询。例如：order_sn like 9876%匹配列前缀的查询。
  4. 匹配范围值得查询。order_sn>9888343243 and order_sn < 9999999999。
  5. 精确匹配左前列并范围匹配另外一列。例如联合索引order_sn和order_date。精确匹配order_sn并范围匹配order_date。
  6. 只访问索引的查询。也称为覆盖索引，查询只需要访问索引不需访问数据行。

使用限制

  1. 如果不是按照索引的最左列开始查找的，则无法使用索引。联合索引order_sn和order_date，如果我们只把订单日期作为查询条件，就无法使用这个联合索引。
  2. 使用索引的时候不能跳过索引中的列。例如：order_date,name,tel 3列组成的联合索引，如果我们在查找中只包含order_date和tel,那么对于这个查询来说就只能使用到order_date这一列来进行查询过滤而无法使用到tel，因为我们在查询条件中跳过了name这一列。
  3. NOT IN和<>无法使用索引。
  4. 如果查询中有某个列的范围查询，则其右边的所有列都无法使用索引。

Hash索引

Hash索引基于hash表，只有查询条件精确匹配hash索引中的所有列时，才能够使用到hash索引。也就是说hash索引只能用在等值查询中。对于hash索引中的每一列，存储引擎都会为每一行计算出一个hash码，hash索引中存储的就是hash码

使用hash索引需要进行2次查找，无法用于排序，不支持部分索引，不支持范围查找，有可能产生hash冲突（不同列产生的hash码是相同的），例如性别列就不能使用hash索引，身份证号列上建立hash索引比较合适。

Q:为什么索引能够减少存储引擎需要扫描的数据量？
A:索引列的大小通常会远小于数据列的大小。以InnoDB来说：InnoDB发生一次IO，最小的单位是页（默认16K），一页内存储的信息越多，效率越高。相比存储数据，一页内能够存储更多的索引。通过索引进行查询需要读取的页的数量少，减少需要扫描的数据量。

索引并不是越多越好。索引会增加写操作的成本，为了解决这个问题InnoDB采用了插入缓存能够将多次插入合并为1次插入。太多的索引也会增加查询优化器的选择时间。

安装演示DB

MySQL演示数据库sakila

1
2
$ mysql -uroot -p123456 < sakila-schema.sql
$ mysql -uroot -p123456 < sakila-data.sql

索引优化策略

索引的选择性指的是不重复的索引值和表的记录数的比值，由此可见主键和唯一索引的选择性最高。选择性越高，效率越高。

索引列上不能使用表达式或者函数

使用索引的一个常见误区就是对表的每一列都建立索引。我们可以使用联合索引，联合索引列的顺序至关重要：

  1. 经常被用到的列优先
  2. 选择性高的列优先
  3. 宽度小的列优先

包含了查询字段的全部值得索引被称为覆盖索引。覆盖索引可以避免对InnoDB主键索引的二次查询，避免对MyISAM表进行系统调用。覆盖索引也有以下的限制：查询中使用了太多的列(select * 无法使用覆盖索引)；存储引擎不支持覆盖索引；使用了双%的like查询。

使用演示数据库sakila进行以下的查询计划：

MySQL覆盖索引

注意到在上图中，select * 无法使用到覆盖索引。

使用索引来优化排序

使用索引优化排序
使用索引排序

在上面的右图中如果我们将查询计划改为：explain select * from rental where rental_date='2005-01-01' order by inventory_id desc,customer_id\G;那么在Extra将会变为：“Extra: Using index condition; Using filesort”，因为它违反了使用索引进行优化的第二条规则。

使用Btree索引模拟hash索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
mysql> alter table film add title_md5 char(32);
mysql> update film set title_md5=md5(title);
mysql> create index idx_md5 on film(title_md5);
mysql> explain select * from film where title_md5=md5('EGG IGBY') and title='EGG IGBY'\G; -- 由于MD5可能hash冲突，所以还需要使用title='EGG IGBY'进行过滤
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: film
   partitions: NULL
         type: ref
possible_keys: idx_title,idx_md5
          key: idx_title
      key_len: 767
          ref: const
         rows: 1
     filtered: 5.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

利用索引优化锁

索引可以减少锁定的行数和加快数据的处理速度，同时加快锁的释放。

1
mysql> drop index idx_actor_last_name on actor;

开2个session，使用事务，发现session2被阻塞了：
MySQL锁
使用索引优化锁

索引的维护和优化

MySQL允许在同一列上创建多个索引，但是过多的索引将会冗余，例如：
冗余索引

一种常见的误区就是认为UNIQUE KEY是唯一约束，很多人错误地为它建立了索引。

确定冗余和重复的索引可以采用pt-duplicate-key-checker

MySQL查询优化器可以通过索引的统计信息来制定合适的查询策略。如果索引的统计信息不当就会影响查询的性能。可以通过analyze table table_name。BTree索引进行更新的是偶可能会产生大量的碎片，碎片化的索引可能会以无序的方式存储在磁盘上，除了索引，表也会产生碎片，我们需要定期对表进行维护（optimize table table_name,需要注意的是使用不当会锁表）。

参考资料