数据库 – 缓存忽视的前瞻数组

发布时间：2020-12-12 08:40:09 所属栏目：MsSql教程来源：网络整理

导读：我正在尝试了解在 here描述的simipiled缓存隐藏的前瞻阵??列,从 this presentation的第35页 Analysis of Insertion into Simplified Fractal Tree: Cost to merge 2 arrays of size X is O(X=B) block I/Os. Merge is very I/O efficient. Cost per element t

我正在尝试了解在 here描述的simipiled缓存隐藏的前瞻阵??列,从 this presentation的第35页

Analysis of Insertion into Simplified
Fractal Tree:

Cost to merge 2 arrays of size X is O(X=B) block I/Os. Merge is very
I/O efficient.

Cost per element to merge is O(1/B) since O(X) elements were
merged.

Max # of times each element is merged is O(logN).

Average insert cost is O(logN/B)

我可以手写#1,#2和#3,但我不明白#4,从论文中,合并可以被认为是二进制加载,例如(31)B可以呈现：
22222
当插入新项目(加1)时,应该有5 = log(32)merge(5进位).但是,在这种情况下,我们必须合并32个元素！另外,如果每次加1,那么从0到2 ^ k将执行多少个系统？流氓应该是2 ^ k – 1.换句话说,一个插入合并！

那么#4如何计算？

解决方法

虽然你是正确的,在最坏的情况下,合并元素的数量(和转移)是N,并且总合并的数量也是相同的顺序,平均插入成本仍然是对数.它来自两个事实：合并成本不同,低成本合并的数量远高于高成本合并的数量.

这可能比较容易看出.
我们设置B = 1(即每个块1个元素,每个合并的最坏情况是一个成本)和N = 32(例如,我们将32个元素插入最初的空数组).
一半的插入(16)将元素放入大小为1的空子阵列中,因此不会导致合并.剩下的插入中,一个(最后一个)需要合并(移动)32个元素,一个(第16个)移动16个,第2个(第8个和第24个)移动8个元素,4个移动4个元素,以及8个移动2个元素.因此,元素移动的总数为96,给每个插入平均3次移动.

希望有帮助.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!