网站导航
> 技术文档 > 数据结构---B+树_b+树结构

数据结构---B+树_b+树结构

网友: 技术文档 2025-07-30 13:49:19

数据结构—B+树

B+树是一种平衡的多路查找树，是数据库和文件系统中常用的索引结构。以下是对B+树的详细介绍：

一、基本结构特点

  1. 节点类型
    • B+树有内节点（非叶子节点）和叶子节点。内节点用于存储索引键和指向下一层节点的指针。例如，在一个包含数字键的B+树中，内节点可能存储键值为50、100等，这些键将数据范围划分成不同的区间，每个键对应一个指针指向子树。而叶子节点用于存储实际的数据记录指针（或者数据本身，这取决于具体的实现）。
    • 所有叶子节点都位于同一层，它们之间通过指针相互连接，形成一个有序的链表。这种结构使得范围查询非常高效。比如，要查找键值在10到20之间的所有记录，可以从第一个大于或等于10的叶子节点开始，沿着叶子节点链表顺序查找，直到遇到大于20的键值为止。
  2. 节点的键值和子节点数量限制
    • 假设B+树的阶数为m，那么内节点最多有m个子节点，最少有[m/2]个子节点（根节点除外，根节点至少有2个子节点，除非它是一个叶子节点）。对于叶子节点，最多可以存储m - 1个键值，最少存储[m/2] - 1个键值（这里m是B+树的阶数）。
    • 例如，一个阶数为4的B+树，内节点最多有4个子节点，最少有2个子节点（根节点除外）。叶子节点最多存储3个键值，最少存储1个键值。这种限制保证了B+树的平衡性，使得查找、插入和删除操作的性能相对稳定。
  3. 键值的存储顺序
    • 在B+树的每个节点中，键值是按照从小到大（或从大到小）的顺序存储的。在内节点中，键值用于划分子树的范围。例如，一个内节点的键值为{20，40，60}，那么它的子树范围可以分为：小于20的键值在第一个子树中，20到40之间的键值在第二个子树中，40到60之间的键值在第三个子树中，大于60的键值在第四个子树中。在叶子节点中，键值也是有序存储，方便范围查询。

二、B+树的操作

  1. 查找操作
    • 从根节点开始，根据目标键值与节点中键值的比较结果，沿着相应的指针向下查找。如果目标键值小于当前节点的第一个键值，就沿着第一个指针向下查找；如果目标键值在两个键值之间，就沿着中间的指针向下查找；如果目标键值大于当前节点的最后一个键值，就沿着最后一个指针向下查找。
    • 一直查找直到叶子节点，如果在叶子节点中找到目标键值，就返回相应的数据记录指针；如果没有找到，就返回查找失败的结果。查找操作的时间复杂度为O(logn)，其中n是B+树中叶子节点的数量。因为B+树是平衡的，每次查找都会将查找范围缩小到一个子树，这种对半查找的思想使得查找效率很高。
  2. 插入操作
    • 首先按照查找操作的方式找到目标键值应该插入的叶子节点位置。如果叶子节点没有满（即键值数量没有达到最大限制），直接将键值插入到合适的位置，并保持叶子节点中键值的有序性。
    • 如果叶子节点满了，就需要进行分裂操作。将叶子节点分裂成两个叶子节点，其中一个节点存储原节点中较小的一部分键值，另一个节点存储较大的一部分键值。然后将分裂产生的新节点的最小键值（或者最大键值，取决于具体实现）上移至父节点。如果父节点满了，父节点也会进行分裂，这个过程可能会一直向上进行，直到根节点分裂，甚至可能产生一个新的根节点。插入操作的时间复杂度也是O(logn)，因为分裂操作虽然会增加一些额外的步骤，但总体上不会改变操作的对数级别复杂度。
  3. 删除操作
    • 先找到要删除的键值所在的叶子节点。如果删除键值后叶子节点仍然满足最小键值数量限制，直接删除该键值即可。
    • 如果删除键值后叶子节点不满足最小键值数量限制，需要进行调整。可以从相邻的兄弟节点借一个键值来满足最小键值数量限制。如果相邻兄弟节点也满足最小键值数量限制，无法借键值，就需要将两个兄弟节点合并。合并后，父节点中的相应键值会被删除。如果父节点不满足最小键值数量限制，这个调整过程可能会一直向上进行，甚至可能导致根节点被删除，树的高度减小。删除操作的时间复杂度同样是O(logn)。

