B树和B+树

一、B树和B+树区别

B树和B+树都是一种平衡树，用于在磁盘或其他直接存取辅助设备上组织和存储数据，但是它们之间存在一些区别。

其中，B树每个节点既可以存放数据，也可以存放指针；而B+树只有叶子节点存储数据，所有的非叶子节点只用于索引，它的叶子节点向左和右都直接连接构成一个链表，便于范围查询和遍历所有数据。因此，B树的高度一般比B+树低，但是B+树的查询性能更稳定。

下面，分别从B树和B+树的基本结构和使用场景进行详细介绍。

二、数据库B树和B+树

在数据库系统中，使用B树和B+树是非常常见的。数据库B树和B+树的特点在于，它们都支持快速的查找、插入和删除操作，因此在数据库的索引创建中，常常采用B树和B+树来实现。

在数据库系统中，B树和B+树的叶子节点存储的是对应数据及其地址，因此在进行范围查找的时候，B+树的效率要高于B树。但是，对比B+树，B树的查询效率在某些特定情况下更高，例如随机访问的时候。

三、B树和B+树有什么区别

从树的本质来看，B树和B+树的区别在于非叶子节点的数据存储方式。B树非叶子节点既可以存储数据，也可以存储指针，但是B+树只有叶子节点存储数据，非叶子节点只存储指针。因此，B树和B+树各有其特点，对于不同的场景，我们可以根据其特点进行选择。

四、3阶B树10个叶子节点

typedef struct BTreeNode {
    int n; //关键字数量
    int key[M]; //关键字
    struct BTreeNode *child[M+1]; //指针
    bool leaf; //是否为叶子节点
}BTreeNode;

BTreeNode *newNode(bool leaf) {
    BTreeNode *node = new BTreeNode;
    node->leaf = leaf;
    node->n = 0;
    for(int i=0;ichild[i] = NULL;
    }
    return node;
}

BTreeNode *insertNonFull(BTreeNode *node, int k) {
    int i = node->n-1;
    if(node->leaf) {
        while(i>=0 && node->key[i]>k) {
            node->key[i+1] = node->key[i];
            i--;
        }
        node->key[i+1] = k;
        node->n++;
    }
    else {
        while(i>=0 && node->key[i]>k) i--;
        if(node->child[i+1]->n == M) {
            splitChild(node, i+1, node->child[i+1]);
            if(node->key[i+1] child[i+1], k);
    }
    return node;
}

BTreeNode *insert(BTreeNode *root, int k) {
    if(root == NULL) {
        return newNode(true); //创建根节点
    } 
    if(root->n == M) {
        BTreeNode *s = newNode(false);
        s->child[0] = root;
        splitChild(s, 0, root);
        insertNonFull(s, k);
        return s;
    } 
    insertNonFull(root, k);
    return root;
}

五、B树和B+树的优缺点

1. B树优点

（1）B树支持随机查找：由于B树的每个节点中都包含数据，因此我们可以通过节点来进行二分查找从而找到目标数据；

（2）B树高度较低：由于每个节点中包含的数据量较多，因此B树的高度相对较低，查询效率也较高。

2. B树缺点

（1）节点内部数据的移动较多；

（2）树的结构比较复杂，实现起来比较困难。

3. B+树优点:

（1）减少了非叶子节点的数据；

（2）叶子节点的数据和节点之间的指针构成了链表结构，便于范围查找和遍历。

4. B+树缺点:

（1）由于节点中不包含数据，因此在进行随机查找的时候，需要先遍历到叶子节点然后再进行二分查找，增加了查询成本；

（2）树的高度相对较高，但是不同于B树，B+树的查询性能比较稳定。

六、B树和B+树都能有效支持

B树和B+树是一种非常优秀的数据结构，在现代计算机系统中应用广泛。它们不仅能够有效地支持范围还是随机查找，而且可以灵活地处理海量数据，能够在快速处理大量数据方面起到至关重要的作用。

七、B树和B+树有什么区别面试

当面试官问到B树和B+树的区别时，主要需要注重以下几个方面：

1. 非叶子节点存储方式：B树和B+树的非叶子节点存储方式不同，B树中的非叶子节点可以存储数据，而B+树中的非叶子节点只存在指针。

2. 叶子节点存储数据：B树中的叶子节点和非叶子节点的存储方式相同，两者皆可存放数据，而B+树中的叶子节点只存放数据，非叶子节点不存放数据。

3. 查询效率：从查询效率来说，B+树中只有叶子节点存放具体数据，这样我们在进行范围查找的时候，只需遍历所有的叶子节点即可，因此，B+树的查询效率相对较高。而B树节点中存储数据，因此，我们进行范围查找时需要对每个非叶子节点进行两次查找，增加了查询时间。

总体来说，B+树的查询效率更加优秀，尤其在范围查找时，但是在一些特定的场景下，B树的查询效率或许更高，需要根据实际情况进行选择。