代码之家 › 专栏 › 技术社区 › Matthieu M.

桶的索引计数

b-tree data-structures algorithm

4

Matthieu M. · 技术社区 · 14 年前

₀ _n ₀ _n <H项目。我可以决定L和H的极限。我甚至可以动态地更新它们,尽管我认为这不会有多大帮助。

桶的顺序很重要。我不能去交换。

现在,我想索引这些桶以便:

看起来很简单对吧?看到这些标准,我立刻想到了一棵芬威克树。这就是他们真正的目的。

然而,当您考虑用例时,会有一些其他用例出现:

我还没有想出如何有效地编辑芬威克树:删除/添加一个节点而不重建整个树。。。

所以问题是:

你知道一个更好的索引结构或者如何更新一个Fenwick树吗?

背景

我试图想出一个结构有点类似于B-树和排名跳过列表,但与本地化索引。这两种结构的问题是索引是沿着数据保存的,这在缓存方面效率很低(即需要从内存中提取多个页)。数据库实现表明,将索引与实际数据隔离开来更便于缓存,因此效率更高。

2 回复 | 直到 14 年前

1

3

Aryabhatta Aryabhatta 14 年前

我把你的问题理解为:

每个bucket都有一个内部顺序,bucket本身也有一个顺序,所以所有的元素都有一些顺序,您需要该顺序中的第i个元素。

您可以做的是维护一个“累积值”树,其中叶节点(x1,x2,…,xn)是bucket的大小。节点的值是其直接子节点的值之和。保持n的幂为2将使它变得简单(你可以在最后用零大小的桶填充它),树将是一个完整的树。

例如,假设桶的尺寸是2,1,4,8。

这棵树看起来像

如果需要总计数,请读取根节点的值。

例如,如果您将4个项目添加到第二个bucket中,它将是(标有*的节点是更改的节点)

     19*
    /   \
   7*    12
  / \   / \
 2  5*  4  8

如果你想找到第i个元素,你可以沿着上面的树走,有效地进行二进制搜索。你已经有了左子和右子计数。如果i>当前节点的左子节点值,减去左子节点值并在右树中递归。如果i<=左子节点值,则向左移动并再次递归。

因为根的左子级是7<9 你从9中减去7(得到2),然后右转。

自2<4(12岁的左孩子),你向左走。

您位于与第三个bucket对应的叶节点。现在您需要在该桶中选择第二个元素。

得到的总计数是O(1)。更新单个bucket/查找项目are O(logn)。

增加新桶按O(1)摊销。

代替二叉树,你也可以用B树做同样的事情。

2

0

Matthieu M. 14 年前

@Moron 建议。

芬威克树

我们只剩下两种数据结构:二叉索引树(讽刺的是,芬威克用这个名字来描述他的结构)和排序跳过列表。

我倾向于跳过列表而不是二叉树,因为它们是自组织的,所以我省去了不断重新平衡我的树的麻烦。

这些结构将允许到达第i个元素 O(log N) ,我不知道是否有可能获得更快的渐近性能。

另一个有趣的实现细节是 我有一个指向此元素的指针,但其他元素可能已被插入/删除,我现在如何知道我的元素的排名?

如果bucket指向拥有它的节点,这是可能的。但这意味着要么节点不应该移动,要么它应该在移动时更新bucket的指针。