12.7. Б-деревья

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<typename T>
struct BTreeNode {
    std::vector<T> keys;           // Ключи
    std::vector<BTreeNode*> children;  // Дети
    bool leaf;                     // Является ли листом

    BTreeNode(bool isLeaf = false) : leaf(isLeaf) {}
};

template<typename T>
class BTree {
private:
    BTreeNode<T>* root;
    int t;  // Минимальная степень

    int maxKeys() { return 2 * t - 1; }
    int minKeys() { return t - 1; }

public:
    BTree(int minDegree) : t(minDegree) {
        root = new BTreeNode<T>(true);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

std::pair<BTreeNode<T>*, int> search(BTreeNode<T>* node, const T& key) {
    // Находим позицию ключа или ребенка
    int i = 0;
    while (i < node->keys.size() && key > node->keys[i]) {
        i++;
    }

    // Нашли ключ
    if (i < node->keys.size() && key == node->keys[i]) {
        return {node, i};
    }

    // Ключ не найден и это лист
    if (node->leaf) {
        return {nullptr, -1};
    }

    // Рекурсивный поиск в ребёнке
    // В реальной реализации здесь происходит чтение с диска
    return search(node->children[i], key);
}

std::pair<BTreeNode<T>*, int> search(const T& key) {
    return search(root, key);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void splitChild(BTreeNode<T>* parent, int i) {
    BTreeNode<T>* full = parent->children[i];
    BTreeNode<T>* newNode = new BTreeNode<T>(full->leaf);

    // Переносим ключи: full получает [0, t-1), newNode — [t, 2t-1)
    T midKey = full->keys[t - 1];

    // Правая половина ключей
    newNode->keys.assign(full->keys.begin() + t, full->keys.end());
    // Левая половина ключей
    full->keys.resize(t - 1);

    // Переносим детей, если не лист
    if (!full->leaf) {
        newNode->children.assign(full->children.begin() + t, full->children.end());
        full->children.resize(t);
    }

    // Вставляем средний ключ в родителя
    parent->keys.insert(parent->keys.begin() + i, midKey);
    parent->children.insert(parent->children.begin() + i + 1, newNode);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void insert(const T& key) {
    // Если корень полон, создаём новый корень
    if (root->keys.size() == 2 * t - 1) {
        BTreeNode<T>* newRoot = new BTreeNode<T>();
        newRoot->children.push_back(root);
        root = newRoot;
        splitChild(newRoot, 0);
        insertNonfull(newRoot, key);
    } else {
        insertNonfull(root, key);
    }
}

void insertNonfull(BTreeNode<T>* node, const T& key) {
    int i = node->keys.size() - 1;

    if (node->leaf) {
        // Вставляем ключ в лист
        node->keys.push_back(T{});
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
    } else {
        // Ищем ребёнка для спуска
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        // Если ребёнок полон, расщепляем
        if (node->children[i]->keys.size() == 2 * t - 1) {
            splitChild(node, i);
            if (key > node->keys[i]) {
                i++;
            }
        }

        insertNonfull(node->children[i], key);
    }
}