查看原文
其他

手写一个简单的Database7(译文)

花家舍 GreatSQL社区 2024-07-08

* GreatSQL使

前文回顾


译注:cstack在github维护了一个简单的、类似sqlite的数据库实现,通过这个简单的项目,可以很好的理解数据库是如何运行的。本文是第七篇,主要是对B-tree的介绍

Part 7 B-Tree简介

B-tree是SQLite用来表示表和索引的数据结构,所以B-tree是非常中心的想法。这个主题主要是介绍B-tree数据结构,所以不会有任何的代码。

为什么说对于数据库来说,树是非常好的数据结构呢?

  • 查找特定的value很快(对数时间花销,loga N)
  • 插入一行或者对查询到的数据删除很快(再平衡使用常量时间)
  • 遍历一个范围内的value很快(不像hash map)

B-tree不同于二叉树(“B”可能代表发明人的名字,但也可以代表“Balanced”)。这里是一个B-tree例子:



B-Tree 例子(https://en.wikipedia.org/wiki/File:B-tree.svg)

不像二叉树每个节点只能有两个子节点,B-tree的每个节点可以有两个以上的子节点。每个节点最多可以有 m 个子节点,其中 m 叫做树的“order”(或者叫“阶”)。为了保持树的尽量平衡,我们还要求节点必须至少有 m / 2 个子节点(四舍五入)。

但还有一些例外:

  • 叶子节点没有子节点
  • 根节点的子节点数可以少于 m,但至少要有两个
  • 如果根节点也是叶子节点(树只有一个节点),那它有0个子节点

上面的描述的是一个B-tree,SQLite用它来存储索引。为了存储表数据,SQLites使用一种B-tree的变体,称为B+tree。


B-treeB+ tree
发音“Bee Tree”“Bee Plus Tree”
用来存储索引
内部节点是否存储key
内部节点是否存储value
每个节点的子节点数
内部节点 vs 叶子节点相同结构不同结构

在我们开始实现索引之前,我将只讨论B+tree,但这里将其称为 B-tree 或者 btree。

有子节点(children)的节点被称为“内部”节点(internal node),内部节点和叶子节点在结构上不同:

m阶tree内部节点叶子节点
存储key和指向子节点的指针key和value
key的数目最多m-1个越多越好
指针的数目keys + 1
value的数目与key的数目相同
Key的用途用来路由与value成对存储
存储value?

这里通过一个例子来看一下,当插入一个元素时,B-tree是怎样发生结构变化的。为了让事情看起来更容易理解,这棵B-tree的阶(order)设置为3(m=3),也就是说:

  • 每个内部节点最多有三个子节点(m)
  • 每个内部节点最多有两个key
  • 每个内部节点至少两个子节点(m-1)
  • 每个内部节点至少一个key

一棵空树只有一个节点:根节点。根节点最开始也作为叶子节点,有0个键值对(key/value):


空的btree

如果我们插入两个键值对(超过两个键值对,节点需要分裂,参考上面规则),他们会按顺序排序存放在叶子节点中。


一个节点的btree

我们假设了节点的容量是两个键值对儿。当我们插入另外一个的时候,就不得不分裂叶子节点了,分裂后的两个节点每个存放之前一半的键值对。分裂后的两个节点都变成了内部节点,同时也变成了一个新的节点的子节点,这个新的节点变成了根节点。


两层的btree

图中的内部节点(也是根节点)有一个key和两个指针指向子节点(就是那两条线)。如果我们想查找一个key,key小于或等于5,我们查看左子树。如果查找的key大于5,就查看右子树。
现在,准备插入一个新的key "2"。首先,我们查找它将位于哪个叶节点(如果它在树中存在的话),这样就到达了左侧叶子节点。这个节点是满的,所以把这个叶子节点进行分裂(split),并在父节点创建新的条目。


四节点的btree

现在继续增加key,18 和 21 。现在又到了不得不分裂的情况,但是在父节点中已经没有空间来增加新的键值对儿了。


内部节点没有空间

解决方法就是分裂根节点为两个内部节点,然后创建一个新的根节点作为两个内部节点的父节点。


三层的btree

树只是在我们分裂根节点的时候才会增加深度。每个叶子节点都有相同的深度和接近相同的数量的键值对儿,所以树能够保持平衡和快速的进行查找。

我暂时先不讨论从树中删除键的操作,推迟到实现插入操作以后。

当我们实现这个数据结构时,每个节点都对应一个page。根节点将在page0中存在。节点中的子节点指针将简单的使用包含子节点的page number。

下一次,我们开始实现btree。



《深MGR
课程已全更新完毕欢迎点击观看~
https://www.bilibili.com/video/BV1Da411W7Va?spm_id_from=333.999.0.0&vd_source=ae1951b64ea7b9e6ba11f1d0bbcff0e4

文章推荐:



关于 GreatSQL

GreatSQL是由万里数据库维护的MySQL分支,专注于提升MGR可靠性及性能,支持InnoDB并行查询特性,是适用于金融级应用的MySQL分支版本。

GreatSQL社区官网: 
https://greatsql.cn/

Gitee: 
https://gitee.com/GreatSQL/GreatSQL

GitHub: 
https://github.com/GreatSQL/GreatSQL

 Bilibili

https://space.bilibili.com/1363850082/video



捉虫活动详情:https://greatsql.cn/thread-97-1-1.html

社区博客有奖征稿详情:https://greatsql.cn/thread-100-1-1.html

(对文章有疑问或者有独到见解都可以去社区官网提出或分享哦~)


&QQ

可扫码添加GreatSQL社区助手微信好友,送验证信息“加群”加入GreatSQL/MGR交流微信群,亦可直接扫码加入GreatSQL/MGR交流QQ群


QQ


想看更多技术好文,点个“在看”吧!

继续滑动看下一个
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存