如何最大化每个 btree 节点的元素数量
How to maximize the number of elements per btree node
我正在从一些数据构建一个 btree。一旦我构建了 btree（即插入所有元素），我就不再插入或删除元素。但是，从某种意义上说，生成的 btree 并不是最优的，如果我可以非常频繁地让每个节点具有 n 个最大元素，我的节点包含的元素少于 n 个（问题变得更糟 n 是）。这是我的 btree 中的一个部分，其中包含数百个元素，n 等于 5。该部分包含根节点和几个最底部的节点
如您所见，很多节点的元素少于 5 个。我的问题是：
有没有办法在构建后 "compact" btree，以便所有（除了一些最底部的节点）都包含恰好 n 元素。将作为键存储在节点中的内容将是 32 位值，但我不能保证它们将以任何特定顺序插入。
如果由于 keys/records 未按密钥顺序交付而导致获取打包 btree 的经典方法不可行，那么基本上有两个选择：
- 离线：从头开始构建新的打包 btree
- 在线：使用与节点拆分相反的过程就地压缩 btree
构建新的 btree 更简单、更快速，而且可以就地完成 'almost'。唯一的额外 space 要求包括每个 btree 级别的一个页面（或页面缓冲区），以容纳正在构建的新 btree 的右脊柱。旧树的页面一清空就可以为新树回收。
此方案通常称为 'pyramid' 方案或 'packing from the bottom up'。不用说，它要求 btree 在打包期间完全脱机，或者根据查询的键将查询分派到正确的树（旧的或新的）的函数。
在线压缩采用基本相同的逻辑，只是细节有点不同，因为键（记录）是从右邻居而不是输入中提取的。树必须逐层压实，从底部向上，从最左边的叶子开始：
- 从父节点下拉分隔键
- 从右邻节点获取密钥直到该节点已满
- 将右邻居的新的最左边的键作为分隔符向上推
- 将正确的邻居设为当前节点，冲洗并重复
这两种方案 - 打包构建和在线压实 - 都可能使树右侧脊柱上的节点填充不足甚至为空。如果这是不可取的，那么可以通过在关卡的最后两个节点之间重新分配密钥来解决这个问题。这可以通过调用与正常 btree 操作相同的 borrowing/balancing 过程来完成。就像打包和压缩一样，这种脊柱重新平衡必须自下而上完成。 IE。从最右边的叶子向上到根。
我正在从一些数据构建一个 btree。一旦我构建了 btree（即插入所有元素），我就不再插入或删除元素。但是，从某种意义上说，生成的 btree 并不是最优的，如果我可以非常频繁地让每个节点具有 n 个最大元素，我的节点包含的元素少于 n 个（问题变得更糟 n 是）。这是我的 btree 中的一个部分，其中包含数百个元素，n 等于 5。该部分包含根节点和几个最底部的节点
如您所见，很多节点的元素少于 5 个。我的问题是： 有没有办法在构建后 "compact" btree，以便所有（除了一些最底部的节点）都包含恰好 n 元素。将作为键存储在节点中的内容将是 32 位值，但我不能保证它们将以任何特定顺序插入。
如果由于 keys/records 未按密钥顺序交付而导致获取打包 btree 的经典方法不可行，那么基本上有两个选择：
- 离线：从头开始构建新的打包 btree
- 在线：使用与节点拆分相反的过程就地压缩 btree
构建新的 btree 更简单、更快速，而且可以就地完成 'almost'。唯一的额外 space 要求包括每个 btree 级别的一个页面（或页面缓冲区），以容纳正在构建的新 btree 的右脊柱。旧树的页面一清空就可以为新树回收。
此方案通常称为 'pyramid' 方案或 'packing from the bottom up'。不用说，它要求 btree 在打包期间完全脱机，或者根据查询的键将查询分派到正确的树（旧的或新的）的函数。
在线压缩采用基本相同的逻辑，只是细节有点不同，因为键（记录）是从右邻居而不是输入中提取的。树必须逐层压实，从底部向上，从最左边的叶子开始：
- 从父节点下拉分隔键
- 从右邻节点获取密钥直到该节点已满
- 将右邻居的新的最左边的键作为分隔符向上推
- 将正确的邻居设为当前节点，冲洗并重复
这两种方案 - 打包构建和在线压实 - 都可能使树右侧脊柱上的节点填充不足甚至为空。如果这是不可取的，那么可以通过在关卡的最后两个节点之间重新分配密钥来解决这个问题。这可以通过调用与正常 btree 操作相同的 borrowing/balancing 过程来完成。就像打包和压缩一样，这种脊柱重新平衡必须自下而上完成。 IE。从最右边的叶子向上到根。