三、B+树的优点

  1. 适合磁盘存储
    • B+树的结构使得它能够很好地利用磁盘的顺序读写特性。因为B+树的内节点只存储键值和指针，而数据记录存储在叶子节点，叶子节点通过指针连接成链表。当进行范围查询时，可以顺序读取叶子节点中的数据，减少了磁盘的随机访问次数，从而提高了查询效率。在数据库系统中，数据通常存储在磁盘上，B+树的这种特性使得它成为理想的索引结构。
  2. 高效的范围查询
    • 由于叶子节点是有序的，并且通过指针连接，范围查询可以直接从一个叶子节点开始，沿着链表顺序查找，直到满足条件为止。相比之下，其他一些索引结构（如B树）在范围查询时可能需要多次回溯或者访问多个不连续的节点，B+树在这一点上具有明显优势。
  3. 平衡性好
    • B+树通过严格的节点键值和子节点数量限制，保证了树的平衡性。无论进行插入、删除操作，树的高度变化都不会太大，这使得各种操作的时间复杂度都能保持在对数级别，保证了操作的高效性。

四、B+树的应用场景

  1. 数据库索引
    • 在关系型数据库中，B+树被广泛用作主索引和辅助索引。例如，在一个学生信息表中，如果以学号作为主键建立索引，B+树可以快速定位到特定学号的学生记录。同时，也可以以姓名等字段建立辅助索引，通过B+树实现快速的姓名查找和范围查询（如查找姓氏为“张”的学生）。
  2. 文件系统
    • 在文件系统中，B+树可以用于管理文件的索引。它可以快速定位文件在磁盘上的存储位置，同时支持对文件名等属性的范围查询。例如，在一个大型的文件服务器中，通过B+树可以快速找到某个目录下所有以特定前缀命名的文件。

五、代码示例

5.1 数据库索引中的B+树代码示例（C++）

以下是一个简单的B+树插入操作的C++代码实现

#include#include#includeusing namespace std;const int M = 4; // B+树的阶数const int MM = 2 * M;const int L = 5; // 叶节点能容纳的最大键值对数struct Node { bool leaf; // 是否为叶节点 Node* parent; // 父节点 Node* children[MM + 1]; // 子节点 int values[MM]; // 记录值 int cnt; // 子节点数或者键值对数};class BPlusTree {public: BPlusTree(); ~BPlusTree(); void insert(int value); // 插入记录 void show(); // 显示整棵B+树private: void split(Node* x, int idx); // 对满节点分裂 void insertNonfull(Node* x, int value); // 插入到非满节点 void show(Node* x, int num); // 递归显示某个节点及其子树 Node* root; // 根节点};BPlusTree::BPlusTree() { root = NULL;}BPlusTree::~BPlusTree() { // TODO}void BPlusTree::split(Node* x, int idx) { Node* y = new Node(); Node* z = x->children[idx]; y->leaf = z->leaf; y->cnt = L; z->cnt = L; // 将z节点的后L个值移动到y节点 memcpy(y->values, z->values + L, sizeof(int) * L); if (!y->leaf) { memcpy(y->children, z->children + L, sizeof(Node*) * (L + 1)); for (int i = L; i children[i] = NULL; } } z->cnt = L; // 为父节点x插入键值，并将y节点加入到x的子节点中 for (int i = x->cnt + 1; i > idx + 1; i--) { x->children[i] = x->children[i - 1]; } x->children[idx + 1] = y; for (int i = x->cnt; i > idx; i--) { x->values[i] = x->values[i - 1]; } x->values[idx] = z->values[L]; x->cnt++;}void BPlusTree::insertNonfull(Node* x, int value) { int i = x->cnt - 1; if (x->leaf) { while (i >= 0 && value values[i]) { x->values[i + 1] = x->values[i]; i--; } x->values[i + 1] = value; x->cnt++; } else { while (i >= 0 && value values[i]) { i--; } i++; if (x->children[i]->cnt == MM) { split(x, i); if (value > x->values[i]) { i++; } } insertNonfull(x->children[i], value); }}void BPlusTree::insert(int value) { if (root == NULL) { root = new Node(); root->leaf = true; root->cnt = 1; root->values[0] = value; } else { if (root->cnt == MM) { Node* s = new Node(); s->leaf = false; s->children[0] = root; split(s, 0); root = s; if (value > root->values[0]) { insertNonfull(root->children[1], value); } else { insertNonfull(root->children[0], value); } } else { insertNonfull(root, value); } }}void BPlusTree::show() { if (root != NULL) { show(root, 0); }}void BPlusTree::show(Node* x, int num) { cout << \"(\" << num << \")\"; for (int i = 0; i cnt; i++) { cout <values[i] << \" \"; } cout <leaf) { for (int i = 0; i cnt; i++) { if (x->children[i] != NULL) { show(x->children[i], num + 1); } } }}int main() { BPlusTree tree; for (int i = 0; i < 20; i++) { tree.insert(i); } tree.show(); return 0;}

