我们知道mysql的数据库和表是存放在mysql的data目录中。一个数据库对应一个目录，一个数据表对应一个或多个文件。

 

Myisam引擎的主键索引

Myisam的表对应三个文件：frm、MYD和MYI，分别存储着表结构，表数据和表索引

下面是以主键为索引构建的myisam表的B+树：

上图中，左上角是一个B+ Tree , 存在MYI文件中。右下角是整个表数据，存在MYD文件中。

当我查询 select * from t where col1 = 30;

它会先判断col1是否为索引字段，是则先到MYI文件中，按照B+ 树的查找算法找到 30这个索引的vlaue，在myisam中value存的是索引所在行的磁盘地址。

于是mysql会拿着这个地址在MYD文件中找到磁盘地址对应的位置的行，读取这个位置的行数据（这个过程叫做回表）。

 

对于myisam使用索引查找行数据会跨两个文件。所以myisam的索引是非聚集索引（非聚集索引的概念是数据存储顺序和索引存储顺序不同的索引结构）。

 

Innodb引擎的主键索引

Innodb的表对应frm和idb两个文件，frm是表结构，idb是数据+索引。

下面是以主键为索引构建的innodb表的B+树：

 

innodb表的主键索引和其他字段的数据一起存放在以B+树的数据结构存储起来的。

Idb文件中的B+树的非叶子节点也是存放多个key但不存放data/value。叶子节点的key是多个（主键）索引字段值，而value是（主键）索引字段所在行的其他列的数据内容。

因为innodb的（主键）索引和数据是放到一个文件中，放在一个叶节点中，而且数据保存顺序和索引保存顺序一致，所以这种索引叫做聚集索引。

聚集索引的效率其实比非聚集索引的效率高，因为它只用查找1个文件，少了回表过程（少了一次磁盘IO操作），尤其在范围查询的时候这个差距会更明显。

 

二级索引

上面介绍了myisam和innodb的主键索引的B+树，下面介绍myisam和innodb的非主键索引（二级索引）的B+树。

 

首先要明白的一件事是：无论是myisam还是innodb，当我们为一个表多创建一个索引的时候，底层就会多构建出一颗B+树。

对于一个表A，我们一般会在建表的时候，给A创建一个主键索引（id）。此时底层就会为这个主键索引构建一棵B+树并存在idb或myi文件中。

但是如果我想给A的另外一个字段构建一个普通索引，或者我想给A的另外几个字段构建一个联合索引，此时底层会多构建出一棵B+树。像这种非主键的索引（普通索引或联合索引或者非主键的唯一索引），我们把它叫做二级索引。

  

每次新建一个二级索引，都会在构建一棵新的B+树。所以如果索引建的太多，还是挺耗磁盘存储空间的。

 

那么接下来我要分开介绍innodb和myisam这两种引擎的二级索引的B+树，因为他们是有所不同的。 

Myisam的二级索引的B+树和myisam的主键索引的B+树没有任何区别，二级索引的B+树的叶子节点中的value也是存放着数据行所在的磁盘地址。无论使用普通索引还是主键来查找数据行都需要找到行的磁盘地址进行回表。  

   

（Myisam的二级索引）

 

 

Innodb的二级索引和innodb的主键索引不同，innodb的主键索引的B+树叶子节点的value存放着行数据，但是他的二级索引叶子节点存的不是行数据的地址也不是行数据本身，而是这个普通索引对应的主键值（id）

（Innodb的二级索引）

如果使用innodb的普通索引或者联合索引查找一条行记录，会先在二级索引的B+树找到这个索引对应的主键值，再根据主键值在主键索引B+树的根节点往下找到叶节点的行数据。

 

比较myisam和innodb的二级索引：

