书本链接：03. B-Tree & Crash Recovery | Build Your Own Database FromScratch in Go
如何实现一棵内存中的B+树？
实现B+树，可以从B+树的特性出发，B+树是一种多路平衡查找树。“平衡”意味着树的高度将严格限制在O(log N)，因此B+树的实现上所有叶子节点的高度都相同，与B树不同的是，在B+树种只有叶子节点包含值，非叶子节点使用键来指示子树键值范围。“多路”意味着B+树中一个节点会存储多个子节点，这一点我们可以从已排序数组来逐步理解，一个已排序数组使用二分查找的查询成本为O(log N)，更新成本为O(N)，为了降低更新成本，我们可以拆分为两级嵌套数组，把数组拆分为m个互不重叠的小数组，更新单个子数组平均时间复杂度就降为了O(N/m)，再用一层父数组来指向子数组，外层数组更新复杂度为O(m)，查询复杂度基本不变，此时不难得出在两层嵌套数组下m的最优取值为。
但对于数据库而言，O()的更新复杂度依旧无法接受，于是要进一步改进为多层嵌套数组，拆分出更多的层级，假设我们不断分割后得到常量s使得数组大小都不超过s，查询时间复杂度依旧不会改变，总更新复杂度为O(log N)，其中包含O(log N) 的查找路径 + O(s)的节点内操作。由于 s 是常量，整体仍为O(log N)。
基本的实现思想了解之后是进一步去维护B+树，维护的核心在于三个不变式：
1.所有叶子节点高度相同。
2.节点大小受限于一个常量。
3.节点不为空。
我们从B+树的分裂与合并出发来思考维护。第二点很直观，只需要在插入元素时候检测是否超出这个常量限制，超过则将一个节点拆分为几个更小的节点，但是要注意节点分裂之后父节点的指向会同样改变，会获得新的分支，也有可能导致父节点分裂，如果分裂一直传递到了根节点，则会建立新根，使得树的高度+1，也正是因为这种自下而上的生长方式，使得B+树只有当分裂进行到根时，才会创建新根，这个新根两边子树长度完全一致，所以也能确保所有叶子节点高度相等。合并可以理解为则是分裂的逆操作，当更新后发现一个节点为空或者空间浪费较大时可以和同级节点合并，合并同样可能传播到根下的子节点合并为1个节点，因此树的高度是有可能降低的。
磁盘上的B+树还有哪些额外考虑？
基于以上的思想和方法已经足以实现一棵内存中的B+树了，但磁盘上的B+树还有一些额外需要考量的因素，我们之前已经了解了3种防崩溃安全磁盘更新方式：重命名文件、日志与LSM树。关键思想在于：更新过程中不要破坏旧数据，同样可以用这样的思想来实现B+树的安全更新，具体来说，插入或删除节点时先递归到叶子节点中完成更新，更新在副本节点上执行，而不去修改原来真正的叶子节点，复制会顺着递归回溯往上传播，形成新的根，再瞬间更换指向根的指针从旧根指向新根，长度为log N的一条新节点路径就被完美替换了，这正是写时复制的思想，保留旧版本数据同时带来一个好处，便是快照隔离。事务从某个版本开始不会受其他版本影响，关于崩溃安全的问题也收缩到了指向根节点的指针更新的原子性，但现在也还存在两个问题：
1.如何找到每一次更新后都会出现的新根？
2.如何重新收回利用旧的节点？
这一部分的内容会在后几章得到解决，其实我们可以初步考虑，新根的出现会频繁创建新的数据页，而我们又希望简单高效的获取到根，所以需要一个固定的偏移量来记录根的页号用于访问，比如偏移量为0；回收旧的节点需要一种数据结构记录回收页，当需要新页时直接返回回收页号来写新数据，这种数据结构也建立在数据页上，所以希望实现一种能够实现自我回收的数据结构也就是后文的FreeList。
除了写时复制外，是否还有什么替代方案能够完成安全的数据更新？
有，虽然写时复制有一定的抗崩溃能力，但是每次更新都需要复制一条从根到叶的完整路径，而大多数更新操作都不涉及页分裂和合并，只需要修改一个叶子节点，与写时复制相对的思想是原地更新，也就是直接对原叶子节点进行更新操作，可以引入双重写入使得崩溃后具有恢复能力，核心在于先将更新后的节点保存到某个位置并刷盘保存，这类似于写时复制同样写到新的页上，但下一步不会修改或保存父节点，而是再直接对原来的叶子节点进行更新与刷盘保存，这时如果发生了崩溃，可能导致数据只写入一半，但我们在之前已经在另一个位置写入了完整的节点，所以可以直接应用之前的副本覆盖原叶子节点的内容，这样无论之前状态如何，节点都会被原地更新为最新状态，可如果之前的副本就没有写完整或者损坏怎么办？这里的处理方式与日志相同，使用校验和，如果校验到数据写入错误，则直接丢弃与忽略他，因为此时还没有发生原地更新，真实的叶子节点数据依旧处于完整状态，如果校验通过，那么他就是最新的状态，可以用于直接覆盖叶子节点。有的数据库会将双写操作记录在日志，称作物理日志，此外还有逻辑日志，逻辑日志记录插入键值等逻辑操作，这类日志只能在数据库正常时执行，因为崩溃后的页不完整，数据状态不一致甚至可能无法正常读取，只有物理日志可以直接盲目应用，覆盖原页，才能在崩溃时恢复。
对比写时复制与双重写入，他们基于不同的理念：双重写入可以确保有足够的信息来生成完整的新版本，而写时复制确保有足够的信息来保留旧版本，如果我们在双写过程中，不去备份更新后的节点而是备份旧节点就又会得到第三种崩溃恢复的方案，这三种思想可以合并为一种：在任何时刻，都有足够的信息来恢复旧/新状态。
