database - 缓存不经意的前瞻数组

Question

我正在尝试理解 here 中描述的简化缓存不经意先行数组, 以及 this presentation 的第 35 页

Analysis of Insertion into Simplified Fractal Tree:

1. Cost to merge 2 arrays of size X is O(X=B) block I/Os. Merge is very I/O efficient.
2. Cost per element to merge is O(1/B) since O(X) elements were merged.
3. Max # of times each element is merged is O(logN).
4. Average insert cost is O(logN/B)

我能理解#1，#2和#3，但我无法理解#4，从论文中，合并可以被认为是二进制加法进位，例如， (31)B 可以表示为: 11111
当插入一个新项目(加 1)时，应该有 5 = log(32) merge(5 carries)。但是，在这种情况下，我们必须合并 32 个元素!另外，如果每次加1，那么从0到2^k会进行多少次进位？答案应该是 2^k - 1。换句话说，每次插入一个合并!

那么#4 是如何计算的？

Answer 1

虽然您在最坏情况下合并元素的数量(以及传输)是 N 并且合并的总数量也是相同的顺序这两个方面都是正确的，但平均插入成本仍然是对数的。它来自两个事实:合并成本不同，低成本合并的数量远高于高成本合并的数量。

通过示例可能更容易理解。
让我们设置 B=1(即每个 block 1 个元素，每次合并都有成本的最坏情况)和 N=32(例如，我们将 32 个元素插入到一个最初为空的数组中)。
一半的插入 (16) 将一个元素放入大小为 1 的空子数组中，因此不会导致合并。在剩余的插入中，一次(最后一次)需要合并(移动)32 个元素，一次(第 16 次)移动 16 个，两次(第 8 次和第 24 次)移动 8 个元素，四次(第 8 次和第 24 次)移动 4 个元素，八次移动 2 个元素。因此，元素移动总数为 96，平均每次插入 3 次移动。

希望对您有所帮助。