超级苦工
阅读 133
Mysql 百问系列:B+Tree 到底是什么

前言:

以前看过许多关于B+ Tree的文章,当时看了总觉得明白了,可是没过多久就又要忘了。直到我看了掘金小册:Mysql是怎么运行 第7,第8章才终于明白了B+ Tree到底是怎么回事。如果对Mysql内部具体如何实现感兴趣的可以去看小册,我自己看这2章,每章都花了2个小时,毕竟介绍的概念有点多。  我这篇文章相当于对这2章内容的概况总结吧,也可以当导读看,看完这个,再去看小册子可能就没那么吃力了。(ps, 这本小册子是我见过最详细介绍Mysql内部原理的系列文章。)

问题:

1.数据是怎么存储在InnoDB中的
2.如果快速找到一条记录?
3.搜索查找记录的流程是怎么样的?
4.页分裂是什么?

准备工作

没错,首先忘了什么数据结构。
在介绍Buffer Pool时提到过

InnoDB 是以 页(一般为大小为16K) 为单位,从磁盘文件中读取数据 到内存的。 一页 包含多条记录(每页至少要有2条记录)

CREATE TABLE `school` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

delimiter;;
CREATE PROCEDURE idata ( ) BEGIN
	DECLARE
		i INT;
	
	SET i = 1;
	WHILE
			( i <= 25 ) DO
			INSERT INTO school
		VALUES
			( i, 'school' );
		SET i = i + 1;
		
	END WHILE;
	
END;;

delimiter;
CALL idata ( );
复制代码

现在我们创建了一张school 表格,并且插入了25条记录。
现实场景中,一页可以记录几百上千条记录。这里为了方便理解,我们假设一页只能存放5条记录。那么存放情况就如图:

image.png

  • 页与页之间是个双向链表,这样方便范围查找。
  • 页号不一定连续
  • 页中的记录是按Key进行排序的。记录之间也是链表


知道了记录的存储情况,那么要查找某个id的记录,就变成了2个问题:

  1. 怎么快速定位某个Key(这里为id) 存在在哪个页面中?
  2. 怎么在页中快速找到对应Key 的记录?

如何快速定位页

为了快速定位,最容易想到的就是建立字典了,比如(1,200),(2,200),(6,210) 这样的确能够满足快速查找的需求,但是比较浪费空间。
所以转换一下方法:

  • 我们用 key,value 的形式,key 记录每一页的最小值,value 记录对应数据页页号。这样形成了目录项。例如,现在我们有25条记录,每5条记录存放在1页中,那么至少有5页,所以至少有5个目录项
  • 目录项管理也通过页的形式进行。5条记录为1页,那么5个目录项就形成了1个目录页。目录页中的记录(即目录项)也是按照顺序排列

image.png

这就是最简单的一个B+Tree 了。叶子节点为数据页,存放数据。(为什么说对于聚簇索引,索引即数据?)而非叶子节点存放的是目录项。

搜索流程

select * from student where id = 14
复制代码

我们要从查id = 14 的数据。那么从根节点``(这里是页400)开始查找,页400有5个记录,通过二分查找算法进行查找,因为11 < 14 < 16 所以 14记录对应的页和11记录对应的页一样。(请牢记下面2个特性: 目录项中的key 记录的是对应页中key的最小值。并且不管数据页还是目录页其中的记录都是有序的。)
那么14 对应的页就是212号页。然后再到页212号中进行二分查找找到对应数据。

页分裂

如果这个时候再插入一条数据。

insert into student values (28,'王五')
复制代码

由于数据页都满了,所以必须新开一个页面来存放28这条记录。假如这个页面为310页。但同时由于目录页400页也满了,没法记录(28,310)这个目录项,所以又必须加个新的目录页例如410页来存放新的目录项。这个时候由于有2个目录页了,所以需要新建新的目录页来管理目录页,``没错,目录页中的记录不一定是指向数据页的,也可能指向目录页。
看起来会变成下面这样:(图有点丑,有好的画图软件麻烦推荐下)

image.png

