首页 > 其他分享 >数据结构之B树与B+树

数据结构之B树与B+树

时间：2024-07-30 08:55:50浏览次数：13  
标签：insert keys children int key 数据结构 节点

目录

数据结构之B树与B+树

B树

B树是一种自平衡的树数据结构，广泛应用于数据库和文件系统中。它的主要特点是能够保持数据有序，并允许高效的插入、删除和查找操作。B树的每个节点可以包含多个键和子节点，从而减少了树的高度，提高了操作效率。

B树的基本概念

  1. 节点：B树的每个节点可以包含多个键和子节点。节点分为内部节点和叶子节点。
  2. 度数：B树的度数（或称为最小度数）是一个重要参数，表示每个节点至少包含的子节点数。通常用t表示。
  3. 键的数量：每个节点包含的键的数量在t-1到2t-1之间。
  4. 子节点的数量：每个节点包含的子节点的数量在t到2t之间。

B树的性质

  1. 根节点：根节点至少有两个子节点，除非它是叶子节点。
  2. 键的排序：每个节点的键按升序排列。
  3. 子节点的数量：每个内部节点的子节点数量比其键的数量多1。
  4. 平衡性：所有叶子节点都在同一层，保证了树的平衡性。

B树的操作

  1. 查找：从根节点开始，根据键的大小逐层查找，直到找到目标键或到达叶子节点。
  2. 插入：在叶子节点插入新键，如果节点已满，则需要分裂节点并将中间键上移。
  3. 删除：删除键时需要考虑多种情况，包括从叶子节点删除、从内部节点删除以及节点合并等。

示例代码

以下是一个简单的B树实现示例，展示了B树的插入和查找操作：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  
  // B 树节点类
  class BTreeNode {
  public:
      std::vector<int> keys;
      std::vector<BTreeNode*> children;
      bool isLeaf;
  
      BTreeNode(bool leaf);
      void insertNonFull(int key);
      void splitChild(int i, BTreeNode* y);
      void traverse();
      BTreeNode* search(int key);
  
  private:
      int t; // 最小度数
      friend class BTree;
  };
  
  // B 树类
  class BTree {
  public:
      BTree(int _t) : t(_t) {
          root = new BTreeNode(true);
          root->t = t;
      }
  
      void traverse() {
          if (root != nullptr) root->traverse();
      }
  
      BTreeNode* search(int key) {
          return (root == nullptr) ? nullptr : root->search(key);
      }
  
      void insert(int key);
  
  private:
      BTreeNode* root;
      int t; // 最小度数
  };
  
  BTreeNode::BTreeNode(bool leaf) : isLeaf(leaf) {}
  
  void BTreeNode::traverse() {
      int i;
      for (i = 0; i < keys.size(); i++) {
          if (!isLeaf) children[i]->traverse();
          std::cout << " " << keys[i];
      }
      if (!isLeaf) children[i]->traverse();
  }
  
  BTreeNode* BTreeNode::search(int key) {
      int i = 0;
      while (i < keys.size() && key > keys[i]) i++;
      if (keys[i] == key) return this;
      if (isLeaf) return nullptr;
      return children[i]->search(key);
  }
  
  void BTree::insert(int key) {
      if (root->keys.size() == 2 * t - 1) {
          BTreeNode* s = new BTreeNode(false);
          s->children.push_back(root);
          s->splitChild(0, root);
          int i = 0;
          if (s->keys[0] < key) i++;
          s->children[i]->insertNonFull(key);
          root = s;
      }
      else {
          root->insertNonFull(key);
      }
  }
  
  void BTreeNode::insertNonFull(int key) {
      int i = keys.size() - 1;
      if (isLeaf) {
          keys.push_back(0);
          while (i >= 0 && keys[i] > key) {
              keys[i + 1] = keys[i];
              i--;
          }
          keys[i + 1] = key;
      }
      else {
          while (i >= 0 && keys[i] > key) i--;
          if (children[i + 1]->keys.size() == 2 * t - 1) {
              splitChild(i + 1, children[i + 1]);
              if (keys[i + 1] < key) i++;
          }
          children[i + 1]->insertNonFull(key);
      }
  }
  
  void BTreeNode::splitChild(int i, BTreeNode* y) {
      BTreeNode* z = new BTreeNode(y->isLeaf);
      z->t = y->t;
      for (int j = 0; j < t - 1; j++) z->keys.push_back(y->keys[j + t]);
      if (!y->isLeaf) {
          for (int j = 0; j < t; j++) z->children.push_back(y->children[j + t]);
      }
      if (t > 1) // 防止 t = 1 时 y->keys.resize(t - 1) 报错 (t - 1 = 0
      {
          y->keys.resize(t - 1);
      }
      y->children.resize(t);
      children.insert(children.begin() + i + 1, z);
      keys.insert(keys.begin() + i, y->keys[t - 1]);
  }
  
  int main() {
      BTree t(3); // 创建一个最小度数为 3 的 B 树
      t.insert(10);
      t.insert(20);
      t.insert(5);
      t.insert(6);
      t.insert(12);
      t.insert(30);
      t.insert(7);
      t.insert(17);
  
      std::cout << "遍历 B 树: ";
      t.traverse();
      std::cout << std::endl;
  
      int key = 6;
      (t.search(key) != nullptr) ? std::cout << key << " 存在\n" : std::cout << key << " 不存在\n";
  
      key = 15;
      (t.search(key) != nullptr) ? std::cout << key << " 存在\n" : std::cout << key << " 不存在\n";
  
      return 0;
  }

