泽民博客 ☰ Menu

InnoDB与MyISAM 聚集索引与非聚集索引

索引（Index）是帮助MySQL高效获取数据的数据结构。MyISAM和Innodb都使用了B+树这种数据结构做为索引。



数据库索引好比是一本书前面的目录，能加快数据库的查询速度。索引分为聚簇索引和非聚簇索引两种，在一个表中只能有一个聚集索引，一般以主键作为聚集索引，而非聚集索引可以有多个。

Innodb引擎
Innodb引擎提供了对数据库ACID事务的支持，并且实现了SQL标准的四种隔离级别。该引擎还提供了行级锁和外键约束，它的设计目标是处理大容量数据库系统，它本身其实就是基于MySQL后台的完整数据库系统，MySQL运行时Innodb会在内存中建立缓冲池，用于缓冲数据和索引。但是该引擎不支持FULLTEXT类型的索引，而且它没有保存表的行数，当SELECT COUNT(*) FROM TABLE时需要扫描全表。当需要使用数据库事务时，该引擎当然是首选。由于锁的粒度更小，写操作不会锁定全表，所以在并发较高时，使用Innodb引擎会提升效率。但是使用行级锁也不是绝对的，如果在执行一个SQL语句时MySQL不能确定要扫描的范围，InnoDB表同样会锁全表。



MyIASM引擎
MyIASM是MySQL默认的引擎，但是它没有提供对数据库事务的支持，也不支持行级锁和外键，因此当INSERT(插入)或UPDATE(更新)数据时即写操作需要锁定整个表，效率便会低一些。不过和Innodb不同，MyIASM中存储了表的行数，于是SELECT COUNT(*) FROM TABLE时只需要直接读取已经保存好的值而不需要进行全表扫描。如果表的读操作远远多于写操作且不需要数据库事务的支持，那么MyIASM也是很好的选择。



两种引擎的选择
大尺寸的数据集趋向于选择InnoDB引擎，因为它支持事务处理和故障恢复。数据库的大小决定了故障恢复的时间长短，InnoDB可以利用事务日志进行数据恢复，这会比较快。主键查询在InnoDB引擎下也会相当快，不过需要注意的是如果主键太长也会导致性能问题，关于这个问题我会在下文中讲到。大批的INSERT语句(在每个INSERT语句中写入多行，批量插入)在MyISAM下会快一些，但是UPDATE语句在InnoDB下则会更快一些，尤其是在并发量大的时候。



Mysql的存储引擎和索引
 可以说数据库必须有索引，没有索引则检索过程变成了顺序查找，O(n)的时间复杂度几乎是不能忍受的。我们非常容易想象出一个只有单关键字组成的表如何使用B+树进行索引，只要将关键字存储到树的节点即可。当数据库一条记录里包含多个字段时，一棵B+树就只能存储主键，如果检索的是非主键字段，则主键索引失去作用，又变成顺序查找了。这时应该在第二个要检索的列上建立第二套索引。  这个索引由独立的B+树来组织。



有两种常见的方法可以解决多个B+树访问同一套表数据的问题，一种叫做聚簇索引（clustered index ），一种叫做非聚簇索引（secondary index）。这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。对于聚簇索引存储来说，行数据和主键B+树存储在一起，辅助键B+树只存储辅助键和主键，主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说，主键B+树在叶子节点存储指向真正数据行的指针，而非主键。



        InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上，若使用”where id = 14”这样的条件查找主键，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。若对Name列进行条件搜索，则需要两个步骤：第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。



        MyISM使用的是非聚簇索引，非聚簇索引的两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。



因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。并且和MyISAM不同，InnoDB的辅助索引数据域存储的也是相应记录主键的值而不是地址，所以当以辅助索引查找时，会先根据辅助索引找到主键，再根据主键索引找到实际的数据。所以Innodb不建议使用过长的主键，否则会使辅助索引变得过大。建议使用自增的字段作为主键，这样B+Tree的每一个结点都会被顺序的填满，而不会频繁的分裂调整，会有效的提升插入数据的效率。



        为了更形象说明这两种索引的区别，我们假想一个表如下图存储了4行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

 我们重点关注聚簇索引，看上去聚簇索引的效率明显要低于非聚簇索引，因为每次使用辅助索引检索都要经过两次B+树查找，这不是多此一举吗？聚簇索引的优势在哪？



        1 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。



        2 辅助索引使用主键作为”指针” 而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个”指针”。也就是说行的位置（实现中通过16K的Page来定位，后面会涉及）会随着数据库里数据的修改而发生变化（前面的B+树节点分裂以及Page的分裂），使用聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。
        
        2. 聚集索引（clustered index）
