超级苦工
阅读 297
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的数据结构的文章相信你会更容易懂。任何数据结构都是为某些场景服务而存在的,了解应用场景后再去看具体实现更容易懂而且印象深刻
关注下面的标签,发现更多相似文章
评论
相关推荐
测试图片

...

js正则校验,match和test的区别

test()var str=&#39;sad13123dfa4v564d5f8fb5sf&#39;; var re=/\d+/g; alert(re.test(str));// 返回布尔值,是否匹配正...

这是一篇文章

this is a blog这是二级标题不错的博客...

手摸手教你撸一个form表单自动收集校验装饰器

项目环境搭建 create-react-app 需要eject后支持decorator装饰器语法 没了 npx create-react-app fakeAntdFormDemo cd fakeAnt...

test

sss...

测试评论开始

(毕设项目)Vue+Go前端后端一体化 企业级微服务网关项目完整无密云盘分享图片 (毕设项目)Vue+Go前端后端一体化 企业级微服务网关项目 【点击下载】不管是基于Java、Python、PHP,还...

测试评论出入参数

准备开始...

测试

测试...

测一测

优点:前端耗时少。因为后端拼接完了html,浏览器只需要直接渲染出来。有利于SEO(搜索引擎优化)。因为在后端有完整的html页面,所以爬虫更容易爬取获得信息,更有利于seo。无需占用客户端资源。即解...

测试

安装 socialiteproviderssocialiteproviders 为 Laravel Socialite 提供了更多的第三方登录方式,基本上你需要的,都能在这里找到。这个组件方便我们完成...

(毕设项目)Vue+Go前端后端一体化 企业级微服务网关项目完整无密云盘分享

(毕设项目)Vue+Go前端后端一体化 企业级微服务网关项目 【点击下载】不管是基于Java、Python、PHP,还是基于Go的网站,网站流量越高,对网关性能要求越高,尤其是亿级流量网站中,网关更是...

2020最新慕课网全站课程分享实战就业班全部都有云盘链接分享

*2020 慕课网所有课程全部都有,百分百高清原画,所有课程全部包含课件源码,完整无密,百度网盘链接分享,官方同步永久包更新! *官方品质,信誉保障!所有课程全部支持试看任何章节! *【点击下载】 *...

Node.js+Koa2+MySQL打造前后端分离精品项目《旧岛》完整无密 云盘分享

Node.js+Koa2+MySQL打造前后端分离精品项目《旧岛》完整无密 【点击下载】Nodejs逐渐成为前端同学进阶的必修技术之一,本课程将带大家从0到1开发一个前后端分离的精品项目《旧岛》,手把...

Learn Go in Y Minutes

转自:https://learnxinyminutes.com/docs/zh-cn/go-cn/ 发明 Go 语言是出于更好地完成工作的需要。Go 不是计算机科学的最新发展潮流,但它却提供了解决现实...

实战企业级项目 践行App重构之路

实战企业级项目 践行App重构之路 完整无密 随着企业级App功能不断累加强大,App代码质量下降、设计缺陷、难以维护、迭代困难等问题越来越突出,App的重构迭代已经成为Android工程师急需解决的...

你好,米粒

米粒小米粒小小米粒其实有时候很孤单...

大学计算机必修课新讲--编译原理+操作系统+图形学

大学计算机必修课新讲--编译原理+操作系统+图形学 无密 [【点击下载】](http://www.97yrbl.com/t-310.html)编译原理,操作系统,图形学被称为程序员的三大浪漫,不仅因为...

2020最新慕课网全站课程完整无密网盘分享

*2020 慕课网所有课程全部都有,百分百高清原画,所有课程全部包含课件源码,完整无密,百度网盘链接分享,官方同步永久包更新!*官方品质,信誉保障!所有课程全部支持试看任何章节!*下载地址:&nbsp...

asdfasdfasdf

asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdf ~asdfasdfasdfasdfsadfasdfffffffffffffff...

asdfasdfasdf

tttttt...