47

我有一个项目，我必须在从兆字节到兆字节的数据上实现快速搜索、插入和删除操作。我最近一直在研究数据结构并分析它们。具体来说，我想介绍3个案例并提出问题：

  1. 数据远远超过内存一次可以处理的数据（样本范围为 10-15 TB）。在这种情况下，我会将数据结构存储在磁盘上。

  2. 与系统的内存相比，数据相对较少，因此可以在内存中存储和操作以提高速度。

  3. 数据超过可用内存，并假设它小于页面文件中可能的连续数据块的大小。因此，我将数据结构存储在磁盘上的文件中，并对文件进行内存映射。

我得出的结论是：

对于案例 1，我应该使用 B-Tree 来加快访问速度，因为它可以节省磁盘旋转产生的延迟

对于案例 2，我应该使用红黑树来更快地访问，因为数据在内存中，而不是。如果我使用 B 树，在更糟糕的情况下需要扫描的元素会少于我必须做的一个

对于案例3，我对此表示怀疑，磁盘上的页面文件使用本机OS I/O对文件进行操作，那么B树应该是更好的选择还是红黑树？

我想知道以上三个结论哪里对，哪里不对，以及如何在三个不同的情况下提高性能。

我正在使用 C++ 语言，带有一棵红黑树和一棵 B 树，它们都是我从头开始设计的。我正在使用 Boost 库进行文件映射。

更新 1::在 stackoverflow 中阅读这篇文章。得到了一些真正好的见解，这让我觉得我在案例中所做的比较类型可能是错误的。在投票最多的答案http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html中发布了一个链接

4

3 回答 3

25

红/黑树或多或少等同于 2-3-4 树，它只是 B 树的一种。如果您对 B 树节点值进行二分搜索，最坏情况下的性能是相同的。

B 树的明显缺点是浪费空间，但是根据使用的语言/内存分配器，您可能会发现 2-3-4 树平均比红黑树使用更少的空间。例如，在 32 位 Java 中，每个对象大约有 8 字节的开销。（这也很大程度上取决于分配器；IIRC phkmalloc 将小分配四舍五入到 2 的幂大小。）

为了回答您的案例，

  1. 磁盘延迟大致平均分配在寻道时间和等待磁盘旋转之间。
  2. 如果你做得对，B-tree 应该能够胜过红黑树（特别是，如果节点适合缓存线，B-tree 应该更快。）
  3. 它不需要在页面文件中是连续的；它只需要在进程的虚拟地址空间中是连续的。对于健全的操作系统，它也与案例 1 几乎相同，除非您的数据足够小以至于它大部分适合内存并且 memcpy 开销很大。

为简单起见，我将使用 B 树并在各种节点大小上运行一些基准测试。

于 2011-06-19T15:40:11.257 回答
0

Robert Sedgewick 的实验数据（在线免费提供）表明，红色容量不断向上移动到黑色树上，并换出到黑色树顶，其二次成本与其他树算法相同。

红黑树算法受到全局红色瀑布（红色喷泉）的影响。

B 树和红黑树具有相同的基本二次交换成本，这与非常简单的静态列表排序完全相同。

为了可视化不可见的隐藏熵流，您必须将所有内容解释为广义的红-绿-黑树。6-B-tree（或更大）中的每个分支都以这种方式分解。

所有额外的容量必须被解释为绿色。中心节点必须是黑色的，最外面的节点必须是红色的。

中央黑色节点是不变支撑（主干），除非明确需要，否则不得触摸它。最外面的红色节点必须是空的，因为它们是主要的换出通道。

红色卡诺通道必须始终大于绿色通道；超过 1/2 的绿色通道使任何交换变得不可能。

因为这是一个抽象的熵流，你必须忽略单个排列，只提取容量流；能量透明地流过随机粒子。

因为绿色容量向下凝聚到根部，红色容量不断被绿色边界推到树顶，这就是全球红色瀑布。

B-tree 换出通道是颠倒的。您必须从顶部到根递归地合并拆分 2 个垂直黑色行，以生成基本的卡诺换出流程。对黑色节点运动的强限制增加了额外的冗余红色运动成本。如果你试图优化一个子系统，熵成本自然会流向另一个子系统。

二叉树的二次交换成本与换出抽象高度（体积）增长的成本相同，这是一个简单的重力。二叉树的形状与对数牛顿重力可视化完全相同。

如果您有一个非常大的静态列表，则交换成本为 0。这样的列表总是与样本空间一样大。大列表的压缩总是有香农-霍夫曼熵成本。这是一个非常简单的隐藏卡诺 I/O 成本。

如果你把所有的桶放在一起，你会得到一个非常简单的静态列表，这就是众所周知的杨图。这个静态列表太小了，所以它总是有一个不变的交换成本。任何树都是一个非常简单的二维静态列表。压缩二维杨图的高度的成本始终是不变的。

树算法的主要成本不是算法成本（绿色成本）；它们的主要成本是额外隐藏的 Carnot Swapout I/O，这需要使用大列表压缩 - 解压（红色成本）进行本地全排序。

于 2021-10-13T12:35:44.937 回答
-3

要了解这些之间的区别，请阅读以下 2 点：

1）“红黑树”是“自平衡”“二叉搜索树”，每个节点都标有颜色（红色或黑色），并在其上定义了额外的操作以保持“平衡”

2）所有“红黑树”都是“二叉搜索树”，但所有“二叉搜索树”都不是“红黑树”

于 2016-03-09T18:28:20.967 回答