本文是《从零实现 SQL 数据库》课程的加餐文章，描述如何在简历中写这个项目，以及一些可能的面试问题&答案，对课程感兴趣的同学可以查看课程主页： https://roseduan.cn/course/
一、简历上如何写这个项目？
项目名称：sqldb: 极简关系型 SQL 数据库
项目概述：sqldb 是使用 Rust 实现的简易关系型 SQL 数据库，支持常见的表管理、SQL 数据查询与存储等功能，支持 ACID 的事务特性，帮助理解生产级关系型数据库的架构原理和设计细节，以及代码层面的具体实现。
项目架构：主要分为了计算层和存储层，存储层支持基于磁盘和内存的存储引擎，并且在存储之上，使用快照隔离的方法实现了 ACID 事务。计算层按照标准的 SQL 数据库架构实现，主要有 SQL 解析、执行计划和执行器。执行器和存储事务层的读写接口进行交互，实现数据的具体存储和查询。
设计细节：
SQL 的词法和语法解析器 执行计划节点构建 执行引擎的执行逻辑 基于内存和磁盘的存储设计 ACID 事务的设计 表达式计算 可视化命令行
项目功能：支持了常见的 SQL 语法，包含：
创建和删除表：Create Table、Drop Table 语法，并且支持 Integer、String 等常见数据类型，支持 (Not) Null、Default、Index 等建表约束 DML：数据插入 Insert Into、数据删除 Delete From、数据更新 Update，数据查询 Select，select 支持投影、排序、分组、limit/offset、where 过滤、agg 聚集函数、join 子句 事务：支持 Begin、Commit、Rollback 语句 其他语句：比如 Show Tables 查看表结构，Explain 语句输出 SQL 执行计划
二、常见面试问题
1. 请简单介绍一下这个项目
结合上面的项目概述、架构、功能中的描述回答即可。
2. 为什么使用 Rust 来实现？
选择 Rust 主要是因为 Rust 具有出色的性能和内存管理能力。作为系统级编程语言，Rust 提供了安全性和高效性，Rust 的所有权模型和内存管理可以帮助避免传统 C/C++ 编程中的内存泄漏和数据竞争问题。此外，Rust 还具有现代化的工具链，支持高效的编译和静态分析，这对构建高性能数据库是非常重要的。
3. 项目中的存储引擎具体是怎么设计的？
存储引擎主要是有内存和磁盘，对外提供统一的读写接口。
内存使用 BTree，主要是使用了 Rust 标准库中的 BtreeMap。
磁盘存储基于简单的日志追加式的 bitcask 存储模型，bitcask 模型是一个高效、简洁的存储引擎，数据以日志的方式写到磁盘文件中，内存中维护了 key 和对应的索引信息。读取的时候直根据 key 从内存中获取到对应的索引，然后根据索引读取磁盘文件中的数据即可。
4. ACID 的事务具体是怎么实现的？
sqldb 中的事务基于快照隔离实现，主要有以下具体的设计细节：
数据快照：每个事务在开始时会获得一个快照。这意味着事务只会看到在事务开始时已提交的数据，不会看到其他事务的未提交修改。即使其他事务修改了数据，当前事务仍然只看到自己开始时的数据版本。
多版本并发控制（MVCC）：每个数据项维护多个版本（即多版本并发控制）。每次数据修改都会创建一个新的版本，事务通过其开始时的快照读取相应的版本，每个版本会关联一个全局唯一的事务版本号。
读写冲突检测：快照隔离会防止并发冲突（如脏读、不可重复读、幻读）。当一个事务修改了数据并提交后，其他事务无法看到其未提交的修改。如果两个事务同时读取相同的数据项并尝试修改它们，会检测到冲突并使其中一个事务回滚，避免不一致的结果。
5. 这种设计是怎么保证 ACID 特性的？
A 原子性：通过事务写入数据，只有调用 Commit 之后，才会生效，否则已经写入的中间数据是无效的。要么调用 Rollback 进行回滚，所以一个事务中的数据要么提交，要么回滚，保证了原子性。 C 一致性：一致性保证数据库从一个有效的状态转换到另一个有效的状态，在原子性和隔离性都满足的情况下，一致性也能够得到保证。 I 隔离性：主要是快照隔离，通过 MVCC 多版本并发控制，以及数据冲突检测机制，能够避免脏读，不可重复读，幻读的问题。是一种介于传统的串行化和可重复读之间的隔离级别。 脏读：事务在开始的时候获取了一个全局快照，只能读到对当前事务可见的数据，其他未提交的事务不能读到，避免了脏读。 不可重复读：通过全局快照，其他事务的修改就算提交了，也不会对当前事务可见，也就是说事务在运行的过程中，始终只能看到其开始时的状态，解决了不可重复读问题。 幻读：事务在读取的时候，如果事务版本号比当面版本号更大，说明是更加新的事务提交的数据，也不可见，解决了幻读的问题。 D 持久性：通过磁盘存储引擎，数据写入之后，能够安全的保存到持久化存储中。
6. SQL 语句是怎么解析并执行的？
SQL 解析：首先使用词法分析器（Lexer）和语法分析器（Parser）将 SQL 查询转换成一个抽象语法树（AST）。词法分析器将 SQL 语句分割成各个语法单元（例如关键字、标识符 Token、运算符），语法分析器 Parser 则检查 SQL 语句是否符合 SQL 语法规范，并生成抽象语法树 AST。
执行计划生成：根据 AST 构建执行计划。执行计划定义了如何访问和处理数据库中的数据。数据的增删改都对应了具体的执行节点，例如 Select 会决定使用索引还是全表扫描，或者如何使用 JOIN、Group By 等操作。
执行器：执行器根据执行计划访问数据库中的数据，执行相应的操作。执行器会与存储引擎交互，从内存或磁盘中读取数据，并根据操作修改数据。
7. SQL 解析时，如何处理不同类型的 SQL 语法？
SQL 解析主要在词法分析和语法分析阶段完成，在 Lexer 中将 SQL 拆分为不同各个语法单元，例如关键字、Token、运算法等。在 Parser 阶段会根据预定义的语法规则进行解析，如果不符合预期的话，则直接报出对应的语法错误。如果是一个有效的 SQL 语句则生成对应的抽象语法树。
8. 如何保证数据的崩溃恢复？
sqldb 中实现了基于磁盘的存储引擎，数据写入的时候会首先写入到磁盘存储引擎中，这能够保证持久性。如果在写入的过程中发生了异常，由于事务原子性机制的保证，中间状态的数据并不会生效，因此能够有效的保证数据库恢复到正确的状态。
9. 如何处理表达式计算？
sqldb 中使用了基于运算符优先级的算法 Precedence Climbing
来进行表达式计算，它本质上是一种递归下降解析表达式的方法，通过递归地处理运算符和操作数来解析表达式，并根据运算符的优先级和结合性来确定表达式的计算顺序。
这种算法的核心思想是利用运算符的优先级进行“爬升”（Climbing），以决定表达式的结构和计算顺序。
在 sqldb 当中，由于运算符众多，支持了几种最常用的运算符加减乘除。
如果面试官要求代码演示，可以参考：https://github.com/rosedblabs/rust-practice/tree/main/expr-eval
10. 如何支持 SQL 语法中的聚合函数和 Join 操作？
聚合函数（如 SUM、AVG、COUNT）在执行引擎中通过遍历结果集并进行相应的计算来实现。在执行查询时，执行引擎会根据执行计划确定是否需要对结果集进行分组，并计算聚合结果。
对于 JOIN 操作，执行引擎会根据查询类型选择合适的连接算法（如 Nested Loop Join 或 Hash Join）来完成数据表的连接操作。
11. 建表时既然支持 Index，那么索引是如何实现的？
sqldb 中的索引实现比较简单，借助 KV 存储引擎的底层结构，实现了类似哈希索引的功能。在实现上，主要是针对索引列，单独存储了一个 Key/Value 对，key 就是表名+索引列数据，value 是主键 id。这样在通过索引列进行查询的时候，能够快速定位到具体的数据，并且取出其中的主键 id 信息，然后再根据主键 id 获取数据。
并且在数据进行增删改的时候，如果索引列也进行了更新，那么也需要对索引的数据进行维护。
12. 如果要将这个数据库扩展成一个生产级别的数据库，你会考虑哪些方面？
要将这个数据库扩展成生产级别的数据库，可以从以下几个方面进行改进：
完善 SQL 语法：增加更多样化的 SQL 语法，支持更加复杂的查询场景 性能优化：增加查询缓存、优化索引结构、增加并行查询处理等，以提高性能。 高可用性和容错：实现数据的自动备份、故障恢复和数据复制机制，确保高可用性。 安全性：增加访问控制、加密、审计日志等功能，确保数据安全性。 易用性：完善命令行工具，提供图形化界面，增强用户友好性。
