周刊（第6期）：《sqlite 3.36 btree实现解析》番外篇
引言：从2021年9月份开始要探索生产级btree存储引擎的实现，到2022年2月整理完毕发布《sqlite 3.36 btree实现解析》的系列文章，我花费了小半年的时间，本期会聊聊整个过程下来我的一些想法。
《sqlite 3.36 btree实现解析》番外篇
时间回到2021年9月份。彼时，因为工作的关系，要研究一下生产级btree存储引擎的实现，在此之前我大体对btree、b+tree的数据结构和算法有个了解，见：
但是，一个生产级的产品，对比教科书的示范型代码，还是有很大的区别的，具体来说，我当时不明白以下这些生产级存储引擎的问题如何解决：
- 如何存储变长的数据？
- 如何存储数据大小超过一个物理页面的数据？
- 如何利用被回收的空间？
- 如何处理崩溃恢复？
- 读写并发如何处理？
- …
为了解答这些疑问，先后去翻阅InnodDB、WiredTiger、sqlite的文档，但是这些项目代码量都太大了，以我当时的程度，无法马上找到很具体的解答。
事情的突破在从网上查找文章时看到的这一篇文章：How Database B-Tree Indexing Works - DZone Database，这是一篇解释btree工作原理的文章，这篇文章同时还列出了一个项目：madushadhanushka/simple-sqlite: Code reading for sqlite backend，这个项目的作者，将sqlite2.5版本中btree的实现，单独抽取出来形成了一个独立的KV库，可以编译通过使用。
看到这个项目的时候，我的感觉就是如获至宝，因为虽然只有几千行的代码量，但是解答了很多上面提到的疑问，“麻雀虽小五脏俱全”，我花了几天的时间整体阅读了解了原理，这个项目给我打开了研究生产级btree存储引擎的突破口。
在这以后，考虑到2.5版本的sqlite已经是2002年的作品，距离现在时间太久了，还想接着了解后面做了那些改进，又接着阅读了3.6.10版本的实现，找这个版本的原因，是因为这是sqlite官方在github上同步的第一个版本，那时候仍然步子不敢迈得太大。
又花了一个多月把这个版本的btree实现了解以后，我了解到在这之后的版本里，sqlite做了另一个重大的更新：在页面管理部分引入了WAL机制，加上前面两个版本阅读下来累积的信心，就接着找当时还是最新的3.36版本的实现来阅读，这又花了一个多月的时间。
这以后，就是逐步将整理的笔记写成文档了，后续的事情不表，都在这几篇文档里。
回头看这整个流程，我自己的感受是：
- “问题驱动”可能是效率更高的学习方式，带着问题出发、找到自己疑问的答案，能更快的学习某个知识。
- 生产级的实现和教科书的区别很大，后者更多的是讲解原理，而生产级实现考虑更多的是各种实际生产中的边际情况。如果只了解原理，而不去具体做实现，对事情的理解最后只能浮于表面。
- 找到那个精简实现是这个过程里的“突破口”，原因在于：如果一上来看的很成熟的版本，而且你在这个领域积累的不深，那么很可能会导致丢失了很多“上下文（context）”情景，给阅读、理解带来很大困难。下次再遇到类似的问题，我会按照这次的经验，先尝试回退到之前的更简单的版本，看看在那里能不能跟上作者的思路，攻克简单的实现之后，再尝试最新的版本。
- 除了数据库领域以外，有一些别的领域，在教学的时候会让学生参与实现一个简单的项目。这类型的项目虽然简单，但是五脏俱全，能够让学生了解这个领域的概貌，我把这种流程称为“破解神秘感”。如我最开始提到的那些疑问，如果在这之前做过数据库相关的作业，应该会有个大体的想法。
这篇番外篇的番外篇
sqlite的注释
除了这些以外，sqlite的代码风格也很好，尤其是注释写的非常详尽。
有一种说法，“好的代码都是自解释的，无需多做注释”。我对这句话有一些不太一样的看法，因为即便再好的代码，如果只看代码的话，对整个的架构、结构很难了解。这一点sqlite就做的很好，在代码中会写上类似文档一样的注释来解释结构，比如有这么一段解释btree内部结构的注释文档：
/
** This file implements an external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
** "Sorting And Searching", pages 473-480. Addison-Wesley
** Publishing Company, Reading, Massachusetts.
**
** The basic idea is that each page of the file contains N database
** entries and N+1 pointers to subpages.
**
** ----------------------------------------------------------------
** | Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
** ----------------------------------------------------------------
**
** All of the keys on the page that Ptr(0) points to have values less
** than Key(0). All of the keys on page Ptr(1) and its subpages have
** values greater than Key(0) and less than Key(1). All of the keys
** on Ptr(N) and its subpages have values greater than Key(N-1). And
** so forth.
*/
如果不写这些注释，读者想要理解作者的思路的话，仅凭代码是很困难的。
这里只是抽取了sqlite代码注释中的一小部分，我读代码下来的感觉，sqlite的注释可以说是“保姆级别”的。“写代码是表达自己，读代码是去理解别人”（见为什么说读代码比写代码难？ - 知乎），可以说sqlite的作者为了让别人更好的理解自己，尽力了。
对应的，我也看过那种几乎没有注释、变量函数名都是缩写的代码，这样的代码作者，可能就不是很像让别人读懂ta。
sqlite几个相关的链接
可以在这里（History Of SQLite Releases）找到sqlite的release历史，进而下载到对应版本的代码。以2.5版本为例，发布于2002-06-17这一天，我用代码统计工具统计了一下，代码量仅有31188行（包括注释）：
BTW：不知道sqlite 2.5版本，对比一些数据库实验课程的大作业，复杂度如何，感觉以早期sqlite代码来入门数据库学习也是足够的，前提是有足够的耐心和时间。
而3.36版本发布于2021-06-18这一天，代码量已经到了21W行，前后相隔19年：
还可以在Release History Of SQLite看到不同版本新增的特性、bug fix等，比如可以看到WAL是在3.7.0版本引入的特性：
2010-07-21 (3.7.0)
- Added support for write-ahead logging.
sqlite的箴言
在每个sqlite代码文件中，开头都有这么一段注释：
** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give.
破解神秘感的项目
前面提到过要破解神秘感，列举几个计算机相关课程的实验大作业或项目。
操作系统
- 哈佛大学的Xv6：Xv6, a simple Unix-like teaching operating system， 对应的课程：6.S081 / Fall 2021。
- 清华的uCore：kiukotsu/ucore: 清华大学操作系统课程实验 (OS Kernel Labs)，实验指导书：Introduction · ucore_os_docs
数据库
- CMU的15445：CMU 15-445/645 :: Intro to Database Systems (Fall 2021)，随课程要完成一个大作业项目，之前没有做过，否则应该不至于不了解生产级实现的原理。
分布式系统
- MIT的6.824：6.824 Schedule: Spring 2022，也是有随课程要完成的大作业，以前使用C++实现Paxos，后面改成了Go实现Raft。
Linux早期内核实现解析
许多年以前，赵炯博士在网上公开过一份文档，基本上逐行讲解了Linux0.11版本内核的实现，那时候的官网oldlinux.org 现在好像已经不能访问，在官网的页面Early Linux Kernel Analisys and Comments也提供了这份文档电子版的下载链接：http://www.oldlinux.org/download/clk011c-1.9.5.pdf，也有对应的公开发行物：Linux内核完全剖析 (豆瓣)。