聚集索引决定数据在磁盘上的物理排序，一个表只能有一个聚集索引，一般用primary key来约束。



举例：t_user表里面的uid上的索引是聚集索引。



Top



  1. 非聚集索引（non-clustered index）
    它并不决定数据在磁盘上的物理排序，索引上只包含被建立索引的数据，以及一个行定位符row-locator，这个行定位符，可以理解为一个聚集索引物理排序的指针，通过这个指针，可以找到行数据。



举例：select uid from t_user where age > 18 and age < 26;age上建立的索引，就是非聚集索引。



Top



  1. 联合索引
    多个字段上建立的索引，能够加速复合查询条件的检索



举例：select uid,login_time from t_user where login_time=? and passwd=?;可以建立（login_name, passwd）的联合索引。











联合索引能够满足最左侧查询需求，例如（a,b,c）三列的联合索引，能够加速a (a,b) (a,b,c)三组查询需求。


这也就是为何不建立（passwd,login_time）这样联合索引的原因，业务上几乎没有passwd的单条件查询需求，而有很多login_name的单条件查询需求。



select uid, login_time from t_user where passwd=? and login_name=?



能否命中（login_time，passwd）这个联合索引。



可以，最左侧查询需求，并不是指SQL语句的写法必须满足索引的顺序。



Top



  1. 索引覆盖
    被查询的列，数据能从索引中取得，而不是通过行定位符row-locator再到row上获取，即“被查询列要被所建的索引覆盖”，这能够加速查询速度。



select uid, login_time from t_user where login_time=? and passwd=?



可以建立（login_name,passwd,login_time）的联合索引，由于login_time已经建立在索引中了，被查询的uid和login_time就不用去row上获取数据了，从而加速查询。



一个问题
有一张表test，这张表除了主键id外，还有a，b, c 三列



假设给这三个字段建一个复合索引 index_abc (a, b, c)，问，下面几种查询中，哪种查询会用到索引 index_abc ？




  1. 查询一



select * from test where a > 1000 and b > 1000;



  1. 查询二



select * from test where a > 1000 and c > 1000；



  1. 查询三



select * from test where b > 1000 and c > 1000;



这是一个经典的面试题，由这个问题，我可以相关问你，什么是 左匹配原则？什么是 聚集索引？什么是 索引覆盖？什么是 回表？



下面给大家捋一捋，以下试验基于MySQL5.7-InnoDB



左匹配原则
接着上面的问题，回到刚刚的三个查询上，首先，我们怎么知道查询有没有用到索引？有没有什么命令是可以帮助我们分析查询语句呢？答案当然是有的，那就 explain 命令



我们分别对上面的语句进行 explain，看看有哪些信息：



复制代码
mysql> explain select * from test where a > 1000 and b > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| 1 | SIMPLE | test | NULL | range | index_abc | index_abc | 4 | NULL | 5060 | 33.33 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+



mysql> explain select * from test where a > 1000 and c > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| 1 | SIMPLE | test | NULL | range | index_abc | index_abc | 4 | NULL | 5060 | 33.33 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+



mysql> explain select * from test where b > 1000 and c > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
| 1 | SIMPLE | test | NULL | index | NULL | index_abc | 12 | NULL | 10120 | 11.11 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
复制代码



我们可以看到，对查询语句执行 explain 后，返回了12列信息，各列说明如下：



Cloumn Meaning
id 查询标识符
select_type 查询类型
table 输出行的表
partitions 匹配的分区
type 联接类型，确切的说是一种数据库引擎查找表的一种方式
possible_keys 可以选择的可能索引，但不一定被查询实际使用
key 实际选择的索引
key_len 所选键的长度
ref 与索引相比的列
rows 估计要查询的列
filtered 按表条件筛选的行百分比
Extra 其他信息
通常分析sql语句，我们只关注type，possible_keys，key，rows



对三条查询语句进行explain后，我们发现：



