聚簇索引(InnoDB)快还是非聚簇(MyISAM)索引快

一个朋友问我聚簇索引快还是非聚簇索引快呢？这个问题其实很难回答，也很难进行一个实际的测试来判断到底哪个快，除了聚簇索引和非聚簇索引在原理上的不同，实际上一个存储引擎的索引快慢还受其实现方法和功能的影响，比如，事物，锁，高并发，存储策略，缓存策略等，本文就简单的从理论上进行分析，根据索引的实现原来来推敲一下到底哪种索引类型更快，最后会通过一个压测实例来验证理论分析结果的合理性。

关于B+树索引的实现原理请参考我转载的文章《MySQL索引背后的数据结构及算法原理》：http://cloudate.net/?p=459

如果上文太长你没时间看，那这里就简单的介绍下索引的原理，顾名思义，索引类似目录信息，通过这个目录可以帮助你快速的找到你想要找的信息，例如图书馆里书架上图书分类信息，例如一本书的目录等，其实都是索引。

现在回到数据库领域，索引是什么，索引就是记录了你保存的数据位置的信息，并且可以通过这些信息可以快速的找到你想要的数据。

当你保存一条记录到数据库，数据库会顺序的保存这些记录到磁盘上，当你查找一条记录的时候你可以从头到尾遍历所有记录，然后检查哪条记录是符合标准的，返回符合标准的记录，然而，久而久之记录的数量变大，占用的磁盘空间也变大，当技术数量达到一定的量级，遍历一次全量数据集合时间的成本是可想而知的，这需要大量的顺序IO，而且每次IO能够读取的数据量是有限的，全量集合进行的大量顺序IO所带来的时间成本将是不可接受的，因此在一张表的数据量超过几百几千行，全表扫描的速度就难以接受了，这时索引就派上用场了。

为了解决大数据量下快速的查找一条记录，我们就需要有索引，最容易想到的就是利用hash建立索引，把每条记录的关键字进行hash然后构建hash表，这样可以在O(1)的时间复杂度下查找到某一条记录，然而，hash索引只能查找单值的关键字，对于范围查找无能为力，于是我们就想到另外一个高效的查找数据结构，二插树，二插树具有Log2N的查找速度，但是，我们需要把整个二插树都加载到内存中，内存显然是存不下的，如果访问磁盘次数在Log2N的复杂度那就太慢了，于是在二插树的基础上衍生了一种神奇的B+树，B+树作为索引可以将大量的顺序IO转换成少量的随机IO，一般B+树有4层，跟节点常驻内存，也就是最多进行3次随机IO即可找到一个节点，公式如下，

O(h)=O(logdN)

一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

因此，对于一个有索引的表来说，查找一条数据需要经过下面的2步：

1. 在B+树中通过某条记录的键值查找记录地址，最多需要3 次随机IO。
2. 通过记录地址在磁盘中查找某条记录的数据返回，需要1次随机IO。

也就是把大量的顺序IO，转化成最多4次的随机IO，顺序IO次数取决于表的实际大小，这就是B+索引的神奇之处。

在了解了索引的原理之后，现在来看一下什么是非聚簇索引和聚簇索？

如上所述，索引和数据分开存储，数据是按照顺序存储在磁盘上，索引则是通过B+树存储在磁盘上，并且主键和辅助索引都采取这种方式，叫做非聚簇索引。

那么什么叫聚簇索引呢？顾名思义，聚簇代表着数据存储在一起，也就是数据存储在索引结构里，和结构耦合在一起，也就是在主键B+树中存储不再是记录的地址，而是记录数据本身，所以叫做聚簇索引，提到这里，有的同学会问，那辅助索引怎么办？辅助索引只能存储主键了，这样通过主键来查找一条记录，那么进行最多3次随机IO即可，不需要到磁盘中读取记录，在索引中直接可以找到数据，然后对于辅助索引来说，则需要最多6次随机IO才能找到一条记录。

总结

1. 非聚簇索引通过主键和候选键查找，索引查找需要4次随机IO，数据查找需要1次随机IO，最多4次随机IO即可找到一条记录。
2. 聚簇索引通过主键查找，只需要查找主键索引，最多需要3次随机IO即可找到一条记录。
3. 聚簇索引通过候选键查找，即需要查找辅助索引，又需要查找主键索引，最多需要6次随机IO可以找到一条记录。

因此，我们不能简单的说聚簇索引快还是非聚簇索引快，这取决于使用主键查找还是候选键进行查找，如果使用主键，聚簇索引更快些，如果使用候选键查找，则非聚簇索引更快些。

在Mysql中，MyISAM使用非聚簇索引，InnoDB使用聚簇索引，那是不是InnoDB的主键查询就一定比MyISAM的查询要快呢？是不是MyISAM的辅助索引查询会比InnoDb的辅助索引查询要快呢？

非也非也，看看下面我的压测结果：

本测试用例运行在硬件和软件环境：Dell Latitude, 4 core CPU * 2G, 4G Memory, mysql 5.5.38。

在测试准备阶段创建了2张表，1张使用MyISAM存储引擎，另外1张表使用InnoDB存储引擎，脚本如下：