这个示例展示了如何创建一个最小度数为3的B树，并进行插入和查找操作。你可以在Visual Studio中运行这段代码，观察B树的行为。

B+树

B+树是B树的一种变体，广泛应用于数据库和文件系统中。与B树相比，B+树在查找、插入和删除操作上有一些不同的特点和优势。

B+树的基本概念

  1. 节点：B+树的每个节点可以包含多个键和子节点。节点分为内部节点和叶子节点。

  2. 度数：B+树的度数（或称为最小度数）是一个重要参数，表示每个节点至少包含的子节点数。通常用t表示。

  3. 键的数量：每个内部节点包含的键的数量在t-1到2t-1之间。

  4. 子节点的数量：每个内部节点包含的子节点的数量在t到2t之间。

  5. 叶子节点：所有的键和值都存储在叶子节点中，叶子节点通过指针相互连接，形成一个链表。

B+树的性质

  1. 根节点：根节点至少有两个子节点，除非它是叶子节点。

  2. 键的排序：每个节点的键按升序排列。

  3. 子节点的数量：每个内部节点的子节点数量比其键的数量多1。

  4. 平衡性：所有叶子节点都在同一层，保证了树的平衡性。

  5. 叶子节点链表：所有叶子节点通过指针相互连接，便于范围查询。

B+树的操作

  1. 查找：从根节点开始，根据键的大小逐层查找，直到找到目标键或到达叶子节点。

  2. 插入：在叶子节点插入新键，如果节点已满，则需要分裂节点并将中间键上移。

  3. 删除：删除键时需要考虑多种情况，包括从叶子节点删除、从内部节点删除以及节点合并等。
    示例代码
    以下是一个简单的B+树实现示例，展示了B+树的插入和查找操作：

#include <iostream>
#include <vector>
#include <algorithm>

// B+ 树节点类
class BPlusTreeNode {
public:
    std::vector<int> keys;
    std::vector<BPlusTreeNode*> children;
    BPlusTreeNode* next; // 指向下一个叶子节点
    bool isLeaf;

    BPlusTreeNode(bool leaf);
    void insertNonFull(int key);
    void splitChild(int i, BPlusTreeNode* y);
    void traverse();
    BPlusTreeNode* search(int key);

private:
    int t; // 最小度数
    friend class BPlusTree;
};

// B+ 树类
class BPlusTree {
public:
    BPlusTree(int _t) : t(_t) {
        root = new BPlusTreeNode(true);
        root->t = t;
    }

    void traverse() {
        if (root != nullptr) root->traverse();
    }

    BPlusTreeNode* search(int key) {
        return (root == nullptr) ? nullptr : root->search(key);
    }

    void insert(int key);

private:
    BPlusTreeNode* root;
    int t; // 最小度数
};

BPlusTreeNode::BPlusTreeNode(bool leaf) : isLeaf(leaf), next(nullptr) {}