where a > 1000 and b > 1000 和 where a > 1000 and c > 1000条件的查询 结果是一样的，其中type指明的索引查找方式为range，possible_keys 可能使用的索引为 index_abc，key 实际使用的索引为 index_abc
where b > 1000 and c > 1000 条件的查询中，type的值为index，possible_keys为NULL，key的值为 index_abc



上面的range 和 index有什么区别呢？



range：仅检索给定范围内的行，使用索引选择行
index：索引联接类型与 ALL 相同，只不过扫描索引树，有两种情况：
如果索引是查询的 覆盖索引（后文有讲），并且可用于满足表中所需的所有数据，则仅扫描索引树。在这种情况下，”额外”（Extra）列表示使用索引。 仅索引扫描通常比全部扫描快，因为索引的大小通常小于表数据
使用索引中的读取执行完整的表扫描，以按索引顺序查找数据行。使用索引不显示在”额外”列中，也就是说：如果不是覆盖索引，使用索引不显示在”额外”列中
换句话说，



range是使用了索引，并且能够在对应的索引树上使用快速查找的方法进行快速查找，是有范围的查找，使用了range，就一定用到了我们建的索引，而index只能是通过扫描整个索引树



上面也提到ALL，那么type还有哪几种比较常见的值呢？下面列举一下（具体其他类型值，看以参考官方文档）：



system：该表只有一行 （= 系统表）。这是 const 联接类型的特殊情况
const：表示通过索引一次就找到了，因为只匹配一行数据，所以很快。如将主键置于where列表中，MySQL就能将该查询转换为一个常量表最多有一个匹配行，在查询开始时读取该行。由于只有一行，因此优化器的其余部分可以将该行中的列中的值视为常量。将主键或 UNIQUE 索引的所有部分与常量值进行比较时，将使用 const
eq_ref：唯一性索引扫描，对于前一表中的每一行组合，将从此表中读取一行，常见于主键或唯一索引扫描。除了system 和 const 类型之外，这是最佳联接类型
ref：非唯一性索引扫描，对于前一表中的每一行组合，将从此表中读取具有匹配索引值的所有行
ALL：将遍历全表以找到匹配的行
好，回到上面三条查询语句上，为什么where条件为a > 1000 and b > 1000 和 a > 1000 and c > 1000 的 type 是 range（用到索引）, 而where条件为 b > 1000 and c > 1000 的 type 是 index 呢？这里面索引树（B+树）的构建方式及存储结构有关



那么复合索引B+树是怎样的呢？看图，一图胜百字



​



对于索引来说只不过比单值索引多了几列，而这些索引列全都出现在索引树上。对于复合索引，存储引擎会首先根据第一个索引列排序，如上图我们可以单看第一个索引列，如，1 1 4 15 18….他是单调递增的；如果第一列相等则再根据第二列排序，依次类推就构成了上图的索引树



以创建的索引 index_abc (a, b, c)为例，如上图所示，每个结点都有三个键值，从上往下分别对应这a，b，c三个索引列



构造索引树时，首先使用多列索引的第一列构建的索引树，以 index_abc (a, b, c) 为例就是优先使用a列构建，当b列值相等时再以c列排序



因此，索引的第一列也就是a列可以说是从左到右单调递增的，但我们看b列和c列并没有这个特性，它们只能在a列值相等的情况下这个小范围内递增，看上图的左下角的结点可理解这点



划重点：由于复合索引树建的时候就是按照当初你建立索引时（index_abc (a, b, c)）对应索引列的顺序从左到右来建的，因此你使用的时候你也得按照从左到右的规则来用，这就是索引的 左匹配原则



所以为什么上面 where a > 1000 and b > 1000 和 where a > 1000 and c > 1000 条件查询的type是range，而 where b > 1000 and c > 1000 的type是index 你明白来吗？



回表，聚集索引
我们都知道，B+树有个特点就是，其叶子结点存的是关键字和数据，非叶子结点存的都是索引关键字，那么复合索引构造的B+树中，其叶子结点存的数据是什么呢？答案该条数据的主键值



