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

栏目: 数据库 · 发布时间: 5年前

内容简介:上一篇文章为进一步知其所以然,今天来聊聊B+树索引在物理磁盘上是怎么设计存储的。
MySQL索引(二)B+树在磁盘中的存储

上一篇文章 《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 )。

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

 图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;
复制代码
MySQL索引(二)B+树在磁盘中的存储

图2-0 表数据

2.1 聚集索引(Clustered index )

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

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

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

 图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,所以索引对性能的提高将是巨大的。

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

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所示辅助索引:

MySQL索引(二)B+树在磁盘中的存储
 图2-2 B+树非聚集索引


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Java

Mark A. Weiss / Pearson / 2006-3-3 / USD 143.00

As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop wel......一起来看看 《Data Structures and Algorithm Analysis in Java》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

html转js在线工具
html转js在线工具

html转js在线工具