php mysql底层BTree与B+Tree实现原理

100人浏览 2024-11-11 08:03:43

概述

这是关于php进阶到架构之Mysql进阶学习的第三篇文章：mysql底层BTree与B+Tree实现原理

第一篇：mysql共享锁及排它锁

第二篇：mysql事务及隔离级别

mysql底层BTree与B+Tree实现原理

索引是什么

为了加速对表中数据行的检索而创建的一种分散存储的数据结构

mysql索引机制为什么是B+Tree

二叉查找树，每个分支最多有两个（路）。

先了解下磁盘的相关知识。

系统从磁盘读取数据到内存时
是以磁盘块（block）为基本单位的，
位于同一个磁盘块中的数据会被一次性读取出来，
而不是需要什么取什么。

模拟查找关键字id =3的过程：

1.从根节点开始找磁盘块1，读入内存，发现 3 < 10，进入 P1 ，一次IO操作

2.此时P1指向磁盘块2，读入内存，发现 3< 5 ，进入 P1，一次IO操作

3.此时P1指向磁盘块4，读入内存，发现 3 = 3，命中，一次IO操作

（这里的IO操作理解为读取一个磁盘块，包括关键字、数据区、子节点引用）

上面索引到id为3的记录，需要3次IO操作、3次内存查找。
假如我们的数据表数据量非常大，那id就很多，
这样这个平衡二叉树的高度就很大，
假如我们要找的id = 3的记录，
在这颗树最大的高度，
那这样的命中索引，
需要很多次IO操作。

二叉树索引小结

二叉树的高度太高了,二叉树的高度决定IO操作次数，IO操作耗时，导致二叉树索引效率较低，故mysql不使用二叉树索引

B-Tree是什么

多路平衡查找树，B-Tree中的每个节点，根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

模拟查找关键字id =10的过程：

1.从根节点开始找磁盘块1，读入内存，发现10 < 17，进入 P1 ，一次IO操作

2.此时P1指向磁盘块2，读入内存，发现 8<10<12 ，进入 P2，一次IO操作

3.此时P2指向磁盘块6，读入内存，遍历叶子节点，发现 10 = 10，命中，一次IO操作

B-Tree相对于平衡二叉树缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree是什么

加强版多路平衡查找树，B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，mysql存储引擎就是用B+Tree实现其索引结构。

从上一节中的B-Tree结构图中，可以看到每个节点中不仅包含数据的key值（关键字，子节点引用），还有data值（一整条记录的磁盘地址）。

而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，

而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree与B-Tree的区别

B+节点关键字搜索采用闭合区间
B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用
B+关键字对应的数据保存在叶子节点中
B+叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系

MyISAM B+Tree索引体现形式

每个MyISAM在磁盘上存储成三个文件，每一个文件的名字均以表的名字开始，扩展名指出文件类型。

.frm文件存储表定义；

·MYD (MYData)文件存储表的数据；

.MYI (MYIndex)文件存储表的索引。

非聚集索引

MyISAM的索引与行记录是分开存储的

其主键索引与普通索引没有本质差异：

主键索引与普通索引是两棵独立的索引B+树，
通过索引列查找时，先定位到B+树的叶子节点，
再通过指针定位到行记录

Innodb B+Tree索引体现形式

每个InnoDB在磁盘上存储成2个文件，每一个文件的名字均以表的名字开始，扩展名指出文件类型。

.frm 文件存储表定义；

·ibd 数据与索引文件；

聚集索引

MySQL的Innodb是以主键索引来组织数据结构的，主键索引与行记录是存储在一起的

因为这个特性，InnoDB的表必须要有聚集索引：

1、如果表定义了PK，则PK就是聚集索引；

2、如果表没有定义PK，则第一个非空unique列是聚集索引；

3、否则，InnoDB会创建一个隐藏的row-id作为聚集索引；

InnoDB的聚集索引，也只能够有一个，因为数据行在物理磁盘上只能有一份聚集存储。

InnoDB的普通索引，可以有多个，它与聚集索引是不同的。

InnoDB存储引擎中页的大小默认为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，
也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗3）。
也就是说一个深度为3的B+Tree索引可以维护103 * 10^3 * 10^3 = 10亿条记录。

Innodb中B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。

辅助索引与聚集索引的区别

辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。

当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，

然后再通过主键在聚集索引中找到完整的行记录数据。