通过页分裂,B+Tree 变成了3层。根节点从页400 变成了页420。 看到这里也许你会疑惑你看过的一些文章,B+Tree 的构建并不是这样的。我想说明的是:InnoDB构建过程跟我上面所提的过程是不同的。上面的过程是为了让大家首先了解下随着数据插入,页面(不管是数据页还是目录页)是会增加的。我做出这个流程是为了让大家知道有这么一个流程,但是具体实施,InnoDB的大神考虑的当然比我们要多,可以说是殊途同归吧,方法不同,但要达到的目的是一样的:就是现有页面存放不了新插入的数据时会进行页分裂。具体流程感情的小伙伴可以查看小册子。我介绍最重要的点:

  • 根节点确定后是不会变的。(上面说的根节点从400 变成页420在真实数据库中是不会存在的。)真实的流程类似于:假设一开始只有5条数据都存放在页10当中,那么这个时候页10即是数据页又是根节点。这个时候又新插入一条数据,Innodb会把页10复制得到数据页20,然后对数据页20进行分裂,把数据页20中的部分数据迁移,得到数据页30,然后新插入的数据根据索引的大小插入到对应的页20或页30中。这个时候原来的页10变成了目录页,记录的目录项对应页20,和页30。但是页10还是根节点

总结

  • 数据记录按页为单位存储,每页包含多条记录。
  • 为了方便从众多数据页中找到对应的记录,设计了目录页。目录页和数据页 构成了一棵B+ Tree。
  • B+ Tree 个根节点固定,会随着数据插入进行页分裂。
  • 也许通篇文章都没有提B+ Tree的数据结构到底是什么,但希望通过B+ Tree 在InnoDB 中现实场景应用,让你对B+ Tree 的作用,以及B+ Tree 中叶子节点和非叶子节点到底是什么有个具体的概念。好好理解下文中的搜索过程,和插入流程。再回过头去瞧那些介绍B+Tree的数据结构的文章相信你会更容易懂。任何数据结构都是为某些场景服务而存在的,了解应用场景后再去看具体实现更容易懂而且印象深刻
关注下面的标签,发现更多相似文章
评论
相关推荐
mark

sdsdsdsd...

1231213213112313

123123...

优秀的Node.js第三方库推荐

axiosAxios 是一个基于 Promise 的 HTTP 库,可以用在浏览器和 node.js 中 cheeriocheerio是一个nodejs实现的类似jquery核心功能的一个模块,用它可...

测试呀

广泛大使馆管道施工幅度顺丰大概岁的法国当时法国对```` 范德萨手动阀是的 范德萨士大夫是的****...

1234123412

我靠,怎么删除鸭?...

test

我们的共和国##...

test

i...

BookStack v2.6 发布,功能类似 GitBook 和看云的在线文档管理系统

程序介绍BookStack,分享知识,共享智慧!知识,因分享,传承久远! BookStack,基于 Mindoc、使用Go语言的Beego框架开发的功能类似GitBook和看云的在线文档管理系统,拥有...

联合索引在B+树上的存储结构及数据查找方式

来源: 掘金 原文: 联合索引在B+树上的存储结构及数据查找方式 能坚持别人不能坚持的,才能拥有别人未曾拥有的。 关注编程大道公众号,让我们一同坚持心中所想,一起成长!! 引言 上一篇文章《MySQL...

这是标题

正文在这里...

从0到1实现Promise

来源: SegmentFault 原文: 从0到1实现Promise 前言 Promise大家一定都不陌生了,JavaScript异步流程从最初的Callback,到Promise,到Generato...

测试标题

测试标题测试标题测试标题...

111

222大啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊...

好看

...

生产环境怎么部署呀

另外,貌似界面不支持移动端...

基于Redis的推荐系统开发

原文: 基于Redis的推荐系统开发 介绍推荐系统并不总是需要用到复杂的机器学习技术.只要手头上有足够的数据,你就可以花很少的功夫开发一个推荐系统.一个最简单的推荐系统可以只是从用户感兴趣的表中查找所...

MongoDB性能优化之准备测试数据

很多时候,我们本地的代码运行的好好的,上线后,刚开始没问题,运行一段时间后就有性能问题了,这是为什么呢? 出现这种情况,往往是本地测试数据量不够,上线后,刚开始,数据量很少,也不会有问题,运行一段时间...

MySQL性能优化之准备测试数据

很多时候,我们本地的代码运行的好好的,上线后,刚开始没问题,运行一段时间后就有性能问题了,这是为什么呢? 出现这种情况,往往是本地测试数据量不够,上线后,刚开始,数据量很少,也不会有问题,运行一段时间...

Android 使用 HTTPS

来源: 简书 原文: Android 使用 HTTPS 如果你的项目的网络框架是okhttp,那么使用https还是挺简单的,因为okhttp默认支持HTTPS。传送门 Android 使用 HTTP...

Android 适配一篇就够 - 编译版本?support?API 兼容?图片适配?

来源: 简书 原文: Android 适配一篇就够 - 编译版本?support?API 兼容?图片适配? 本文介绍 Android 不同系统及图片资源的常见适配问题。 compileSdkVersi...