mysql索引在磁盘存储_MySQL索引（二）B+树在磁盘中的存储

回顾

&＃xfffc;

上一篇文章《MySQL索引为什么要用B&＃43;树》讲了MySQL为什么选择用B&＃43;树来作为底层存储结构&＃xff0c;提了两个知识点&＃xff1a;

B&＃43;树索引并不能直接找到行&＃xff0c;只是找到行所在的页&＃xff0c;通过把整页读入内存&＃xff0c;再在内存中查找。

索引的B&＃43;树高度一般为2-4层&＃xff0c;查找记录时最多只需要2-4次IO。

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

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

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

1.1 磁盘IO为什么慢

先温习下知识点&＃xff1a;磁盘IO时间 &＃61; 寻道 &＃43; 磁盘旋转 &＃43; 数据传输时间

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

&＃xfffc; 图1-1 磁盘物理结构

1.2 性能对比

机械硬盘的连续读写性能很好&＃xff0c;但随机读写性能很差。

顺序访问&＃xff1a;内存访问速度是硬盘访问速度的6~7倍(kafka的特点&＃xff0c;以后有机会的话再讲一讲)

随机访问&＃xff1a;内存访问速度就要比硬盘访问速度快上10万倍以上

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

二、索引在磁盘上的存储

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

假设我们有一张这样的表&＃xff0c;表中有如图2-0的数据

CREATE TABLE &＃96;user&＃96; (

&＃96;ID&＃96; bigint(11) NOT NULL AUTO_INCREMENT, &＃96;NAME&＃96; varchar(20), PRIMARY KEY (&＃96;ID&＃96;), KEY &＃96;idx_name&＃96; (&＃96;NAME&＃96;) ) ENGINE&＃61;InnoDB DEFAULT CHARSET&＃61;utf8;

图2-0 表数据

2.1 聚集索引(Clustered index )

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

根据示例数据构建如图2-1所示聚集索引&＃xff1a;

&＃xfffc; 图2-1 B&＃43;树聚集索引

2.1.1 知识点

叶子节点存放了整张表的所有行数据。

非叶子节点并不存储行数据&＃xff0c;是为了能存储更多索引键&＃xff0c;从而降低B&＃43;树的高度&＃xff0c;进而减少IO次数。

聚集索引的存储在物理上并不是连续的&＃xff0c;每个数据页在不同的磁盘块&＃xff0c;通过一个双向链表来进行连接。

2.1.2 查找&＃xff1a;假设要查找数据项6

把根节点由磁盘块0加载到内存&＃xff0c;发生一次IO&＃xff0c;在内存中用二分查找确定6在3和9之间&＃xff1b;

通过指针P2的磁盘地址&＃xff0c;将磁盘2加载到内存&＃xff0c;发生第二次IO&＃xff0c;再在内存中进行二分查找找到6&＃xff0c;结束。

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

&＃xfffc;

2.1.3 怎样选择聚集索引

每张InnoDB表有且只有一个聚集索引&＃xff0c;那它是怎么选择索引的呢&＃xff1f;

一般情况&＃xff0c;用PRIMARY KEY来作为聚集索引。

如果没有定义PRIMARY KEY&＃xff0c;将会用第一个UNIQUE且NOT NULL的列来作为聚集索引。

如果表没有合适的UNIQUE索引&＃xff0c;会内部根据行ID值生成一个隐藏的聚簇索引GEN_CLUST_INDEX。

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

2.2 非聚集索引(Secondary indexes)

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

根据示例数据(idx_name索引)构建如图2-2所示辅助索引&＃xff1a;

&＃xfffc; 图2-2 B&＃43;树非聚集索引

2.2.1 知识点

每个表可以有多个辅助索引

通过辅助索引查数据时&＃xff0c;先查找辅助索引获得聚集索引的主键&＃xff0c;然后通过主键索引来查找完整的行记录。

通过非主键索引比主键索引查找速度要慢一倍。

2.2.2 查找&＃xff1a;获取NAME&＃61;Jake的数据

第一阶段&＃xff1a;通过辅助索引查到主键索引的主键

把idx_name索引的根节点由磁盘块0加载到内存&＃xff0c;发生一次IO&＃xff0c;查找到在P2指针中

根据P2指针的磁盘地址&＃xff0c;加载磁盘块2到内存&＃xff0c;发生第二次IO&＃xff0c;查找到Jake节点以及它的主键索引9

第二阶段&＃xff1a;通过主键索引找到完整的行记录

把根节点由磁盘块0加载到内存&＃xff0c;发生一次IO&＃xff0c;在内存中用二分查找确定9在P3指针中

通过指针P3的磁盘地址&＃xff0c;将磁盘3加载到内存&＃xff0c;发生第二次IO&＃xff0c;再在内存中进行二分查找找到9&＃xff0c;以及它的行记录&＃xff0c;

查找结束。

未完待续…

原文链接&＃xff1a;MySQL索引(二)B&＃43;树在磁盘中的存储 - 掘金  https://juejin.im/post/5cef2c43e51d45572c05ffe3