标签: b-tree

请回答 b 树而不是 b+ 树。我有 2 个问题。

1. 当你向 ab 树插入重复的键时会发生什么？对于以下输入，t=3 的 b 树会是什么样子？1,1,1,1,1,1,1,1,1,1,1,1,1,1

2. ab树中t=3的父节点可以是这样的吗？1,1,4,10？如果是这样，键“1”和第二个键“1”之间的儿子是否只包含值“1”？

这本在线书籍介绍了 MySQL 如何利用B 树来索引数据。时间复杂度取决于每个节点的条目数。

MySQL 在一个节点中保存多少个条目？

我正在阅读有关 B 树的内容，很有趣的是，它是专门为存储在辅助内存中而构建的。但我对以下几点感到有点困惑：

1. 如果我们将 B-Tree 保存在辅助内存中（通过 Java 中的序列化），B-Tree 的优势是否会丢失？因为一旦节点被序列化，我们将无法访问对子节点的引用（正如我们在主内存中获得的那样）。所以这意味着，我们必须一一读取所有节点（因为子节点没有可用的引用）。如果我们必须读取所有节点，那么树的优点是什么？我的意思是，在这种情况下，我们不会在树上使用二分搜索。有什么想法吗 ？

PostgreSQL使用MVCC技术进行数据库并发控制，为每次写入创建一个项目的新版本，然后通过可见性规则访问该版本。问题是btree索引如何实现多版本控制？当添加新的btree节点和树时被分裂后，原有的btree结构会发生改变。这时候PGSQL是怎么处理的？有人能告诉我吗？

搜索数据库 B-Tree 索引可以在 O(log n) 时间内执行。

对于B-Tree索引，日志的基是什么？

我知道在 Big-O 表示法中，基数并不重要。不管怎样，我很好奇 B 树索引的基础是什么。

例如，对排序列表进行二分查找以 2 为底，时间复杂度为 O(log n)。这是因为我们可以在每次比较时丢弃一半的列表。

同样，出于同样的原因，平衡二叉树上的二分搜索以 2 为底。

删除了旧问题并写了一个更好的问题。所以我不知道我该怎么做，所以我认为我应该使用链表，但似乎会有限制。我注意到一些与树相关的包，例如这些.

这似乎也不符合我想要做的事情，然后我开始考虑使用诸如IsThere2Nodes或 likeIsParentOf(x)等方法为节点创建一个类。我有点含糊，但我只是想知道我是否我在正确的方向上接近这个。

这是B+树的一个节点。我想使用智能指针，因为我的程序泄漏了大量内存。如何使用智能指针转换代码？

class node
{

public:

    long* key;
    int capacity;
    node** nodes;
    node* parent;
    long* value;

    node ( int order ) {
        key = new long[order + 1];
        value = new long[order + 1];
        nodes = new node *[order + 2];
        capacity = 0;
        parent = NULL;
        for ( int i = 0; i <= order + 1; i++ ) {
            this->nodes[i] = NULL;
        }
    }
    ~node() {
        delete[] key;
        delete[] value;
        for ( int i = 0; i <= order …

我知道这是一个常见的问题,我在Stack Overflow中看到了一些线程,但仍然无法得到它.

这是Stack溢出的公认答案:

"磁盘搜索是昂贵的.B-Tree结构专门设计用于尽可能避免磁盘搜索.因此,B-Tree将更多的键/指针打包到单个节点而不是二叉树.这个属性使得树非常平坦.通常大多数B-Tree只有3或4级深度,并且根节点可以很容易地被缓存.这只需要2-3次寻找在树中找到任何东西.叶子也是这样"填充",所以迭代一棵树(例如完整扫描或范围扫描)是非常有效的,因为您每个块(搜索)读取数百/数千个数据行.

在具有相同容量的二叉树中,您将拥有几十个级别,并且顺序访问每个值将需要至少一次搜索."

据我所知,B-Tree有比BST更多的节点(Order).所以它绝对比BST更平坦,更浅.

但是这些节点又被存储为链表吗？

我不明白他们什么时候说键被读作块,从而最小化I/O的数量.

是不是同样的论点也对BST有利？除了链接将向下？

请有人向我解释一下？

我对于要插入顺序为 1 和顺序为 2 的 B+ 树中的键的最大和最小数量感到困惑。

在我看的视频中，据说一个节点（根除外）中插入的键的最大数量至少为m，最多为2m（假设m为阶数）。

根据这 2 个陈述，在 B+ 树中插入的键的最小和最大数量是多少，阶数为 1 和阶数为 2？我不确定以上两种说法是否冲突，或者我误解了什么。任何想法？

我有以下功能，我不确定他们是在实现二叉树还是 B 树。

这是代码：

def foo(x):
    if x:
        a, b, c = x
        return foo(a) + b + foo(c)
    else:
        return 0

谁能帮我弄清楚正在使用哪些数据结构？

我想在Java中创建一个B + -Tree的简单实现,我需要一些帮助.我希望我的程序实现这些功能:搜索,插入,删除.

我的问题:

1. 用于表示树的最佳数据结构是什么？我在想TreeMap.
2. 在B + -Tree中,数据被存储在叶节点(K,V)和内部节点中而不是每个记录中的数据中存在指向子节点(K,P)的指针.我想建议如何指向另一个节点因为我不能在java中使用指针.

此外,如果您有任何建议,或者您想要一个简单的实现,我可以作为参考,请告诉我.

谢谢