周刊(第12期):Page oriented类存储引擎里可能同时存在多种结构

2022-04-10
6分钟阅读时长

引言:本期聊一聊Page oriented类存储引擎内的数据结构组织。在满足“向磁盘读写的基本单位是物理页面”这个大前提下,这类存储引擎的可能同时存在多种结构。


page oriented类存储引擎里可能同时存在多种树形结构

存储引擎的分类

目前接触到的存储引擎,以向磁盘读写方式来分类的话,大体可以分为两类:

  • LSM-Tree结构。
  • Page oriented类。

LSM-Tree是“Log-Structured Merge-Tree”的简称,这类存储引擎写入一条数据的流程大体如下:

  • 向内存以及WAL日志中写入完成,即可认为写入成功。
  • 内存中的数据写满之后,将落盘到所谓的sstable中。
  • sstable分为多层,随着写入进行,不同层次的sstable数据将进行合并。

LSM

(图片引用自LSM树详解 - 知乎)

从上面简单的写入LSM的流程可以看到:无论是写入内存还是磁盘,这类存储引擎在写入新数据时(不是合并sstable流程),磁盘操作的单位是一条记录。而一条记录的长度,是不定长的。

与LSM-Tree类的结构不同的是,Page oriented类的存储引擎,向磁盘发起读写操作的基本单位是页面(page),一个页面通常的大小是2的次方,最小一般是1024字节,比如sqlite的存储,其页面大小为4K(可以修改编译选项配置页面大小)。

以一个物理页面为读写磁盘的基本单位,这也是这一类存储引擎之所以被称为”Page oriented类存储引擎“的原因。本文重点是介绍Page oriented类存储引擎的结构。

Page oriented存储引擎的结构

还是以之前介绍过的sqlite的架构图来开头:

btree架构

这个架构由下往上依次是:

  • 系统层:提供不同系统级API的封装,比如文件读写、加解锁操作等。
  • 物理页面管理层:提供物理页面读写、缓存等功能。
  • 树形结构的实现:根据具体的树形算法,组织物理页面之间的逻辑关系(比如父子页面、兄弟页面),以及单个物理页面之内的数据的组织。

这里的重点是页面管理层和树形结构的实现这两部分:

  • 物理页面管理相当于是磁盘文件的”原材料供应商“,负责对它的客户也就是各种不同结构的实现提供物理页面这一”原材料“的读写、缓存管理,而它对这些材料被客户拿去做成了什么,一无所知。
  • 树形结构的实现,从页面管理器拿到了”物理页面“这个原材料之后,可以按照自己的算法和数据结构任意塑造成任何合理的结构。

数据库文件的物理页面组织和逻辑页面结构

可以看到,Page oriented存储引擎,在满足“向磁盘读写的基本单位是物理页面”这个大前提下,这类存储引擎的可能同时存在多种结构:可能只有B-Tree,也可能只有B+Tree。还有另一种情况是:这类存储引擎内部同时存在多种结构。

以sqlite为例,内部其实就存在两种结构:

  • 存储索引的index tree:结构为B-Tree,键为表索引,值为这一行数据的rowid,其中rowid为隐藏列,创建数据表时自动生成,这一列是自增整数。
  • 存储数据的table tree:结构为B+Tree,键为rowid,值为一行数据。

这两类存储引擎,由于同属于“Page oriented类存储引擎”,因此可以共用同一个物理页面管理器。

数据库文件的rowid全量数据表和索引表

下面,以sqlite中的一个表为例来解释上面这个流程。

首先,创建一个表以及索引:

// 创建数据库COMPANY
CREATE TABLE COMPANY(
   ID             INT      NOT NULL,
   NAME           TEXT    NOT NULL,
   AGE            INT     NOT NULL,
);
// 创建索引
CREATE INDEX id_index ON COMPANY (id);

上面这个建表以及创建索引之后,对应的在这个数据文件中就有了两个树形结构:

  • 存储COMPANY表数据的table-tree。
  • 存储索引idrowid关系的index-tree。

如果向这个表插入数据,比如:

INSERT INTO COMPANY (ID,NAME,AGE) VALUES (1, 'Paul', 32 );

那么,这个插入操作背后实际对应了向这两棵树的插入操作:

  • 首先,将这一行数据插入到table-tree中,同时得到rowid以及插入时候的id
  • 再将第一步得到的rowid以及id插入到index-tree中。

如果使用id_index索引来查询COMPANY表,比如:

select * from COMPANY where id = 1;

这个查询操作也实际上经过了上面这两个表:

  • 首先,通过存储id_indexrowid关系的index-tree,找到id=1对应的rowid
  • 然后,再根据第一步得到的rowid到table-tree中查询到这一行数据。

总结

  • 存储引擎,按照对磁盘读写方式的不同,大体可以分为以下两类:
    • LSM-Tree:写磁盘的基本单位是一条记录,而一条记录大小是不定长的。
    • Page oriented:读写磁盘的基本单位是页面,页面大小为2的次方。
  • “Page oriented”类存储引擎的核心模块是页面管理器和树形结构的实现,前者提供物理页面这一“原材料”的读写操作,对页面内部的结构一无所知;后者组织管理物理页面间的逻辑关系,以及物理页面内部的数据。
  • 在满足“读写磁盘的基本单位是页面”的大前提下,“Page oriented”类存储引擎可以使用各种树形结构,还可能在同一个存储引擎中同时存在多种树形结构。
  • sqlite的实现,内部存在两种不同的树形结构:使用B-Tree来管理索引数据,以B+Tree来管理表数据。这是因为:
    • 索引数据的值只有rowid这样的整型数据,所以单个物理页面内能存储更多的索引数据,适合使用B-Tree这样“高而瘦”的结构来管理这类单条数据很小的数据。
    • 而B+Tree的树形结构是“矮而胖”的结构,更适合存储管理多种不定长的数据。

其他推荐

Git的第一版

2005年4月6日,Git发布了第一版。Git无疑是最伟大的开源软件之一,它的出现极大改变了开源软件的协作、开发方式。

根据这里的“史料”( Git十歲了!Git之父Linus Torvalds說古,大談Git開發秘辛 | iThome )记载:Linus最初只花了10天就写出了第一版可以跑的Git了。

使用Rust编写gRPC服务的初学者指南

最近在使用Rust编写gRPC服务,这篇教程讲解了这部分内容,包括一应一答模式、单向stream模式、双向stream模式都有对应的代码例子,见:Rust gRPC: A beginners guide to gRPC with Rust

在大公司工作的吐槽

一位在美国工作的工程师写的国外大公司(文中是亚马逊)晋升的一些槽点,看起来和国内大公司也差不多,见:关于升职 - Yang Letu - Medium

另外文中还推荐了一个推特上的吐槽:

Noah Kantrowitz on Twitter: “FAANG promo committees are killing Kubernetes: A Short Thread 🧵” / Twitter

《关于威尔史密斯打人,一位台湾老师的社会课引导思考》

关于威尔史密斯打人,一位台湾老师的社会课引导思考,见:https://www.facebook.com/hhsleo/posts/5543635368999794

(上面的文章可能需要FB权限才能打开,也可以看这篇微信公众号的转发:关于威尔史密斯打人,一位台湾老师的社会课引导思考

“我告訴學生,我今天扮演的角色,就像是政治人物或媒體,我蓄意餵養你片面的、我想要你知道的資訊,而有超過7成的人,在這個過程中,被我操弄了,你因為我每次餵養的資訊不同,而產生立場反覆的狀況!明明政治人物應該考慮的是公益,媒體應該報導的是真相,但我若故意要操弄輿論,我只要給你我要你知道的訊息就好,對我不利的,我一概不提。慢慢的,我就可以透過這種愚弄的手法,讓民眾變成對我死忠而深信不疑的禁臠而不自知,我要你膜拜你就膜拜,我要你打砸殺你就打砸殺,我要你剷除異己你就剷除異己,我要你上刀山下油鍋,你還會爭先恐後想要身先士卒。而這樣的現象,正在世界各地上演”

邮件订阅

微信公众号

wechat-account-qrcode