划重点：也就是说，利用复合索引查找数据的流程是，先在复合索引的B+树上找到对应数据的主键值（ID，注：MyISAM的索引叶子节点存储记录指针）,然后再根据这个主键（ID）值，到主键索引树（B+树）上查找这个ID所在的行记录（主键索引树的页子结点存储的关键字和对应的行记录数据），最后查找结束。这个查找流程操作也叫 回表查询



有没有注意到，B+树中，有的叶子结点存储的行记录，有点存储的是主键值



划重点：



叶子结点存储行记录的索引又叫 聚集索引，InnoDB必须要有，且只有一个聚集索引：
如果定义了主键，则主键索引就是 聚集索引
如果没有定义主键，则第一个not NULL unique列是聚集索引
否则，InnoDB会创建一个隐藏的row-id作为聚集索引
叶子结点存储主键值叫普通索引，也叫 非聚集索引



覆盖索引
还是上面的例子，我们再次看一下 where条件为 b > 1000 and c > 1000 的查询 explain后的信息



复制代码
mysql> explain select * from test where b > 1000 and c > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
| 1 | SIMPLE | test | NULL | index | NULL | index_abc | 12 | NULL | 10120 | 11.11 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——-+———-+————————–+
复制代码



按照我们刚刚讲的索引的 左匹配原则，这个查询应该没有有效用上我们建的索引 index_abc ，为什么key（实际使用到的索引）列却是 index_abc？这里就涉及到了 覆盖索引



什么是覆盖索引？覆盖索引 就是：SQL只需要通过索引就可以返回查询所需要的数据，而不必通过二级索引查到主键之后再去查询数据（即回表查询）



不难理解，因为我们的test表本来就只有四个字段，id, a, b, c，其中（a, b, c）建立列索引，id又是主键，复合索引树的叶子结点存的就是主键值，所以 select * from test where b > 1000 and c > 1000 查找的数据通过复合索引树就可以全部得到，不需要回表，因此这里面用到了索引，这个索引树实际是什么索引的索引树呢？，当然是index_abc了，因为b, c 列包含在复合索引列中



为什么possible_keys列（可能使用到的索引）为NULL，因为搜索引擎找不到以b列开头的索引



所以，使用列索引覆盖，Extra列也就有列Using index



最后，为什么 a > 1000 and b > 1000 和 b > 1000 and a > 1000，explain的结果一样呢？



复制代码
mysql> explain select * from test where a > 1000 and b > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| 1 | SIMPLE | test | NULL | range | index_abc | index_abc | 4 | NULL | 5060 | 33.33 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+



mysql> explain select * from test where b > 1000 and a > 1000;
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
| 1 | SIMPLE | test | NULL | range | index_abc | index_abc | 4 | NULL | 5060 | 33.33 | Using where; Using index |
+—-+————-+——-+————+——-+—————+———–+———+——+——+———-+————————–+
复制代码
这就该我们mysql 查询优化器 干活了，mysql查询优化器会判断纠正这条sql语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划。



B-Tree介绍
B-Tree是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）



B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；



B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；



B+Tree介绍
B+树是B-树的变体，也是一种多路搜索树：



   1.其定义基本与B-树同，除了：



   2.非叶子结点的子树指针与关键字个数相同；



   3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；



   5.为所有叶子结点增加一个链指针；



   6.所有关键字都在叶子结点出现；



   如：（M=3）


B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；



   B+的特性：



   1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；



   2.不可能在非叶子结点命中；



   3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；



   4.更适合文件索引系统；


mysql中的索引



mysql中普遍使用B+Tree做索引，但在实现上又根据聚簇索引和非聚簇索引而不同。



聚簇索引
所谓聚簇索引，就是指主索引文件和数据文件为同一份文件，聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身，key为主键，如果是一般索引的话，data便会指向对应的主索引，如下图所示：



在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。



非聚簇索



非聚簇索引就是指B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址。主索引和辅助索引没啥区别，只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中，如下图：



非聚簇索引比聚簇索引多了一次读取数据的IO操作，所以查找性能上会差。



