【MySQL】索引原理（二）：B+Tree索引的实现，MyISAM 和 InnoDB

傷城~ 2022-11-20 13:58 155阅读 0赞

在[【MySQL】存储引擎（一）：存储引擎介绍][MySQL]一文中，我们说过了，MySQL是一个支持插件式存储引擎的数据库。在MySQL里面，每个表在创建的时候都可以指定它所使用的存储引擎。这里我们主要关注一下最常用的两个存储引擎，MyISAM和InnoDB的索引的实现。

首先，MySQL的数据都是文件的形式存放在磁盘中的，我们可以找到这个数据目录的地址。在MySQL中有这么一个参数，我们来看一下：

show VARIABLES LIKE 'datadir';

![在这里插入图片描述][20201029001926481.png_pic_center]

每张InnoDB 的表有两个文件（.frm和.ibd），MyISAM的表有三个文件（.frm、.MYD、.MYI）。

有一个是相同的文件(.frm），是MySQL里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成。我们主要看一下其他两个文件是怎么实现MySQL不同存储引擎的索引。如下图，是MySQL的B+Tree索引结构，但叶子节点存什么数据还不知道。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]

## 1.MyISAM ##

在MyISAM里面，另外有两个文件：

*  .MYD文件，D代表Data，是MyISAM的数据文件，存放数据记录。
 *  .MYI文件，I代表Index，是MyISAM的索引文件，存放索引，比如我们在id字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。

**问题一**：也就是说，在MyISAM里面，索引和数据是两个独立的文件。那我们怎么根据索引找到数据呢？

MyISAM的B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI中找到键值后，会到数据文件.MYD中获取相应的数据记录。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]

**问题二**：这里是主键索引，如果是辅助索引，有什么不一样呢？

在 MyISAM 里面，辅助索引也在这个.MYI文件里面。辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]

## 2.InnoDB ##

InnoDB 只有一个文件（.ibd文件），那索引放在哪里呢？在InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文件是同一个文件，都在.ibd文件里面。在InnoDB的主键索引的叶子节点上，它直接存储了我们的数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]

**问题一**：什么叫做聚集索引（聚簇索引）？

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。（比如字典的目录是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。在InnoDB里面，它组织数据的方式叫做叫做（聚集）索引组织表（clusteredindexorganize table），所以主键索引是聚集索引，非主键都是非聚集索引。

**问题二**：如果InnoDB里面主键是这样存储的，那主键之外的索引，比如我们在name字段上面建的普通索引，又是怎么存储和检索数据的呢？

InnoDB中，主键索引和辅助索引是有一个主次之分的。辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。比如我们用 name 索引查询 name=‘青山’，它会在叶子节点找到主键值，也就是id=1，然后再到主键索引的叶子节点拿到数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 4]

**问题三**：为什么在辅助索引里面存储的是主键值而不是主键的磁盘地址呢？如果主键的数据类型比较大，是不是比存地址更消耗空间呢？

在 [【MySQL】详谈索引存储结构推演过程][MySQL 1] 一文我们说到 B Tree是通过不断的分叉和合并操作使树保持平衡的，而这个时候键值的地址会发生变化，所以在辅助索引里面不能存储地址。

**问题四**：如果一张表没有主键怎么办？

1.  如果我们定义了主键(PRIMARY KEY)，那么InnoDB会选择主键作为聚集索引。
2.  如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引。
3.  如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐藏的聚集索引，它会随着行记录的写入而主键递增。

select _rowid name from user_info;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 5]

**问题五**：在选择主键字段时，推荐使用自增还是uuid？

推荐使用主键列自增，因为增加数据时会按顺序在后面增加，不会破坏已有结构。而对于字符串（UUID），会比较器ASCII码值，多了一次转换运算；并且插入是无序的。

[MySQL]: https://blog.csdn.net/weixin_43935927/article/details/113983566
[20201029001926481.png_pic_center]: /images/20221120/213f0b4ffc7840588196cf6470902ec1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/223661747a8a41fb899d43530b9ba3d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/477315acdbf146fdb69b0fc2a8d4f66b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/76672b28beb04349939c85176c71af09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201029002146563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201029002336339.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw==,size_16,color_FFFFFF,t_70#pic_center
[MySQL 1]: https://blog.csdn.net/weixin_43935927/article/details/109346359
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201029002650194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw==,size_16,color_FFFFFF,t_70#pic_center