标签: b-tree

分页二叉树与 AVL 树和/或 B 树有何不同？

我从 (Lafore) 学习的教科书首先介绍了红黑树，并且不包含任何伪代码，尽管所介绍的相关算法似乎相当复杂，有许多独特的情况。

接下来，他展示了 2-3-4 棵树，在我看来，这些树更容易理解，我猜想实现。他包含了一些非常清晰的实际 Java 代码。他似乎暗示 2-3-4 更容易实施，根据我目前所见，我同意。

然而，维基百科的说法相反......我认为这可能是不正确的：

http://en.wikipedia.org/wiki/2-3-4_tree

2-3-4 树是红黑树的等距，这意味着它们是等效的数据结构。换句话说，对于每棵 2-3-4 树，至少存在一棵数据元素顺序相同的红黑树。而且，2-3-4树上引起节点扩展、分裂和合并的插入和删除操作等价于红黑树中的颜色翻转和旋转。红黑树的介绍通常先介绍2-3-4树，因为它们在概念上更简单。然而，2-3-4 树可能难以在大多数编程语言中实现，因为树上的操作涉及大量特殊情况。红黑树更易于实现，因此倾向于使用。

具体来说，关于“大量特殊情况”的部分对我来说似乎很落后（我认为是具有大量特殊情况的RB，而不是2-3-4）。但是，我仍在学习（老实说，我还没有完全了解红黑树），所以我很想听听其他意见。

作为旁注......虽然我同意 Lafore 所说的大部分内容，但我认为与维基百科所说的常见内容（RB 之前的 2-3-4）相比，他以相反的顺序呈现它们很有趣。我确实认为首先使用 2-3-4 会更有意义，因为 RB 很难概念化。也许他选择这个顺序是因为 RB 与他在上一章中刚刚完成的 BST 更密切相关。

我最接近最终理解磁盘 btree 架构的是这个.

它很简单，很容易阅读和理解。但是我还是觉得很迷茫。似乎根本没有内存数据结构。我错过了什么吗？是什么让这成为一个 btree？是否只是“指向”其子节点键的 long 数组？这样有效率吗？大多数数据库和文件系统就是这样设计的吗？

是否有在内存中的磁盘 btree（或其他数据结构）上实现的方法？每个节点在哪里包含文件偏移量之类的？

在B +树的常见实现中，我们可以假定键具有固定的长度（例如25个字节）。然后，我们可以定义每个节点必须具有最小数量的键，并且必须具有最大数量。

如果我希望树接受可变长度的键，我应该修改什么？如果我说节点必须至少有2个密钥，但是我要插入的密钥太大而无法容纳该节点的块，该怎么办？

我想要像轮胎一样的轮胎地图:

Map<String,Object> map = new TireMap();
map.put("com","1");
map.put("com.aa","2");
map.put("com.aa.bb","3");

map.get("com");// return ["1","2","3"]
map.get("com.a"); //return ["2","3"]
map.get("com.aa"); //return ["2","3"]
// the key maybe full key or just key prefix

如何实现这样的地图？或者是否已经在Java API或开源中退出了地图？

它非常像innodb在mysql中.

PS: Performance非常重要.存储物品将超过1000W.

我正在学习postgresql内部和我想知道或postgresql B树索引实际上是经典的B树或B +树？要拼写出来,这意味着节点只包含键或键值对？

据说 B 树在无法放入主内存的大量数据的情况下特别有用。

我的问题是我们如何决定 B 树的顺序或在节点中存储多少键？或者一个节点应该有多少个孩子？

我发现到处都有人在每个节点使用 4/5 个密钥。它如何解决海量数据和磁盘读取问题？

与 Fractal Index（由 Tokutek 提供）相关的 3 种 IO 优化写优化数据结构（不包括 LSM）：

1) 任何类型的缓冲存储库树。具有相同想法的相关出版物：

• http://www.cc.gatech.edu/~bader/COURSES/GATECH/CSE-Algs-Fall2013/papers/Arg03.pdf
• http://cs.slu.edu/~goldwasser/publications/SODA2000.pdf

2）COLA（缓存无视前瞻（前向指针）数组）。

• http://supertech.csail.mit.edu/papers/sbtree.pdf

3）穿梭树：

• http://supertech.csail.mit.edu/papers/sbtree.pdf

什么数据结构实际上被称为“分形树索引”？

COLA 如何在实际软件中准确使用？COLA 是用作缓冲树的小缓冲区还是在实际应用中处理 TB 级数据，类似于 LSM？为什么有人更喜欢使用 COLA 而不是缓冲树？它与 TB 级的 LSM 有何不同？

说到 Lars Arge 的缓冲树：据我所知，“缓冲区”可能存储在外部存储器中，而“缓冲区”可能具有整个 RAM 的大小：唯一的要求是在推送一级之前适合内存进行排序下？

为什么有人更愿意使用如此大的外部存储器“缓冲区”而不是在每个内部节点上使用大小为 B 的较小缓冲区？

我需要快速找出两个给定集合中存在多少个整数。这些集合只被写入一次，但这个操作将使用不同的集合对执行多次。这些集合包含 5-30 个整数，这些整数中最大的一个是 840000。

我最初尝试迭代一个Vec元素，并为每个元素检查它是否存在于另一个Vec. 然后我决定BTreeSet改用它，因为它在检查集合中是否存在整数时应该明显更快，但情况似乎并非如此。Vec在稳定的 Rust 1.34 下，在稳定的 Rust 1.34 下以发布模式调用数千个集合时，该实现需要 ~72ms 和 BTreeSet ~96ms，并且在夜间使用时具有相同的性能。

这是Vec实现：

use std::cmp;

fn main() {
    let mut sets = Vec::with_capacity(1000);
    for i in 1..1000 {
        let mut set = Vec::new();
        for j in 1..i % 30 {
            set.push(i * j % 50000);
        }
        sets.push(set);
    }
    for left_set in sets.iter() {
        for right_set in sets.iter() {
            calculate_waste(left_set, right_set);
        }
    }
}

fn calculate_waste(left_nums: &Vec<usize>, …

Rust 的有序集是一个BTreeSet：

use std::collections::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

Run Code Online (Sandbox Code Playgroud)

有序映射是一个BTreeMap.

由于 set 和 map 是有序的，因此应该有一种方法可以获取包含的最大和最小元素。你怎么得到它们？