小编Squ*_*mmy的帖子

所以我有一个问题,我很确定它是可以解决的,但经过许多小时的思考和讨论,只取得了部分进展.

问题如下.我正在构建一个BTree,可能是几百万个密钥.在搜索BTree时,它会根据需要从磁盘分页到内存,并且每个操作页面都相对昂贵.这实际上意味着我们需要遍历尽可能少的节点(尽管在遍历节点之后,遍历该节点的成本,直到该节点为0).因此,我们不希望通过使大量节点接近最小容量来浪费空间.从理论上讲,这应该是可以预防的(在合理范围内),因为树的结构取决于键插入的顺序.

因此,问题是如何重新排序密钥,以便在构建BTree之后使用最少数量的节点.这是一个例子:

我偶然发现了这个问题你应该以什么顺序将一组已知的密钥插入到B-Tree中以获得最小的高度？不幸的是,这个问题略有不同.答案,似乎也没有解决我的问题.还有一点值得补充的是,我们希望通过手动构建树来获得数学保证,并且只使用insert选项.我们不想手动构建树,犯错误,然后发现它是无法搜索的!

我也偶然发现了两篇研究论文,这些论文非常接近解决我的问题,但并不完全存在! B树和最佳2,3树的时间和空间最优性(我实际上从上面拍摄了图像)讨论并量化了空间最优和空间质量BTrees之间的差异,但是没有达到描述如何设计插入顺序,就我所知.

任何有关这方面的帮助都将非常感激.

谢谢

研究论文可在以下网址找到:

http://www.uqac.ca/rebaine/8INF805/Automne2007/Sujets2007Automne/p174-rosenberg.pdf

http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1143&context=hmc_fac_pub

编辑::我最终用FILLORDER算法填充了如上文所述构造的btree骨架.如前所述,我希望避免这种情况,但是在发布了2个优秀答案之前我最终实现了它!

GetFilesDir()返回null,这完全是奇怪的.更糟糕的是,我的代码是......非常简单:

public class main extends Activity {
/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);

    File f = this.getFilesDir();
    f.getAbsolutePath();

    tempClicked((ToggleButton)findViewById(R.id.tempToggle));
}

这将在f.getAbsolutePath()上崩溃.它目前在模拟器中运行,在1024x600下模拟2.3.3系统.

谷歌在这方面什么也没有回报......那么为什么地球上会发生这种情况？我该如何修复它？!

非常感谢!

编辑::已解决!

嗯,有点......

我认为这是一个模拟器错误.我将模拟器的外观更改为WXVGA,然后允许它正确地写入文件.然后,当我将分辨率更改回1024x600时,它保持正常工作.

所以,如果有人有类似的错误,我建议你使用模拟器,直到找到超越错误的方法.