void BPlusTreeNode::traverse() {
    int i;
    for (i = 0; i < keys.size(); i++) {
        if (!isLeaf) children[i]->traverse();
        std::cout << " " << keys[i];
    }
    if (!isLeaf) children[i]->traverse();
}

BPlusTreeNode* BPlusTreeNode::search(int key) {
    int i = 0;
    while (i < keys.size() && key > keys[i]) i++;
    if (keys[i] == key) return this;
    if (isLeaf) return nullptr;
    return children[i]->search(key);
}

void BPlusTree::insert(int key) {
    if (root->keys.size() == 2 * t - 1) {
        BPlusTreeNode* s = new BPlusTreeNode(false);
        s->children.push_back(root);
        s->splitChild(0, root);
        int i = 0;
        if (s->keys[0] < key) i++;
        s->children[i]->insertNonFull(key);
        root = s;
    }
    else {
        root->insertNonFull(key);
    }
}

void BPlusTreeNode::insertNonFull(int key) {
    int i = keys.size() - 1;
    if (isLeaf) {
        keys.push_back(0);
        while (i >= 0 && keys[i] > key) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = key;
    }
    else {
        while (i >= 0 && keys[i] > key) i--;
        if (children[i + 1]->keys.size() == 2 * t - 1) {
            splitChild(i + 1, children[i + 1]);
            if (keys[i + 1] < key) i++;
        }
        children[i + 1]->insertNonFull(key);
    }
}

void BPlusTreeNode::splitChild(int i, BPlusTreeNode* y) {
    BPlusTreeNode* z = new BPlusTreeNode(y->isLeaf);
    z->t = y->t;
    for (int j = 0; j < t - 1; j++) z->keys.push_back(y->keys[j + t]);
    if (!y->isLeaf) {
        for (int j = 0; j < t; j++) z->children.push_back(y->children[j + t]);
    }
    if (t > 1) // 防止 t = 1 时 y->keys.resize(t - 1) 报错 (t - 1 = 0
    {
        y->keys.resize(t - 1);
    }
    y->children.resize(t);
    children.insert(children.begin() + i + 1, z);
    keys.insert(keys.begin() + i, y->keys[t - 1]);
    if (y->isLeaf) {
        z->next = y->next;
        y->next = z;
    }
}

int main() {
    BPlusTree t(3); // 创建一个最小度数为 3 的 B+ 树
    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    t.insert(30);
    t.insert(7);
    t.insert(17);

    std::cout << "遍历 B+ 树: ";
    t.traverse();
    std::cout << std::endl;

    int key = 6;
    (t.search(key) != nullptr) ? std::cout << key << " 存在\n" : std::cout << key << " 不存在\n";

    key = 15;
    (t.search(key) != nullptr) ? std::cout << key << " 存在\n" : std::cout << key << " 不存在\n";

    return 0;
}

这个示例展示了如何创建一个最小度数为3的B+树，并进行插入和查找操作。你可以在Visual Studio中运行这段代码，观察B+树的行为。

B树和B+的差别

B树和B+树都是自平衡的树数据结构，广泛应用于数据库和文件系统中。尽管它们有许多相似之处，但也有一些关键的区别。以下是它们之间的主要差异：

  1. 叶子节点
  • B树：键和值都可以存储在内部节点和叶子节点中。
  • B+树：所有的键和值都存储在叶子节点中，内部节点只存储键。
  1. 内部节点
  • B树：内部节点包含键和值，并且可以直接用于查找操作。
  • B+树：内部节点只包含键，不包含值。查找操作最终会到达叶子节点。
  1. 叶子节点链表
  • B树：叶子节点之间没有链表结构。
  • B+树：所有叶子节点通过指针相互连接，形成一个链表，便于范围查询。
  1. 查找效率
  • B树：查找操作可能会在内部节点找到目标键。
  • B+树：查找操作总是到达叶子节点，查找路径更长，但叶子节点链表使得范围查询更高效。
  1. 空间利用率
  • B树：由于键和值都存储在内部节点和叶子节点中，空间利用率较低。
  • B+树：由于内部节点只存储键，空间利用率较高。
  1. 范围查询
  • B树：范围查询需要在树中进行多次查找。
  • B+树：由于叶子节点链表的存在，范围查询非常高效，只需在叶子节点链表中遍历即可。