MyisAM索引与InnoDB索引相比较
MyisAM支持全文索引（FULLTEXT）、压缩索引，InnoDB不支持；
InnoDB支持事务，MyisAM不支持；
MyisAM顺序储存数据，索引叶子节点保存对应数据行地址，辅助索引很主键索引相差无几；InnoDB主键节点同时保存数据行，其他辅助索引保存的是主键索引的值；
MyisAM键值分离，索引载入内存（key_buffer_size），数据缓存依赖操作系统；InnoDB键值一起保存，索引与数据一起载入InnoDB缓冲池；MyisAM主键（唯一）索引按升序来存储存储，InnoDB则不一定
MyisAM索引的基数值（Cardinality，show index 命令可以看见）是精确的，InnoDB则是估计值。这里涉及到信息统计的知识，MyisAM统计信息是保存磁盘中，在alter表或Analyze table操作更新此信息，而InnoDB则是在表第一次打开的时候估计值保存在缓存区内；
MyisAM处理字符串索引时用增量保存的方式，如第一个索引是‘preform’，第二个是‘preformence’，则第二个保存是‘7，ance’，这个明显的好处是缩短索引，但是缺陷就是不支持倒序提取索引，必须顺序遍历获取索引
为什么选用B+/-Tree
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。



简单点说说内存读取，内存是由一系列的存储单元组成的，每个存储单元存储固定大小的数据，且有一个唯一地址。当需要读内存时，将地址信号放到地址总线上传给内存，内存解析信号并定位到存储单元，然后把该存储单元上的数据放到数据总线上，回传。



写内存时，系统将要写入的数据和单元地址分别放到数据总线和地址总线上，内存读取两个总线的内容，做相应的写操作。



内存存取效率，跟次数有关，先读取A数据还是后读取A数据不会影响存取效率。而磁盘存取就不一样了，磁盘I/O涉及机械操作。磁盘是由大小相同且同轴的圆形盘片组成，磁盘可以转动(各个磁盘须同时转动)。磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不动，磁盘转动，但磁臂可以前后动，用于读取不同磁道上的数据。磁道就是以盘片为中心划分出来的一系列同心环(如图标红那圈)。磁道又划分为一个个小段，叫扇区，是磁盘的最小存储单元。



磁盘读取时，系统将数据逻辑地址传给磁盘，磁盘的控制电路会解析出物理地址，即哪个磁道哪个扇区。于是磁头需要前后移动到对应的磁道，消耗的时间叫寻道时间，然后磁盘旋转将对应的扇区转到磁头下，消耗的时间叫旋转时间。所以，适当的操作顺序和数据存放可以减少寻道时间和旋转时间。
为了尽量减少I/O操作，磁盘读取每次都会预读，大小通常为页的整数倍。即使只需要读取一个字节，磁盘也会读取一页的数据(通常为4K)放入内存，内存与磁盘以页为单位交换数据。因为局部性原理认为，通常一个数据被用到，其附近的数据也会立马被用到。



B-Tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率也就上去了。



B+Tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，I/O操作更少了。所以B+Tree拥有更好的性能。



在MySQL中，主要有四种类型的索引，分别为：B-Tree索引，Hash索引，Fulltext索引(MyISAM 表)和R-Tree索引，本文讲的是B-Tree索引。



后面的索引原理一定要看，太重要了，阿里两个人都问这个mysql的索引原理



mysql使用了 B+索引：



B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；



一、Mysql索引主要有两种结构：B+Tree索引和Hash索引
(a) Inodb存储引擎 默认是 B+Tree索引



(b) MyISAM 存储引擎 默认是Fulltext索引；



(c)Memory 存储引擎 默认 Hash索引；



Hash索引



mysql中，只有Memory(Memory表只存在内存中，断电会消失，适用于临时表)存储引擎显示支持Hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。Hash索引把数据以hash形式组织起来，因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能。



B+Tree索引



B+Tree是mysql使用最频繁的一个索引数据结构，是Inodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎。毕竟不可能只对数据库进行单条记录的操作。



带顺序访问指针的B+Tree



B+Tree所有索引数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。



这样做是为了提高区间效率，例如查询key为从18到49的所有数据记录，当找到18后，只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点，极大提高了区间查询效率。



大大减少磁盘I/O读取



数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点需要一次I/O就可以完全载入。



什么是索引
索引（Index）是帮助数据库高效获取数据的数据结构。索引是在基于数据库表创建的，它包含一个表中某些列的值以及记录对应的地址，并且把这些值存储在一个数据结构中。最常见的就是使用哈希表、B+树作为索引。



一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。