drop table test_myisam;
CREATE TABLE `test_myisam` (
  `id` bigint unsigned auto_increment,
  `ext_id` bigint unsigned,
  `col` bigint unsigned,
  PRIMARY KEY (`id`),
  INDEX ext_id_idx (ext_id)
) ENGINE=MyISAM;
drop table test_innodb;
CREATE TABLE `test_innodb` (
  `id` bigint unsigned auto_increment,
  `ext_id` bigint unsigned,
  `col` bigint unsigned,
  PRIMARY KEY (`id`),
  INDEX ext_id_idx (ext_id)
) ENGINE=InnoDB;

另外，使用如下脚本在各个表中插入80万条的记录：

#!/bin/bash
for((i=1;i<=800000;i++));do 
  echo test_myisam:$i
  mysql -uroot -Dtest -e "insert into test_myisam (ext_id, col) values($i, $i)"; 
done
for((i=1;i<=800000;i++));do 
  echo test_innodb:$i
  mysql -uroot -Dtest -e "insert into test_innodb (ext_id, col) values($i, $i)"; 
done

压测结果如下：

robert@robert-Latitude-E6440:~/桌面/myisam vs. innodb$ mysqlslap -hlocalhost -P3306 --concurrency=100 --iterations=10 --create-schema='test' --query='select * from test_myisam where  id = 1000;' --number-of-queries=10000 --debug-info --verbose -uroot
Benchmark
Average number of seconds to run all queries: 0.196 seconds
Minimum number of seconds to run all queries: 0.191 seconds
Maximum number of seconds to run all queries: 0.202 seconds
Number of clients running queries: 100
Average number of queries per client: 100
User time 0.50, System time 0.70
Maximum resident set size 4804, Integral resident set size 0
Non-physical pagefaults 6257, Physical pagefaults 0, Swaps 0
Blocks in 0 out 0, Messages in 0 out 0, Signals 0
Voluntary context switches 156832, Involuntary context switches 910
robert@robert- Latitude-E6440:~/桌面/myisam vs. innodb$ mysqlslap -hlocalhost -P3306 --concurrency=100 --iterations=10 --create-schema='test' --query='select * from test_innodb where  id = 1000;' --number-of-queries=10000 --debug-info --verbose -uroot
Benchmark
Average number of seconds to run all queries: 0.199 seconds
Minimum number of seconds to run all queries: 0.191 seconds
Maximum number of seconds to run all queries: 0.212 seconds
Number of clients running queries: 100
Average number of queries per client: 100
User time 0.51, System time 0.69
Maximum resident set size 4968, Integral resident set size 0
Non-physical pagefaults 6331, Physical pagefaults 0, Swaps 0
Blocks in 0 out 0, Messages in 0 out 0, Signals 0
Voluntary context switches 158774, Involuntary context switches 924
robert@robert- Latitude-E6440:~/桌面/myisam vs. innodb$ mysqlslap -hlocalhost -P3306 --concurrency=100 --iterations=10 --create-schema='test' --query='select * from test_myisam where  ext_id = 1000;' --number-of-queries=10000 --debug-info --verbose -uroot
Benchmark
Average number of seconds to run all queries: 0.283 seconds
Minimum number of seconds to run all queries: 0.275 seconds
Maximum number of seconds to run all queries: 0.311 seconds
Number of clients running queries: 100
Average number of queries per client: 100
User time 0.48, System time 0.74
Maximum resident set size 3408, Integral resident set size 0
Non-physical pagefaults 6300, Physical pagefaults 4, Swaps 0
Blocks in 208 out 0, Messages in 0 out 0, Signals 0
Voluntary context switches 148780, Involuntary context switches 733
robert@robert- Latitude-E6440:~/桌面/myisam vs. innodb$ mysqlslap -hlocalhost -P3306 --concurrency=100 --iterations=10 --create-schema='test' --query='select * from test_innodb where  ext_id = 1000;' --number-of-queries=10000 --debug-info --verbose -uroot
Benchmark
Average number of seconds to run all queries: 0.261 seconds
Minimum number of seconds to run all queries: 0.248 seconds
Maximum number of seconds to run all queries: 0.291 seconds
Number of clients running queries: 100
Average number of queries per client: 100
User time 0.44, System time 0.78
Maximum resident set size 3320, Integral resident set size 0
Non-physical pagefaults 6343, Physical pagefaults 0, Swaps 0
Blocks in 0 out 0, Messages in 0 out 0, Signals 0
Voluntary context switches 153573, Involuntary context switches 740

根据上面压测结果，MyISAM和InnoDB主键索引和辅助索引在查找的性能上表现基本相当，和之前理论分析结果有些出入，这是因为索引的实现原理虽然不同，但是由于一个存储引擎需要实现更多的功能和特点，例如，事物，锁等，因此可能导致一些性能的波动，因此InnoDB聚簇索引的优点并不能在这个测试用例中得以体现，另一方面，当前的测试用例每次查询同一条记录，这样另压测难以验证之前的理论分析。

长按下面二维码关注更多云时代架构文章！