周刊（第12期）：Page oriented类存储引擎里可能同时存在多种结构
引言：本期聊一聊Page oriented类存储引擎内的数据结构组织。在满足“向磁盘读写的基本单位是物理页面”这个大前提下，这类存储引擎可能同时存在多种结构。
page oriented类存储引擎里可能同时存在多种树形结构
存储引擎的分类
目前接触到的存储引擎，以向磁盘读写方式来分类的话，大体可以分为两类：
• LSM-Tree结构。
• Page oriented类。
LSM-Tree是“Log-Structured Merge-Tree”的简称，这类存储引擎写入一条数据的流程大体如下：
• 向内存以及WAL日志中写入完成，即可认为写入成功。
• 内存中的数据写满之后，将落盘到所谓的sstable中。
• sstable分为多层，随着写入进行，不同层次的sstable数据将进行合并。
（图片引用自LSM树详解 - 知乎[1])
从上面简单的写入LSM的流程可以看到：无论是写入内存还是磁盘，这类存储引擎在写入新数据时（不是合并sstable流程），磁盘操作的单位是一条记录。而一条记录的长度，是不定长的。
与LSM-Tree类的结构不同的是，Page oriented类的存储引擎，向磁盘发起读写操作的基本单位是页面（page），一个页面通常的大小是2的次方，最小一般是1024字节，比如sqlite的存储，其页面大小为4K（可以修改编译选项配置页面大小）。
以一个物理页面为读写磁盘的基本单位，这也是这一类存储引擎之所以被称为”Page oriented类存储引擎“的原因。本文重点是介绍Page oriented类存储引擎的结构。
Page oriented存储引擎的结构
还是以之前介绍过的sqlite的架构图来开头：
这个架构由下往上依次是：
• 系统层：提供不同系统级API的封装，比如文件读写、加解锁操作等。
• 物理页面管理层：提供物理页面读写、缓存等功能。
• 树形结构的实现：根据具体的树形算法，组织物理页面之间的逻辑关系（比如父子页面、兄弟页面），以及单个物理页面之内的数据的组织。
这里的重点是页面管理层和树形结构的实现这两部分：
• 物理页面管理相当于是磁盘文件的”原材料供应商“，负责对它的客户也就是各种不同结构的实现提供物理页面这一”原材料“的读写、缓存管理，而它对这些材料被客户拿去做成了什么，一无所知。
• 树形结构的实现，从页面管理器拿到了”物理页面“这个原材料之后，可以按照自己的算法和数据结构任意塑造成任何合理的结构。
可以看到，Page oriented存储引擎，在满足“向磁盘读写的基本单位是物理页面”这个大前提下，这类存储引擎的可能同时存在多种结构：可能只有B-Tree，也可能只有B+Tree。还有另一种情况是：这类存储引擎内部同时存在多种结构。
以sqlite为例，内部其实就存在两种树形结构：
• 存储索引的index tree：结构为B-Tree，键为表索引，值为这一行数据的
rowid，其中rowid为隐藏列，创建数据表时自动生成，这一列是自增整数。• 存储数据的table tree：结构为B+Tree，键为
rowid，值为一行数据。
这两类存储引擎，由于同属于“Page oriented类存储引擎”，因此可以共用同一个物理页面管理器。
下面，以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。• 存储索引
id到rowid关系的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_index到rowid关系的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[2] ）记载：Linus最初只花了10天就写出了第一版可以跑的Git了。
使用Rust编写gRPC服务的初学者指南
最近在使用Rust编写gRPC服务，这篇教程讲解了这部分内容，包括一应一答模式、单向stream模式、双向stream模式都有对应的代码例子，见：Rust gRPC: A beginners guide to gRPC with Rust[3]。
在大公司工作的吐槽
一位在美国工作的工程师写的国外大公司（文中是亚马逊）晋升的一些槽点，看起来和国内大公司也差不多，见：关于升职 - Yang Letu - Medium[4]
另外文中还推荐了一个推特上的吐槽：
Noah Kantrowitz on Twitter: "FAANG promo committees are killing Kubernetes: A Short Thread 🧵" / Twitter[5]
《关于威尔史密斯打人，一位台湾老师的社会课引导思考》
关于威尔史密斯打人，一位台湾老师的社会课引导思考，见：https://www.facebook.com/hhsleo/posts/5543635368999794
（上面的文章可能需要FB权限才能打开，也可以看这篇微信公众号的转发：关于威尔史密斯打人，一位台湾老师的社会课引导思考）
“我告訴學生，我今天扮演的角色，就像是政治人物或媒體，我蓄意餵養你片面的、我想要你知道的資訊，而有超過7成的人，在這個過程中，被我操弄了，你因為我每次餵養的資訊不同，而產生立場反覆的狀況！明明政治人物應該考慮的是公益，媒體應該報導的是真相，但我若故意要操弄輿論，我只要給你我要你知道的訊息就好，對我不利的，我一概不提。慢慢的，我就可以透過這種愚弄的手法，讓民眾變成對我死忠而深信不疑的禁臠而不自知，我要你膜拜你就膜拜，我要你打砸殺你就打砸殺，我要你剷除異己你就剷除異己，我要你上刀山下油鍋，你還會爭先恐後想要身先士卒。而這樣的現象，正在世界各地上演”
引用链接
[1] LSM树详解 - 知乎: https://zhuanlan.zhihu.com/p/181498475[2] Git十歲了！Git之父Linus Torvalds說古，大談Git開發秘辛 | iThome: https://www.ithome.com.tw/news/95088[3] Rust gRPC: A beginners guide to gRPC with Rust: https://dev.to/anshulgoyal15/a-beginners-guide-to-grpc-with-rust-3c7o[4] 关于升职 - Yang Letu - Medium: https://yorotoo.medium.com/%E5%85%B3%E4%BA%8E%E5%8D%87%E8%81%8C-55dbe62ebaf[5] Noah Kantrowitz on Twitter: "FAANG promo committees are killing Kubernetes: A Short Thread 🧵" / Twitter: https://twitter.com/kantrn/status/1511791378497384454
往期推荐：