为什么要使用索引
我们知道，数据库查询是数据库最主要的功能之一。而查询速度当然是越快越好。而当数据量越来越大的时候，查询花费的时间会随之增长。而索引，可以加速数据的查询。因为索引是有序排列的。



举个例子来说，假设我们有一个数据库表Employee，这个表分别有三个字段：name，age，address。假设表中有1000条记录。



假如没有使用索引，当我们查询名为“Jesus”的雇员的时候，即调用：



select name,age,address from Employee where name = ‘Jesus’;
此时数据库不得不在Employee表中对这1000条记录一条一条的进行判断name字段是否为“Jesus”。这也就是所谓的全表扫描。



而当我们在Employee表上的name字段上创建索引时，当我们查询名为“Jesus”的雇员时，会通过索引查找去查询名为“Jesus”的雇员，因为该索引已经按照字母顺序排列，因此要查找名为“Jesus”的记录时会快很多，因为名字首字母为“J”的雇员都是排列在一起的。通过该索引，能获取到表中对应的记录。



举例说明使用索引的好处
假设索引（索引是一种数据结构）是链表结构。每个节点存储的是关键字字段（这个例子中对应的是name属性）以及该关键字字段在数据库表的对应的记录的地址。而这些节点是根据name属性排序的（即根据字母顺序排序）。因此，当我们执行上面说的查找名为“Jesus”的sql语句时，数据库会通过该索引来查询，因为该链表是有序排列的，在我们找到第一个name属性为“Jesus”的节点后，继续往后找，当遇到name属性不为“Jesus”的节点时，就无需再往后查找了，因为节点是根据name属性有序排列的啊。假设第一个name=“Jesus”的节点是第499个节点，最后一个name=“Jesus”的节点是第500个节点，那么只需要遍历501个节点就可以了。当发现第501个节点的name字段不为“Jesus”，后面的499个节点也就无需遍历了。通过索引，我们就找到了name为“Jesus”的节点，而通过该节点的另一个属性（关键字字段在数据库表的对应的记录的地址），我们就能获取到Employee表中满足条件name=“Jesus”的记录了。



通过使用索引，查询判断的次数就从1000次缩小到了501次了。起到了加速了查询效率。但实际上数据库中索引的结构，并不是链表结构。



数据库中使用什么数据结构作为索引
数据库中实际使用的索引并不会是链表结构，因为效率太低了。
我们知道链表的查询效率是O(n)。就像上面的例子，遍历了501次才找到第一条符合条件的记录，这是很低效的。而我们知道，数组+二分查找的效率是O(lgn)，但是数组的插入元素以及删除元素的效率很低，因此使用数组做为索引结构并不合适。



另外，在选择数据库索引的结构的时候，要考虑到另一个问题。索引是存在于磁盘中，当索引非常大的时候，达到几个G的时候，无法一次加载到内存中。



考虑到上面两个因素，数据库中索引使用的是树形结构。



各种树的名字
有这么几种树：



B-Tree
B+-Tree
B*-Tree
首先要明白三种树名中的“-”起到的是分隔的作用，并不是“减”的意思。



因此正确的翻译应该是B树，B+树，B树。而不是B-树，B+树，B树。因此，当你听到别人说“B减树”的时候，要明白它指的是B-Tree。即B树和B-树是同一种树。



为什么要强调上面这一点呢，因为有的博文中写的是：B树是二叉树，B-树是多路搜索树。



然而B树和B-树都是指B-Tree。引用维基百科上的话：



B-tree
Not to be confused with Binary tree.



也就是说，B-Tree并不是Binart tree。B-Tree的中文名是平衡多路搜索树。
（B树的相关介绍在下面）



平衡二叉树
树形结构是计算机系统里最重要的数据结构。



我们知道，二叉树的查找的时间复杂度是O(log2N)，其查找效率与深度有关，而普通的二叉树可能由于内部节点排列问题退化成链表，这样查找效率就会很低。因此平衡二叉树是更好的选择，因为它保持平衡，即通过旋转调整结构保持最小的深度。其查找的时间复杂度也是O(log2N)。



但实际上，数据库中索引的结构也并非AVL树或更优秀的红黑树，尽管它的查询的时间复杂度很低。



