书本链接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。除了写时复制外是否还有什么替代方案能够完成安全的数据更新有虽然写时复制有一定的抗崩溃能力但是每次更新都需要复制一条从根到叶的完整路径而大多数更新操作都不涉及页分裂和合并只需要修改一个叶子节点与写时复制相对的思想是原地更新也就是直接对原叶子节点进行更新操作可以引入双重写入使得崩溃后具有恢复能力核心在于先将更新后的节点保存到某个位置并刷盘保存这类似于写时复制同样写到新的页上但下一步不会修改或保存父节点而是再直接对原来的叶子节点进行更新与刷盘保存这时如果发生了崩溃可能导致数据只写入一半但我们在之前已经在另一个位置写入了完整的节点所以可以直接应用之前的副本覆盖原叶子节点的内容这样无论之前状态如何节点都会被原地更新为最新状态可如果之前的副本就没有写完整或者损坏怎么办这里的处理方式与日志相同使用校验和如果校验到数据写入错误则直接丢弃与忽略他因为此时还没有发生原地更新真实的叶子节点数据依旧处于完整状态如果校验通过那么他就是最新的状态可以用于直接覆盖叶子节点。有的数据库会将双写操作记录在日志称作物理日志此外还有逻辑日志逻辑日志记录插入键值等逻辑操作这类日志只能在数据库正常时执行因为崩溃后的页不完整数据状态不一致甚至可能无法正常读取只有物理日志可以直接盲目应用覆盖原页才能在崩溃时恢复。对比写时复制与双重写入他们基于不同的理念双重写入可以确保有足够的信息来生成完整的新版本而写时复制确保有足够的信息来保留旧版本如果我们在双写过程中不去备份更新后的节点而是备份旧节点就又会得到第三种崩溃恢复的方案这三种思想可以合并为一种在任何时刻都有足够的信息来恢复旧/新状态。
书本链接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。除了写时复制外是否还有什么替代方案能够完成安全的数据更新有虽然写时复制有一定的抗崩溃能力但是每次更新都需要复制一条从根到叶的完整路径而大多数更新操作都不涉及页分裂和合并只需要修改一个叶子节点与写时复制相对的思想是原地更新也就是直接对原叶子节点进行更新操作可以引入双重写入使得崩溃后具有恢复能力核心在于先将更新后的节点保存到某个位置并刷盘保存这类似于写时复制同样写到新的页上但下一步不会修改或保存父节点而是再直接对原来的叶子节点进行更新与刷盘保存这时如果发生了崩溃可能导致数据只写入一半但我们在之前已经在另一个位置写入了完整的节点所以可以直接应用之前的副本覆盖原叶子节点的内容这样无论之前状态如何节点都会被原地更新为最新状态可如果之前的副本就没有写完整或者损坏怎么办这里的处理方式与日志相同使用校验和如果校验到数据写入错误则直接丢弃与忽略他因为此时还没有发生原地更新真实的叶子节点数据依旧处于完整状态如果校验通过那么他就是最新的状态可以用于直接覆盖叶子节点。有的数据库会将双写操作记录在日志称作物理日志此外还有逻辑日志逻辑日志记录插入键值等逻辑操作这类日志只能在数据库正常时执行因为崩溃后的页不完整数据状态不一致甚至可能无法正常读取只有物理日志可以直接盲目应用覆盖原页才能在崩溃时恢复。对比写时复制与双重写入他们基于不同的理念双重写入可以确保有足够的信息来生成完整的新版本而写时复制确保有足够的信息来保留旧版本如果我们在双写过程中不去备份更新后的节点而是备份旧节点就又会得到第三种崩溃恢复的方案这三种思想可以合并为一种在任何时刻都有足够的信息来恢复旧/新状态。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
