实现一个简单Database8（译文）
前文回顾
- 实现一个简单的Database系列
译注：cstack在github维护了一个简单的、类似sqlite的数据库实现，通过这个简单的项目，可以很好的理解数据库是如何运行的。本文是第八篇，主要是对B-tree的叶子节点格式的实现
Part 8 B-Tree叶子节点格式
我们准备把表的格式从非排序的数组格式行（rows）改成B-Tree。这是一个相当大变化，需要多个篇幅才能实现。在本文结束时，我们将定义叶子节点的布局，支持插入键值对儿到单节点的B-Tree。但是首先，来回顾一下把数据结构（从数组array）切换到B-Tree的原因。
替换表格式
根据现在的格式（数组组织的行数据格式），每个page存储的只有行数据（没有元数据），所以空间使用上很有效率，非常节省空间。插入操作也很快，因为它只是追加到表的结尾而已。然而，查询一个特定的行数据只能遍历整张表的数据才能搞定。并且如果想删除一行数据的话，我们就只能移动这条数据后面的所有数据才能填补因为删除数据产生的空洞。
如果把表数据按照数组的方式存储，但是保持行按 id 排序，我们就可以使用二分查找方式来查找一个特定的 id 。然而，插入操作会变得很慢，因为我们不得不移动大量行（rows）才能腾出空间插入数据。
相反，我们采用树的结构。每个在树中的节点能够包含的行数量可变，所以我们不得不在节点中存储一些额外信息来追踪节点中包含了多少行数据。此外，所有内部节点还有存储开销，因为这些节点不存储任何行数据（只存储目录项用来做路由查找）。作为对维护一整个大文件方案的替换，（使用树的结构来组织行数据）我们可以快速执行插入、删除和查找。
| 非排序数组行数据 | 排序数组行数据 | Tree of nodes | |
|---|---|---|---|
| 页内包含 | 只有数据 | 只有数据 | 元数据, 主键, 数据 |
| 每页行数 | more | more | fewer |
| 插入 | O(1) | O(n) | O(log(n)) |
| 删除 | O(n) | O(n) | O(log(n)) |
| id查找 | O(n) | O(log(n)) | O(log(n)) |
节点头的格式（Node Header Format）
叶子节点和内部节点有不同的布局格式。这里创建一个enum类型用来追踪节点的类型（node type）：
+typedef enum { NODE_INTERNAL, NODE_LEAF } NodeType;