为什么平衡二叉树也不适合作为索引
之前说了平衡树的查找时间复杂度是O(log2N)，已经很不错了，但还是不适合作为索引结构。那么肯定是有一种更适合作为索引的数据结构。那么这个更适合作为索引的数据结构，难道是查找的时间复杂度更低吗？并不是。这种作为索引的数据结构的查找的时间复杂度也近似O(log2N)。



那为什么平衡二叉树不适合作为索引呢？



索引是存在于索引文件中，是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。



注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。



而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。



B-Tree适合作为索引
平衡二叉树不适合作为索引。那么什么才适合作为索引——B树。



平衡二叉树没能充分利用磁盘预读功能，而B树是为了充分利用磁盘预读功能来而创建的一种数据结构，也就是说B树就是为了作为索引才被发明出来的的。



来看看关于“局部性原理与磁盘预读”的知识：



复制代码
局部性原理与磁盘预读：



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



搞清楚上面的意思。磁盘预读是具体实现，其理论依据是局部性原理。



为什么说红黑树没能充分利用磁盘预读功能，引用一篇博文的一段话：



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



也就是说，使用红黑树（平衡二叉树）结构的话，每次磁盘预读中的很多数据是用不上的数据。因此，它没能利用好磁盘预读的提供的数据。然后又由于深度大（较B树而言），所以进行的磁盘IO操作更多。



B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字，树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少，更多的是在内存中对读取进来的数据进行查找。



B树的查询，主要发生在内存中，而平衡二叉树的查询，则是发生在磁盘读取中。因此，虽然B树查询查询的次数不比平衡二叉树的次数少，但是相比起磁盘IO速度，内存中比较的耗时就可以忽略不计了。因此，B树更适合作为索引。



比B树更适合作为索引的结构——B+树
比B树更适合作为索引的结构是B+树。MySQL中也是使用B+树作为索引。它是B树的变种，因此是基于B树来改进的。为什么B+树会比B树更加优秀呢？



B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；



B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。



引用一段话：



复制代码
走进搜索引擎的作者梁斌老师针对B树、B+树给出了他的意见（为了真实性，特引用其原话，未作任何改动）： “B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。
B树比如你的例子中查，17的话，一把就得到结果了，
有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。
另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。”
复制代码



举个例子来对比。
B树：



比如说，我们要查找关键字范围在3到7的关键字，在找到第一个符合条件的数字3后，访问完第一个关键字所在的块后，得遍历这个B树，获取下一个块，直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的。



B+树(叶节点保存数据，其他的节点 全部存放索引)：



相比之下，B+树的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针，因此从块1到块2的访问，通过块1指向块2的指针即可。从块2到块3也是通过一个指针即可。



引用一篇博文中网友评论的一段话：



数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。
B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
正如上面所说，在数据库中基于范围的查询是非常频繁的，因此MySQL最终选择的索引结构是B+树而不是B树。



二、索引的原理
一 索引原理



索引的目的在于提高查询效率，与我们查阅图书所用的目录是一个道理：先定位到章，然后定位到该章下的一个小节，然后找到页数。相似的例子还有：查字典，查火车车次，飞机航班等



本质都是：通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。



数据库也是一样，但显然要复杂的多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择怎么样的方式来应对所有的问题呢？我们回想字典的例子，能不能把数据分成段，然后分段查询呢？最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分成第三段……这样查第250条数据，只要找第三段就可以了，一下子去除了90%的无效数据。但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是lgN，具有不错的查询性能。但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的。而数据库实现比较复杂，一方面数据是保存在磁盘上的，另外一方面为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。



二 磁盘IO与预读



考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。



三、索引的数据结构



任何一种数据结构都不是凭空产生的，一定会有它的背景和使用场景，我们现在总结一下，我们需要这种数据结构能够做些什么，其实很简单，那就是：每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢？就这样，b+树应运而生。



如上图，是一颗b+树，关于b+树的定义可以参见B+树，这里只说一些重点，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。



###b+树的查找过程
如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。



###b+树性质
1.索引字段要尽量的小：通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。
2.索引的最左匹配特性（即从左往右匹配）：当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。



这也是经常考察的，比如 我定义了 A,B,C的联合索引，如果 我只传递了 A,B 能走索引吗？答案是能，因为最左侧原理(百度问过)



