知乎上有个问题：如何实现一个数据库？手痒忍不住又水了一篇。以计算机中最常用的分析、理解问题的思想，我们可以从两个维度：逻辑和物理，来思考如何实现一个数据库。
逻辑维度
数据模型（对外，面向用户）
想要实现一个数据库，首先你得定义给给用户什么样的数据模型？在前些年，这些可能不是个问题，彼时，数据库约等于关系型数据，约等于 Oracle/SQLServer/MySQL/PostgreSQL 。但随着数据量的不断增大、用户需求的不断细化，关系模型已经不能一招鲜、吃遍天。
作者：木鸟杂记 https://www.qtmuniao.com/2022/12/11/how-to-build-a-database 转载请注明出处
时下（2022）常见的有 Relational 模型（Oracle）、Document 模型（MongoDB）、Search Engine（Elasticsearch） KV 模型（Redis）、Wide Column 模型（Cassandra），Graph 模型（Neo4j）、Time Series 模型（InfluxDB）。更多模型及其产品可见 DB-Engines 排名[1]。
数据组织（对内，面向系统）
数据库，本质上就是存取数据。从程序员的角度来说，就是如何在计算机存储层次体系[2]中组织数据。
学过操作系统、计算机体系结构的同学都知道，对于计算机来说：
- 离 CPU 越近，如寄存器（Register）、缓存（Cache）、内存（Memory），速度越快、容量越小、造价越昂贵。
- 离 CPU 越远，如闪存（SSD）、磁盘（Disk）、磁带（Tape），速度越慢、容量越大、造价越便宜。
近年出现了一些新产品。如可持久化内存（Persistent Memory[3]），代表产品是 Intel 的傲腾[4]，大致介于内存和SSD 之间，但由于定位不明确（向上走不够快，向下走不够便宜），还没能大规模应用；又如云上的对象存储，代表产品是 AWS S3[5]，大致是几种非易失性存储的替代产品，价格足够感人、带宽足够高、扩展性足够强，因此大获成功，已经成为云上的存储基础设施，所有需要上云的数据库都会考虑在底层使用对象存储。
物理维度
数据库在物理上可以粗分为查询引擎和存储引擎。从感性上理解，存储引擎负责数据在外存的组织与将数据载入内存，查询引擎负责解析用户查询为数据层的读写与数据在内存中的计算。
限于篇幅，此处我们略去了另外几个重要的模块：并发控制、宕机恢复等。
查询引擎
每个数据模型都有与其契合的数据查询方式。当然，我们最熟知便是 SQL 之于关系模型。SQL 也是一门计算机语言，既是语言，就需要一套所有类似编译器前端需要流程：
Parser：对使用形式语言抽象的查询语法，利用自动机模型进行解析，构建抽象语法树[6]
Validator：对语法树进行依据 Schema 进行校验
不同的是，由于查询语言属于声明式语言[7]，因此在执行上可以有很大的自由发挥的空间，所谓：
- Planner：使用模式信息将语法树中对用户有意义的元素（如名字），转为内部标识（如 ID）
- Optimizer：利用关系代数对计划树进行逻辑变换、利用统计信息对执行路径（比如使用哪个索引）进行选择，以期付出最小代价，实现用户查询需求
- Executor：将优化好的执行计划在存储层进行执行，真正的去访问我们存储于计算机体存储体系结构中的数据
树是在数据系统中应用非常深入的一种数据结构。大部分的数据查询，在逻辑上都可以抽象为对数据集的不断变换，对应到树中：
- 叶子节点：数据集合。有不同粒度，如一列、一行、一个表
- 中间节点：变换算子。有不同类型，如 selection、project、join、dedup、top 等
广义上来说，像 Hadoop、Spark、Flink 这些大数据范畴的中间件，也都有查询引擎的影子，只不过要么算子更为简单、要么侧重多机、要么侧重流等等。
存储引擎
对应数据组织，系统程序员需要根据数据库应用场景，在外存（SSD 和 Disk 中）组织数据。如：
- 考虑事务型还是交易型：在列存还和行存中权衡
- 考虑读写比例：在原地更新（B+ tree）和增量更新（LSM-Tree）间权衡
- 考虑安全性：在是否加密间权衡
然后，考虑如何将数据从外存向内存搬运。
- 我们知道，外存尺寸要比内存大的多，因此只能将部分数据载入内存，供用户访问。那每次载入哪些数据、每次逐出哪些数据，就是一个需要设计的策略，或者说算法——Buffer Pool，LRU
- 我们又知道，IO 相比 CPU 慢的多，数据访问多有局部性原理，因此每次去外存拿数据总倾向于“批发”，那每次批发的量，也是一个需要考量的点——Block，Page
[8]
最后，还需要考虑如何将数据从内存向每个 CPU 腾挪，准确来说，这已经属于查询引擎范畴，为了逻辑连贯，我们将其放在此处。
- 单核 CPU 遭遇瓶颈，只能向多核发展，那如何将内存中的数据喂给每个 CPU —— Cache Line 对齐
- 多个 CPU 需要进行协同，如何编排多个 CPU 的执行，如何串接多个 CPU 的输入输出——锁、信号量、队列
而数据如何在内存中组织，是两个引擎都会涉及到的事情。
- 行存还是列存。后者可以使用 SIMD 优化。
- 稀疏还是稠密。NULL 数据多少。
- 同构还是异构。是否需要支持动态类型和嵌套类型。
然而，上述只考虑了数据在单机中的组织。如果单机无法提供目标存储容量和吞吐量，就需要考虑分布式系统——将多个机器通过网络连接在一起，作为一个整体对外提供服务。
于是我们又引入了很不靠谱（相比单机总线）的网络和难以严格同步的时钟，如何对齐进行处理，又是另外一个长长的故事了。虽然当代数据库无一不需要多机协同，但限于篇幅问题，就此打住了。对此感兴趣的可以看看我们的 DDIA 读书会的分享：https://ddia.qtmuniao.com/
参考
- 数据库权威排名 DB-Engines https://db-engines.com/en/ranking
- 计算机存储体系 https://en.wikipedia.org/wiki/Memory_hierarchy
- 可持久化内存 https://en.wikipedia.org/wiki/Persistent_memory
- 英特尔® 傲腾™ 持久内存 https://www.intel.cn/content/www/cn/zh/architecture-and-technology/optane-dc-persistent-memory.html
- Amazon Simple Storage Service (Amazon S3) https://aws.amazon.com/cn/s3/
- 自动机编程 https://en.wikipedia.org/wiki/Automata-based_programming
- 声明式语言 https://en.wikipedia.org/wiki/Declarative_programming
- 访问的局部性原理 https://en.wikipedia.org/wiki/Locality_of_reference