标签：insert,keys,children,int,key,数据结构,节点
From： https://blog.csdn.net/ChuJian_cao/article/details/140786824

相关文章

  • 数据结构----树
    目录树1.概念:1.1关于树的一些基本概念2. 二叉树2.1概念2.2二叉树性质（重点）2.3满二叉树、完全二叉树2.4二叉树的顺序存储结构2.5二叉树的遍历（重点）2.6二叉树的链式存储树1.概念:树(Tree)是(n>=0)个节点的有限集合T，它满足两个条件：有且仅有一个特定的......
  • [数据结构] 珂朵莉树
    介绍珂朵莉树，学名珂朵莉树，又学名老司机树（$ODT$），常用来解决“区间推平”（把区间改为某一个数）等的操作，只适用于随机数据，可以定向卡掉；其实这玩意就是暴力，没啥可说的，分块都比不上她暴力；但人家毕竟是她，所以对于一些题还是有用的；实现只要你会$C++\STL$里的$set$，搞定她完......
  • 【数据结构】排序
    1.排序的概念及其运用1.1排序的概念排序：指的是将一组数据（通常是一个列表、数组或任何有限集合）按照某种特定的顺序重新排列的过程。这个特定的顺序可以是升序（从小到大）、降序（从大到小）或者根据自定义的规则进行排序。稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的......
  • 数据结构优化DP
    51nod-基因匹配+luogu-【模板】最长公共子序列本题重在转化。由于最长公共子序列的下标是一个最长上升子序列，所以我们可以考虑把数字映射成下标，有多个就要倒序把每个值映射成多个不同的值，因为一个数有多种下标都是可取的。51nod-3976-最长序列与基本问题相同，但是需要根据长度插......
  • 好玩的数据结构qwq
    从2024.7.29开始记录。代码不放可能是因为我没写。1.P7470[NOIOnline2021提高组]岛屿探险先考虑\(b_i>d_j\)的情况。那么答案就是\(\sum[a_i\oplusc_j\led_j]\)。我们把\(a_i\)插入\(01\text{trie}\)中。然后我们从上往下走，走到深度为\(h\)的节点，那么代......
  • 【数据结构】排序算法
    目录排序冒泡排序选择排序直接插入排序希尔排序堆排序归并排序快速排序排序排序的概念：假设含有n个记录的序列为{R1,R2,R3,···,Rn}，其相应的关键字分别为{K1,K2,K3,···Kn}，需确定1,2,3,···,n的一种排列P1,P2,···,Pn，使其相应的关键字满足Kp1<=Kp2<=K......
  • 山东大学数据结构与算法实验13最小生成树（Prim算法/Kruskal算法）
    A : Prim算法题目描述使用prim算法实现最小生成树输入输出格式输入第一行两个整数n,e。n(1≤n≤200000)代表图中点的个数，e(0≤m≤500000)代表边的个数。接下来e行，每行代表一条边：ijw 表示顶点i和顶点j之间有一条权重为w的边输出最小生成树所有边的......
  • 最细哈希表相关的力扣题和讲解和Java、C++常用的数据结构（哈希法）来源于代码随想录，十分
    20240725一、什么时候适用什么样的结构。1.java中1.1HashSet：1.2TreeSet：1.3LinkedHashSet：1.4HashMap：1.5TreeMap：1.6LinkedHashMap：1.7总结2.c++中2.1std::unordered_set：2.2std::set：2.3std::multiset：2.4std::unordered_map：2.5std::map：2.6std::multimap：3代码......
  • 浅谈简单的数据结构1（树状数组 、线段树）（c++）
    *_*课间休息后的知识点轰炸树状数组引入给定长为n的序列a，q次操作，每次查询一段区间的和，或修改一个数的权值。1≤n,q≤5×10^5,0≤a_i≤10^9。分析如果没有修改操作，这是一道非常简单的前缀和题。假如我们修改前缀和数组，查询就还是O(1)的，是否可行呢？当然不行。考虑......
  • 408 数据结构线性表算法
    第一章线性表定义：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。线性表的表示：若用L命名，表示：L=(a1,a2,a3,a4,a5,……,an)线性表的逻辑特性：a1：唯一的表头元素an：唯一的表尾元素除去a1：每个元素有且仅有一个直接前驱除去an：每个元素有且仅有一个直接后继......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99