补充一下. 全文索引（FULLTEXT）=mysql的 myISAM搜索引擎默认的索引类型
MySQL从3.23.23版开始支持全文索引和全文检索，fulltext索引仅可用于 MyISAM 表；他们可以从CHAR、VARCHAR或TEXT列中作为CREATE TABLE语句的一部分被创建，或是随后使用ALTER TABLE 或CREATE INDEX被添加。////对于较大的数据集，将你的资料输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把资料输入现有FULLTEXT索引的速度更为快。不过切记对于大容量的数据表，生成全文索引是一个非常消耗时间非常消耗硬盘空间的做法。
文本字段上的普通索引只能加快对出现在字段内容最前面的字符串(也就是字段内容开头的字符)进行检索操作。如果字段里存放的是由几个、甚至是多个单词构成的较大段文字，普通索引就没什么作用了。这种检索往往以LIKE %word%的形式出现，这对MySQL来说很复杂，如果需要处理的数据量很大，响应时间就会很长。
　　这类场合正是全文索引(full-text index)可以大显身手的地方。在生成这种类型的索引时，MySQL将把在文本中出现的所有单词创建为一份清单，查询操作将根据这份清单去检索有关的数据记录。全文索引即可以随数据表一同创建，也可以等日后有必要时再使用下面这条命令添加：
　　ALTER TABLE table_name ADD FULLTEXT(column1, column2)
　　有了全文索引，就可以用SELECT查询命令去检索那些包含着一个或多个给定单词的数据记录了。下面是这类查询命令的基本语法：
　　SELECT * FROM table_name
　　WHERE MATCH(column1, column2) AGAINST(‘word1’, ‘word2’, ‘word3’)
　　上面这条命令将把column1和column2字段里有word1、word2和word3的数据记录全部查询出来。



参考：Mysql索引详解及优化(key和index区别)



四，索引使用注意事项
1，不要滥用索引



①，索引提高查询速度，却会降低更新表的速度，因为更新表时，mysql不仅要更新数据，保存数据，还要更新索引，保存索引



②，索引会占用磁盘空间



2，索引不会包含含有NULL值的列



复合索引只要有一列含有NULL值,那么这一列对于此符合索引就是无效的，因此我们在设计数据库设计时不要让字段的默认值为NULL。



3，MySQL查询只是用一个索引



如果where字句中使用了索引的话，那么order by中的列是不会使用索引的



4，like



like ‘%aaa%’不会使用索引而like “aaa%”可以使用索引



二、选择索引的数据类型
Mysql支持很多数据类型，选择合适的数据类型存储数据对性能有很大的影响。



(1)越小的数据类型通常更好：越小的数据类型通常在磁盘、内存和cpu缓存中都需要更少的空间，处理起来更快。



(2)简单的数据类型更好：整形数据比起字符，处理开销更小，因为字符串的比较更复杂。在MySQL中，应用内置的日期和时间数据类型，而不是字符串来存储时间；以及用整形数据存储IP地址。



(3)尽量避免NULL：应该制定列为NOT NULL，除非你想存储NULL。在MySQL中，含有空值的列很难进行查询优化，因为他们使得索引、索引的统计信息以及比较运算更加复杂。



三、MySQL常见索引有：主键索引、唯一索引、普通索引、全文索引、组合索引
1，INDEX（普通索引）：ALTER TABLE ‘table_name’ ADD INDEX index_name(‘col’)



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



2，UNIQUE（唯一索引）：ALTER TABLE ‘table_name’ ADD UNIQUE(‘col’)



与“普通索引”类似，不同的就是：索引列的值必须唯一，但允许有空值。



3，PRIMARY KEY（主键索引）：ALTER TABLE ‘table_name’ ADD PRIMARY KEY(‘col’)



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



4，FULLTEXT（全文索引）：ALTER TABLE ‘table_name’ ADD FULLTEXT(‘col’)



仅可用于MyISAM和InoDB，针对较大的数据，生成全文索引很耗时耗空间



组合索引：ALTER TABLE ‘table_name’ ADD INDEX index_name(‘col1’,’col2’,’col3’)



为了更多的提高mysql效率可建立组合索引，遵循“最左前缀”原则。创建复合索引应该将最常用（频率）做限制条件的列放在最左边，一次递减。组合索引最左字段用in是可以用到索引的。相当于建立了col1,col1col2,col1col2col3三个索引



Category storage