Mysql深度解析（一）索引底层数据结构与算法

news/2024/4/20 6:04:13/文章来源:https://blog.csdn.net/fjd7474/article/details/127622074

MySQL底层索引是用B+树实现的
传送门：什么是B-树、B+树、B*树

传送门：深入理解MySQL索引底层数据结构与算法

传送门：MySQL中Innodb的索引

1 索引是什么?

索引：帮助Mysql高效获取数据的排好序的数据结构。

2 Mysql索引为什么用B+树而不是用B树?

首先需要知道B树和B+树的区别：
（1）B+树非叶子节点不存储data，只存储索引(冗余)，叶子节点包含所有索引字段。而B树所有节点都存放data和索引。
（2）B+树叶子节点用指针连接，而B树没有。

所以Mysql索引用B+树的原因就是：
（1）B+树叶节点使用指针相连，提高了区间访问速度，支持范围查找。
（2）B+树非叶节点不存放数据，只存放索引，所以相同数据量的情况下B+树更加矮胖，所以每次I/O操作可以读取更多的节点数量，当找到目标数据的时候，再通过节点中的数据地址信息去读取数据，可以在总体上减少I/O操作，体检查询效率。

补充：Mysql文件页大小默认16KB
查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size’;

假设我们一行数据大小为1K，那么一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)
那么一颗高度为2的B+树能存储的数据为：117016=18720条，一颗高度为3的B+树能存储的数据为：11701170*16=21902400（千万级条）

（3）B+树结构的检索性能更具有稳定性，B-在找到节点的时候，其实就是已经拿到了需要的数据，而B+树在找到节点之后，还需要再次I/O操作去读取数据，B-最快的时候1次I/O操作就能拿到数据，而B+树每次都需要遍历到叶子节点才能拿到数据，相对来说，B+树结构的检索性能更具有稳定性。

3 MyISAM存储引擎和InnoDB存储引擎索引区别

3.1 MyISAM存储引擎

MyISAM索引文件和数据文件是分离的(非聚集)，叶节点的data域存放的是数据记录的地址

在这里插入图片描述

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别

只是主索引要求key是唯一的

而辅助索引的key可以重复

如果我们在Col2上建立一个辅助索引，则此索引的结构

跟主键索引的结构没什么区别
在这里插入图片描述

3.2 InnoDB存储引擎

InnoDB引擎索引的关键字和数据都在叶节点上。

可以分为聚集索引与非聚集索引，这两种索引都是使用B+树组织的。

聚集索引：叶节点包含了完整行数据

当我们基于 InnoDB 引擎创建一张表的时候，都会创建一个聚集索引，每张表都有唯一的聚集索引：

如果这张表定义了主键索引，那么这个主键索引就作为聚集索引。
如果这张表没有定义主键索引，那么该表的第一个唯一非空索引作为聚集索引。
如果这张表也没有唯一非空索引，那么 InnoDB 内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个 6 个字节的列，该列的值会随着数据的插入自增。

主键索引和聚集索引并不是一回事

聚集索引最主要的优势就是查询快。如果要查询完整的数据行，使用非聚集索引往往需要回表才能实现，而使用聚集索引则能一步到位。

聚集索引也有一些劣势：

聚集索引可以减少磁盘 IO 的次数，这在传统的机械硬盘中是很有优势的，不过要是固态硬盘或者内存（有时候为了提高操作效率，数据库服务器会整一个比较大的内存），这个优势就不明显了。
聚集索引在插入的时候，最好是主键自增，自增主键插入的时候比较快，直接插入即可，不会涉及到叶子节点分裂等问题（不需要挪动其他记录）；而其他非自增主键插入的时候，可能要插入到两个已有的数据中间，就有可能导致叶子节点分裂等问题，插入效率低（要挪动其他记录）。如果聚集索引在插入的时候不是自增主键，插入效率就会比较低。

非聚集索引

非聚集索引也称为二级索引或者辅助索引，对于非聚集索引，数据库会有单独的存储空间来存放。非聚集索引在查找的时候要经过两个步骤，例如执行 select * from user where username=‘javaboy’（假设 username 字段是非聚集索引），那么此时需要先搜索 username 这一列索引的 B+Tree，这个 B+Tree 的叶子结点存储的不是完整的数据行，而是主键值，当我们搜索完成后得到主键的值，然后拿着主键值再去搜索主键索引的 B+Tree，就可以获取到一行完整的数据。

所以如果我们在查询中用到了非聚集索引，那么就会搜索两棵 B+Tree，第一次搜索 B+Tree 拿到主键值后再去搜索聚集索引的 B+Tree，这个过程就是所谓的回表。

一张表只能有一个聚集索引，但可以有多个非聚集索引。使用聚集索引的时候，数据的查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚集索引低。