数据结构—B+树
B+树是一种平衡的多路查找树，是数据库和文件系统中常用的索引结构。以下是对B+树的详细介绍：
一、基本结构特点
- 节点类型
- B+树有内节点（非叶子节点）和叶子节点。内节点用于存储索引键和指向下一层节点的指针。例如，在一个包含数字键的B+树中，内节点可能存储键值为50、100等，这些键将数据范围划分成不同的区间，每个键对应一个指针指向子树。而叶子节点用于存储实际的数据记录指针（或者数据本身，这取决于具体的实现）。
- 所有叶子节点都位于同一层，它们之间通过指针相互连接，形成一个有序的链表。这种结构使得范围查询非常高效。比如，要查找键值在10到20之间的所有记录，可以从第一个大于或等于10的叶子节点开始，沿着叶子节点链表顺序查找，直到遇到大于20的键值为止。
- 节点的键值和子节点数量限制
- 假设B+树的阶数为m，那么内节点最多有m个子节点，最少有[m/2]个子节点（根节点除外，根节点至少有2个子节点，除非它是一个叶子节点）。对于叶子节点，最多可以存储m - 1个键值，最少存储[m/2] - 1个键值（这里m是B+树的阶数）。
- 例如，一个阶数为4的B+树，内节点最多有4个子节点，最少有2个子节点（根节点除外）。叶子节点最多存储3个键值，最少存储1个键值。这种限制保证了B+树的平衡性，使得查找、插入和删除操作的性能相对稳定。
- 键值的存储顺序
- 在B+树的每个节点中，键值是按照从小到大（或从大到小）的顺序存储的。在内节点中，键值用于划分子树的范围。例如，一个内节点的键值为{20，40，60}，那么它的子树范围可以分为：小于20的键值在第一个子树中，20到40之间的键值在第二个子树中，40到60之间的键值在第三个子树中，大于60的键值在第四个子树中。在叶子节点中，键值也是有序存储，方便范围查询。
二、B+树的操作
- 查找操作
- 从根节点开始，根据目标键值与节点中键值的比较结果，沿着相应的指针向下查找。如果目标键值小于当前节点的第一个键值，就沿着第一个指针向下查找；如果目标键值在两个键值之间，就沿着中间的指针向下查找；如果目标键值大于当前节点的最后一个键值，就沿着最后一个指针向下查找。
- 一直查找直到叶子节点，如果在叶子节点中找到目标键值，就返回相应的数据记录指针；如果没有找到，就返回查找失败的结果。查找操作的时间复杂度为O(logn)，其中n是B+树中叶子节点的数量。因为B+树是平衡的，每次查找都会将查找范围缩小到一个子树，这种对半查找的思想使得查找效率很高。
- 插入操作
- 首先按照查找操作的方式找到目标键值应该插入的叶子节点位置。如果叶子节点没有满（即键值数量没有达到最大限制），直接将键值插入到合适的位置，并保持叶子节点中键值的有序性。
- 如果叶子节点满了，就需要进行分裂操作。将叶子节点分裂成两个叶子节点，其中一个节点存储原节点中较小的一部分键值，另一个节点存储较大的一部分键值。然后将分裂产生的新节点的最小键值（或者最大键值，取决于具体实现）上移至父节点。如果父节点满了，父节点也会进行分裂，这个过程可能会一直向上进行，直到根节点分裂，甚至可能产生一个新的根节点。插入操作的时间复杂度也是O(logn)，因为分裂操作虽然会增加一些额外的步骤，但总体上不会改变操作的对数级别复杂度。
- 删除操作
- 先找到要删除的键值所在的叶子节点。如果删除键值后叶子节点仍然满足最小键值数量限制，直接删除该键值即可。
- 如果删除键值后叶子节点不满足最小键值数量限制，需要进行调整。可以从相邻的兄弟节点借一个键值来满足最小键值数量限制。如果相邻兄弟节点也满足最小键值数量限制，无法借键值，就需要将两个兄弟节点合并。合并后，父节点中的相应键值会被删除。如果父节点不满足最小键值数量限制，这个调整过程可能会一直向上进行，甚至可能导致根节点被删除，树的高度减小。删除操作的时间复杂度同样是O(logn)。
三、B+树的优点
- 适合磁盘存储
- B+树的结构使得它能够很好地利用磁盘的顺序读写特性。因为B+树的内节点只存储键值和指针，而数据记录存储在叶子节点，叶子节点通过指针连接成链表。当进行范围查询时，可以顺序读取叶子节点中的数据，减少了磁盘的随机访问次数，从而提高了查询效率。在数据库系统中，数据通常存储在磁盘上，B+树的这种特性使得它成为理想的索引结构。
- 高效的范围查询
- 由于叶子节点是有序的，并且通过指针连接，范围查询可以直接从一个叶子节点开始，沿着链表顺序查找，直到满足条件为止。相比之下，其他一些索引结构（如B树）在范围查询时可能需要多次回溯或者访问多个不连续的节点，B+树在这一点上具有明显优势。
- 平衡性好
- B+树通过严格的节点键值和子节点数量限制，保证了树的平衡性。无论进行插入、删除操作，树的高度变化都不会太大，这使得各种操作的时间复杂度都能保持在对数级别，保证了操作的高效性。
四、B+树的应用场景
- 数据库索引
- 在关系型数据库中，B+树被广泛用作主索引和辅助索引。例如，在一个学生信息表中，如果以学号作为主键建立索引，B+树可以快速定位到特定学号的学生记录。同时，也可以以姓名等字段建立辅助索引，通过B+树实现快速的姓名查找和范围查询（如查找姓氏为“张”的学生）。
- 文件系统
- 在文件系统中，B+树可以用于管理文件的索引。它可以快速定位文件在磁盘上的存储位置，同时支持对文件名等属性的范围查询。例如，在一个大型的文件服务器中，通过B+树可以快速找到某个目录下所有以特定前缀命名的文件。
五、代码示例
5.1 数据库索引中的B+树代码示例（C++）
以下是一个简单的B+树插入操作的C++代码实现
#include<iostream>
#include<cstring>
#include<vector>
using 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 < MM; i++) {
z->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 < x->values[i]) {
x->values[i + 1] = x->values[i];
i--;
}
x->values[i + 1] = value;
x->cnt++;
}
else {
while (i >= 0 && value < x->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 < x->cnt; i++) {
cout << x->values[i] << " ";
}
cout << endl;
if (!x->leaf) {
for (int i = 0; i <= x->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<int> Keys { get; set; }
public List<BPlusTreeNode> Children { get; set; }
public bool IsLeaf { get; set; }
public BPlusTreeNode Next { get; set; }
public BPlusTreeNode(bool isLeaf)
{
Keys = new List<int>();
Children = new List<BPlusTreeNode>();
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 < node.Keys[i])
{
i--;
}
node.Keys.Insert(i + 1, key);
}
else
{
int i = node.Keys.Count - 1;
while (i >= 0 && key < node.Keys[i])
{
i--;
}
i++;
if (node.Children[i].Keys.Count == 2 * _minDegree - 1)
{
SplitChild(node, i, node.Children[i]);
if (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();
}
}
}
好的文章：