1.如果使用innodb的二级索引（普通索引、非主键唯一索引或联合索引）查询行，需要走两棵树，假如每棵树都是3层，就会发生3+3=6次io操作。如果myisam的话，只需走一棵树，只会发生3次io拿到行地址，但是myisam还要根据行地址到数据表中找到行数据，innodb直接在B+树中就拿到了行数据。
2.Innodb的二级索引的叶子节点存的是主键值，myisam的二级索引存的是行地址，后者更节省存储空间。
  

 

 

稀疏索引和稠密索引   

稀疏索引就是索引列和其他列 的数据不放在一棵B+树中的索引，稠密索引就是索引列和其他列的数据放在同一棵B+树的索引。

 

Innodb的主键索引（聚集索引）是稠密索引，innodb的二级索引是稀疏索引。

Myisam的主键索引（非聚集索引） 是稀疏索引，myisam的二级索引也是稀疏索引。 

 

 

  

InnoDB与MyISAM存储引擎之间的比较

下面我们以下几个方面来比较一下这两个存储引擎的不同。 

事务的支持

InnoDB支持ACID的事务处理，MyISAM并不支持事务

 

索引与主键处理

InnoDB存储引擎使用的是聚集索引，InnoDB主键的叶子节点是该行的数据，而其他索引则指向主键，而MyISAM存储引擎使用的是非聚集索引，主键与其他索引的叶子节点都存储了指向数据的指针。

另外一个是MyISAM数据表允许没有主键和其他索引，而InnoDB数据表如果没有主键的话，而会生成一个用户不可见6字节的主键。

外键

MyISAM不支持外键，而Innodb则支持建立数据表之间的外键关联。

存储文件的不同

Innodb存储文件有frm、ibd，而MyISAM是frm、MYD、MYI,Innodb存储文件中frm是数据表结构定义文件，ibd是数据文件,MyISAM中frm是数据表结构定义文件，MYD是数据的文件，MYI则是存储索引的文件。

select count(*)

使用MyISAM存储引擎的数据表会记录一个数据表的总行数，所以对使用MyISAM存储引擎的数据表进行select count(*)，可以很快得到一个数据表的总行数，而对于InnoDB存储引擎的数据表，想要查询总行数需要进行全表扫描才能得到。

锁的级别

InnoDB支持行级锁，而MyISAM只支持表级锁，因此InnoDB更能支持高并发。

================================================

 

为什么Innodb表必须有主键，并且推荐用整型的自增主键？

只要你是innodb的表，B+树必须用一个列的值作为节点中每个索引的key。如果不创建主键，innodb也会从数据表中选一列没有重复值的列的值作为节点的key，目的就是为了把B+树这个结构给组织起来。如果表中所有的列都有重复值，mysql会维护一个没有重复值的隐藏列（row_id） 作为这个B+树节点的索引的key，但是这会增加mysql的负担，所以还是自己建一个主键。

为什么推荐用自增整型主键，我们之前说过在用B+树进行查找一个索引A的时候，会逐次把树的节点加载到内存，将这个节点内所有的key与索引A进行比对找到索引A所在的范围。整型肯定比字符串的比对效率高。而且数字占用的存储空间肯定比字符串小，使得一棵层数相同的B+树能存储更多的索引。

为啥要自增的？因为如果是自增的索引，在insert数据的时候，索引会直接添加在B+树最右边的叶子节点中，避免了复杂的页分裂。如果不是自增的索引，而是一个唯一字符串（uuid），插入这样的索引到B+树的叶子节点时可能让B+树做多次平衡（页分裂），而平衡的过程需要进行一系列计算。所以使用自增数字作为主键相比于使用非自增的字符串uuid作为主键相比，索引加入到B+树的这个操作的性能会更高（数据的插入的速度更快）。

所以无论从时间还是空间来说，自增整型作主键都是更好的。

 

================================================

范围查找(> < between and)和in查找在B+树中的实现：

情况1：> <

比如我想查找id>30的数据（假设这里id是主键索引），那么mysql会先从根节点往下层节点找到30所在的叶子节点，然后通过叶子节点的双向链接找右边相邻的节点，这些右边相邻的叶子节点逐一加载到内存中。

