B+树排序C++测试程序

下面是一个简单的用于进行B+树排序的C++测试程序的示例：

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

// B+树节点的结构
struct BPlusTreeNode {
    bool isLeaf;
    std::vector<int> keys;
    std::vector<BPlusTreeNode*> children;
    BPlusTreeNode* parent;

    BPlusTreeNode(bool leaf = false) : isLeaf(leaf), parent(nullptr) {}
};

// B+树类
class BPlusTree {
private:
    int degree; // B+树的度
    BPlusTreeNode* root;

public:
    BPlusTree(int deg) : degree(deg), root(nullptr) {}

    // 插入键值对
    void insert(int key) {
        if (root == nullptr) {
            root = new BPlusTreeNode(true);
            root->keys.push_back(key);
            return;
        }

        BPlusTreeNode* node = findLeafNode(key);

        // 在叶节点中插入键值
        node->keys.push_back(key);
        std::sort(node->keys.begin(), node->keys.end());

        // 如果叶节点超过度数，则进行分裂
        if (node->keys.size() > degree) {
            splitNode(node);
        }
    }

    // 找到包含给定键值的叶节点
    BPlusTreeNode* findLeafNode(int key) {
        BPlusTreeNode* node = root;

        while (!node->isLeaf) {
            int i = 0;
            while (i < node->keys.size() && key >= node->keys[i]) {
                i++;
            }
            node = node->children[i];
        }

        return node;
    }

    // 分裂节点
    void splitNode(BPlusTreeNode* node) {
        int midIndex = node->keys.size() / 2;
        int midKey = node->keys[midIndex];

        // 创建一个新的节点作为右兄弟节点
        BPlusTreeNode* rightNode = new BPlusTreeNode(node->isLeaf);
        rightNode->keys.assign(node->keys.begin() + midIndex, node->keys.end());
        rightNode->parent = node->parent;

        // 更新原节点的键值
        node->keys.resize(midIndex);

        // 更新父节点的链接
        if (node->parent == nullptr) {
            // 如果原节点是根节点，则创建一个新的根节点
            BPlusTreeNode* newRoot = new BPlusTreeNode(false);
            newRoot->keys.push_back(midKey);
            newRoot->children.push_back(node);
            newRoot->children.push_back(rightNode);

            node->parent = newRoot;
            rightNode->parent = newRoot;

            root = newRoot;
        } else {
            // 如果原节点不是根节点，则将右兄弟节点插入父节点中
            int insertIndex = insertIntoParent(node->parent, midKey, rightNode);
            rightNode->parent = node->parent;

            // 调整父节点的链接
            for (int i = node->parent->keys.size() - 1; i > insertIndex; i--) {
                std::swap(node->parent->children[i], node->parent->children[i + 1]);
            }
            node->parent->children[insertIndex + 1] = rightNode;
        }
    }

    // 将节点插入到父节点中
    int insertIntoParent(BPlusTreeNode* parent, int key, BPlusTreeNode* node) {
        int insertIndex = 0;
        while (insertIndex < parent->keys.size() && key >= parent->keys[insertIndex]) {
            insertIndex++;
        }

        parent->keys.insert(parent->keys.begin() + insertIndex, key);
        parent->children.insert(parent->children.begin() + insertIndex + 1, node);

        // 如果父节点超过度数，则进行分裂
        if (parent->keys.size() > degree) {
            splitNode(parent);
        }

        return insertIndex;
    }

    // 中序遍历B+树
    void inorderTraversal(BPlusTreeNode* node) {
        if (node == nullptr) {
            return;
        }

        if (node->isLeaf) {
            for (int key : node->keys) {
                std::cout << key << " ";
            }
        } else {
            for (int i = 0; i < node->keys.size(); i++) {
                inorderTraversal(node->children[i]);
                std::cout << node->keys[i] << " ";
            }
            inorderTraversal(node->children.back());
        }
    }

    // 打印B+树
    void printTree() {
        inorderTraversal(root);
        std::cout << std::endl;
    }
};

int main() {
    BPlusTree btree(3); // 创建一个度为3的B+树

    // 插入一些测试数据
    btree.insert(8);
    btree.insert(4);
    btree.insert(12);
    btree.insert(2);
    btree.insert(6);
    btree.insert(10);
    btree.insert(14);
    btree.insert(1);
    btree.insert(3);
    btree.insert(5);
    btree.insert(7);
    btree.insert(9);
    btree.insert(11);
    btree.insert(13);
    btree.insert(15);

    // 打印排序后的结果
    btree.printTree();

    return 0;
}

这个程序演示了如何使用B+树对一组整数进行排序。在主函数中，我们创建了一个度为3的B+树对象，并插入了一些测试数据。然后，我们通过中序遍历B+树来打印排序后的结果。

请注意，这只是一个简单的示例程序，用于演示B+树的基本原理和功能。实际应用中，可能需要根据具体需求进行更多的功能扩展和优化。