5.2 文件系统中的B+树代码示例（C#）

以下是一个B+树在文件系统中的简单实现，用于管理文件索引

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;public class BPlusTreeNode{ public List Keys { get; set; } public List Children { get; set; } public bool IsLeaf { get; set; } public BPlusTreeNode Next { get; set; } public BPlusTreeNode(bool isLeaf) { Keys = new List(); Children = new List(); IsLeaf = isLeaf; }}public class BPlusTree{ private int _minDegree; private BPlusTreeNode _root; public BPlusTree(int minDegree) { _minDegree = minDegree; _root = new BPlusTreeNode(true); } public void Insert(int key) { if (_root.Keys.Count == 2 * _minDegree - 1) { var newRoot = new BPlusTreeNode(false); newRoot.Children.Add(_root); SplitChild(newRoot, 0, _root); _root = newRoot; } InsertNonFull(_root, key); } private void InsertNonFull(BPlusTreeNode node, int key) { if (node.IsLeaf) { int i = node.Keys.Count - 1; while (i >= 0 && key = 0 && key  node.Keys[i]) {  i++; } } InsertNonFull(node.Children[i], key); } } private void SplitChild(BPlusTreeNode parent, int index, BPlusTreeNode fullChild) { var newNode = new BPlusTreeNode(fullChild.IsLeaf); parent.Keys.Insert(index, fullChild.Keys[_minDegree - 1]); parent.Children.Insert(index + 1, newNode); newNode.Keys.AddRange(fullChild.Keys.GetRange(_minDegree, _minDegree - 1)); fullChild.Keys.RemoveRange(_minDegree - 1, _minDegree); if (!fullChild.IsLeaf) { newNode.Children.AddRange(fullChild.Children.GetRange(_minDegree, _minDegree)); fullChild.Children.RemoveRange(_minDegree, _minDegree); } else { newNode.Next = fullChild.Next; fullChild.Next = newNode; } } public void PrintTree() { PrintNode(_root, \"\"); } private void PrintNode(BPlusTreeNode node, string indent) { Console.WriteLine(indent + string.Join(\", \", node.Keys)); if (!node.IsLeaf) { foreach (var child in node.Children) { PrintNode(child, indent + \" \"); } } }}namespace BPluse_Tree_CSharpTest{ internal class Program { static void Main(string[] args) { var bpt = new BPlusTree(2); bpt.Insert(10); bpt.Insert(20); bpt.Insert(5); bpt.Insert(6); bpt.Insert(12); bpt.Insert(30); bpt.Insert(7); bpt.Insert(17); bpt.PrintTree(); Console.ReadKey(); } }}

好的文章：

1.关于B+树的介绍、用途和c++代码实现

2.红黑树、AVL树、B树、B+树的对比与应用场景解析

网络标签：

相关问题