如图所示，它的一个查找轨迹是蓝色线条所示，一共经过了5个指针，发生了5次磁盘IO。

如果 范围查找 的范围条件过大，那么在B+树中的IO操作次数会过多，此时mysql会认为还不如直接全表扫描快，就会放弃使用索引改为用全表扫描。

 

情况2：in查找

比如我想查 where id in (18, 30, 31,37,51)，它的过程如下如所示：

每查找一个id都会从根节点往下去找到这个id对应的叶子节点。所以上面的 where in查询共发生了8次io。

In查找有时候会被mysql认为是范围查找，有时候被认为是多个精确查找。

 

情况3：

现在假设views字段是一个普通索引而不是一个主键，如果我想查找 views > 100（假设满足>100的views有103,234,177,302这4个数字，这4个数字放在了2个叶节点上，二级索引共3层节点）。那么会先在二级索引通过范围查找找到103,234,177,302这4个数字对应的主键id（假设对应的id分别是57,11,90,33），这个过程发生了3次io操作。然后根据这4个主键id到主键索引的B+树中从根节点往下找这4个id对应的行记录（有4个id就要分4次从根节点往下找）。我们假设57,11,90,33这4个id分别放在了4个叶子节点中，主键索引的树有3层，那么在主键索引共进行 (3-1) * 4 = 8次io，再加上在二级索引发生的3次io，一共是11次io。

 

所以范围查找和in查找相比于精确查找(=)来说是更费io的。

 

================================================

 

联合索引查找在B+树中的实现：

在实际工作中，如果我们对一个表的3,4个字段建索引的话，我们很少会对每一个字段单独建索引。而是对这3,4个字段建立一个联合索引。

联合索引的底层是怎么实现的（重要，现在网上说的索引优化规则都是基于此）

以一个innodb表，4个字段，7条记录为例：

Col1	Col2	    Col3	    Col4
10001	Assistant	1998-09-03	2002-06-03
10001	Engineer	1996-08-03	2001-08-03
10001	Staff	    2001-09-03	2006-03-06
10002	Staff	    1996-08-03	
10003	Staff	    1997-08-03	2011-08-07
10003	Staff	    2001-09-03	2009-06-03
10004	Staff	    1996-08-03	

建立 index(col1, col2, col3) 这3个字段的联合索引。

构建B+的排序原则如下：先按照col1排序，如果col1相同，那么再按col2排序，col1和col2都相同则按col3排序。构建出来的一个B+树如下：

按照网上说的最左前缀原则，我们知道 where col1 = 10003  and col2=”staff” 使用到了联合索引，但是where col3=1996-08-03没有用到联合索引

接下来从底层解释一下，为什么 where col3=1996-08-03没有用到联合索引；

 

其实原因很简单，当执行 where col3=1996-08-03 的时候，相当于不看 col1和col2，那么我们在B+树中不看col1和col2是这个样子的（划线法）：

我们只到索引的高速查找是基于树节点的每一个索引key都是排好序的，可是此时 只看col3它在B+树中（从左到右）就不是一个排好序的样子而是一个乱序的样子，所以此时它会做一个全表扫描而无法用到索引进行查找。

 

再举一个例子：

一个文章表，我给它的id和view设置了单独索引，现在有两个索引

Select * from article where id>500 and view < 100;

请问这个sql会不会同时用到id和view这两个索引进行查找？

是不会的，原因很简单，从底层的角度看，建立了两个单独索引意味着创建了两棵B+树，但是mysql不会对一条sql语句去查两棵B+树，而是只会去其中一颗B+树查。所以上面的sql虽然where中写上了id和view的条件，但是真正用到的就只有一个索引。

 

 

再再再举一个例子：

这个例子就是我们网上搜mysql优化的时候提到的一条规则：where用联合索引作为条件时，使用范围查找之后的条件都用不到索引。

比如：

数据集如下

