MySQL索引(二)B+树在磁盘中的存储

9,665 阅读5分钟

回顾

w200

上一篇文章《MySQL索引为什么要用B+树》讲了MySQL为什么选择用B+树来作为底层存储结构,提了两个知识点:

  1. B+树索引并不能直接找到行,只是找到行所在的页,通过把整页读入内存,再在内存中查找。
  2. 索引的B+树高度一般为2-4层,查找记录时最多只需要2-4次IO。

为进一步知其所以然,今天来聊聊B+树索引在物理磁盘上是怎么设计存储的。

一、理解为什么要减少磁盘IO次数

众所周知,MySQL的数据实际是存储在文件中,而磁盘IO的查找速度是要远小于内存速度的,所以减少磁盘IO的次数能很大程度的提高MySQL性能。

1.1 磁盘IO为什么慢

先温习下知识点:磁盘IO时间 = 寻道 + 磁盘旋转 + 数据传输时间

从磁盘读取数据时,系统会将逻辑地址发给磁盘,磁盘将逻辑地址转换为物理地址(哪个磁道,哪个扇区)。 磁头进行机械运动,先找到相应磁道,再找该磁道的对应扇区,扇区是磁盘的最小存储单元(见图1-1)。

-w356
 图1-1 磁盘物理结构

1.2 性能对比

机械硬盘的连续读写性能很好,但随机读写性能很差。

  • 顺序访问:内存访问速度是硬盘访问速度的6~7倍(kafka的特点,以后有机会的话再讲一讲)
  • 随机访问:内存访问速度就要比硬盘访问速度快上10万倍以上

随机读写时,磁头需要不停的移动,时间都浪费在了磁头寻址上。 而在实际的磁盘存储里,是很少顺序存储的,因为这样的维护成本会很高。

二、索引在磁盘上的存储

知道磁盘IO的性能了吧,接下来看看MySQL是如何根据这种情况来设计索引的物理存储,以下内容以InnoDB引擎为例,MyISAM略有不同,后面再讲。

假设我们有一张这样的表,表中有如图2-0的数据

CREATE TABLE `user` (
  `ID` bigint(11) NOT NULL AUTO_INCREMENT,
  `NAME` varchar(20),
  PRIMARY KEY (`ID`),
  KEY `idx_name` (`NAME`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

图2-0 表数据

2.1 聚集索引(Clustered index )

每个InnoDB表都有一个称为聚集索引的特殊索引,该索引是按照表的主键构造的一棵B+树。

根据示例数据构建如图2-1所示聚集索引:

 图2-1 B+树聚集索引

2.1.1 知识点

  • 叶子节点存放了整张表的所有行数据。
  • 非叶子节点并不存储行数据,是为了能存储更多索引键,从而降低B+树的高度,进而减少IO次数。
  • 聚集索引的存储在物理上并不是连续的,每个数据页在不同的磁盘块,通过一个双向链表来进行连接。

2.1.2 查找:假设要查找数据项6

  1. 把根节点由磁盘块0加载到内存,发生一次IO,在内存中用二分查找确定6在3和9之间;
  2. 通过指针P2的磁盘地址,将磁盘2加载到内存,发生第二次IO,再在内存中进行二分查找找到6,结束。

这里只进行了两次IO,实际上,每个磁盘块大小为4K,3层的B+树可以表示上百万的数据,也就是每次查找只需要3次IO,所以索引对性能的提高将是巨大的。

2.1.3 怎样选择聚集索引

每张InnoDB表有且只有一个聚集索引,那它是怎么选择索引的呢?

  • 一般情况,用PRIMARY KEY来作为聚集索引。
  • 如果没有定义PRIMARY KEY,将会用第一个UNIQUENOT NULL的列来作为聚集索引。
  • 如果表没有合适的UNIQUE索引,会内部根据行ID值生成一个隐藏的聚簇索引GEN_CLUST_INDEX

所以在建表的时候,如果没有逻辑唯一且非空列时,可以添加一个auto_increment的列,方便建立一个聚集索引。

2.2 非聚集索引(Secondary indexes)

非聚集索引又叫辅助索引,叶子节点并不包含行记录数据,而是存储了聚集索引键。

根据示例数据(idx_name索引)构建如图2-2所示辅助索引:

 图2-2 B+树非聚集索引

2.2.1 知识点

  • 每个表可以有多个辅助索引
  • 通过辅助索引查数据时,先查找辅助索引获得聚集索引的主键,然后通过主键索引来查找完整的行记录。
  • 通过非主键索引比主键索引查找速度要慢一倍。

2.2.2 查找:获取NAME=Jake的数据

第一阶段:通过辅助索引查到主键索引的主键

  1. 把idx_name索引的根节点由磁盘块0加载到内存,发生一次IO,查找到在P2指针中
  2. 根据P2指针的磁盘地址,加载磁盘块2到内存,发生第二次IO,查找到Jake节点以及它的主键索引9

第二阶段:通过主键索引找到完整的行记录

  1. 把根节点由磁盘块0加载到内存,发生一次IO,在内存中用二分查找确定9在P3指针中
  2. 通过指针P3的磁盘地址,将磁盘3加载到内存,发生第二次IO,再在内存中进行二分查找找到9,以及它的行记录,

查找结束。


未完待续…

如果想要实时关注更新的文章以及分享的干货,可以关注我的公众号

懂了吗