col1	col2	col3
5	13	254
5	24	500
8	18	304
6	22	108
9	33	290
10	24	350
9	22	333
8	30	566
10	40	302
10	17	130
10	36	280

建立联合索引index col1_col2_col3(col1, col2, col3)

Select * from t where col1=10 and col2>20 order by col3

Select * from t where col1=10 and col2>20 and col3 =300

上面的2个sql中，Col1和 col2 都用到了索引，但是col3没有用到索引。这里也要从B+树解释，用一句话说就是 符合col1=10 的叶节点他们的col2字段是排好序的。但是符合 col1=10且col2>10的叶节点他们的col3字段是乱序的，所以order by col3没有用到索引，需要mysql在内存中对col3进行排序，而 col3=300 没有用到索引，因为索引快速查找是依赖于排好序这个特性的。

 

我这么说可能大家不明白，那就画个图好了。

上面是一个构建好的B+ Tree，红框内的索引是满足 col1 = 10 and col2>20的索引。你看看他们的col3字段，也就是黄色框框之内的内容（350,302,280），黄框内的col3不是排好序的，而是乱序的。所以col3是没有用到索引。

 

========================================================

索引的优缺点

索引的优势：
我们知道索引的B+树结构的作用是排序和快速查找。
没有索引我们需要全表扫描，每扫描一条记录就是一次IO（有多少条数据就会发生几次IO），有了索引之后，精确查找时树的层数就是IO操作的次数，因此索引可以减少IO成本。
索引在建的时候会帮我们把索引字段排好序，所以查的时候如果用了“order by 索引字段”的话，数据库就无需再对数据进行排序，减少了cpu的消耗。

索引的劣势：
1.建过多的索引是很占空间的。
2.索引虽然能提高查询速度，但是会降低更新表的速度（insert、update和delete）。体现在底层就是更新表的操作会引起B+树的重新平衡（页分裂）、结构的改变和更改链接的指向。

索引的分类：
单列索引：一个索引只包含单个列，一个表可以建多个单列索引，但建议不要超过5个。而且用联合索引优于用单列索引。
唯一索引：索引列的值必须唯一，但允许空值。
联合索引：一个索引包含多个列的值。

哪些字段适合建索引：
1.一个表必须有主键索引，这里会建索引。
2.频繁作为查询条件的字段要
3.与其他表进行关联的字段或者外键
4.查询中要经常排序的字段
5.查询中统计和分组字段（因为分组会先进行排序）

不适合建索引的情况：
1.表记录很少（数据量不大全表扫描也很快）
2.频繁更新的字段不适合建索引，where条件用不到的字段不建索引
3.有很多重复的值的字段或者说离散度很低的字段不适合建索引（你想想看，一个B+树的节点的key中全是相同的值，排不排序都一样，而且还要读取很多很多的非叶子节点到内存，同样进行了很多io操作，例如下图：）

查找where tid = 1 ，由于这棵树的索引全是1，所以所有的树节点都会从磁盘读到内存，io的次数=树中的节点的个数。这个时候比全表扫描好一点点，但是也好不到哪里去。

========================================================

 

Memory 和 Merge 引擎

 

Memory存储引擎将表的数据存放在内存，每个memory表对应一个frm文件，只存储表结构，而Memory的数据存在内存当中，这是为了快速查询和插入数据。Memory的访问非常快，默认使用Hash索引，但是由于是存在内存中，所以一旦mysql关闭，数据就会消失，也就是不支持持久化。

还有Memory引擎是将数据存在内存，所以表的数据不能太多，否则内存会不足，也就是说不能存大表。

 

Merge引擎是一组Myisam表的组合，这些Myisam表必须结构完全相同。Merge表本身没有存数据，对Merge类型的表的增删改查本质都是对内部的Myisam表进行的。

对Merge表drop操作是不会删除内部的Myisam,只会删除Merge表。

 

这里只简单的介绍有这两种引擎，之后有机会会对这些引擎详细介绍。