30018：B 树页分裂与不变式验证

题目

实现最小度数为 $2$ 的 B 树页分裂操作，以及检查整组页是否构成合法 B 树的验证器。

解析

满子页有三个键。分裂时保存中间键和四个孩子引用，把中间键提升到父页，原页保留左半部分，新右页接收右半部分；父页中的键和孩子引用要从右向左搬移，避免覆盖尚未搬移的内容。

验证器使用带开闭语义的上下界检查键范围，不对极端整数做加减。访问标记同时承担环检测、共享子树检测和不可达页检查；递归完成后，只有所有页都恰好被访问一次才算合法。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

enum {
    BTREE_MAX_KEYS = 3,
    BTREE_MAX_CHILDREN = 4
};

typedef struct {
    bool leaf;
    size_t key_count;
    int64_t keys[BTREE_MAX_KEYS];
    size_t children[BTREE_MAX_CHILDREN];
} BTreePage;

static bool valid_reference(size_t page_count, size_t index) {
    return index != SIZE_MAX && index < page_count;
}

bool btree_split_full_child(
    BTreePage *pages,
    size_t page_count,
    size_t parent_index,
    size_t child_slot,
    size_t right_index,
    int64_t *out_promoted
) {
    if (pages == NULL || out_promoted == NULL || page_count == 0 ||
        parent_index >= page_count || right_index >= page_count ||
        parent_index == right_index) {
        return false;
    }
    BTreePage *parent = &pages[parent_index];
    if (parent->leaf || parent->key_count >= BTREE_MAX_KEYS ||
        child_slot > parent->key_count) {
        return false;
    }
    for (size_t i = 0; i <= parent->key_count; ++i) {
        if (!valid_reference(page_count, parent->children[i])) {
            return false;
        }
    }
    size_t child_index = parent->children[child_slot];
    if (!valid_reference(page_count, child_index) ||
        child_index == parent_index || child_index == right_index) {
        return false;
    }
    for (size_t page = 0; page < page_count; ++page) {
        for (size_t slot = 0; slot < BTREE_MAX_CHILDREN; ++slot) {
            if (pages[page].children[slot] == right_index) {
                return false;
            }
        }
    }

    BTreePage *child = &pages[child_index];
    if (child->key_count != BTREE_MAX_KEYS ||
        child->keys[0] >= child->keys[1] ||
        child->keys[1] >= child->keys[2]) {
        return false;
    }
    if (child->leaf) {
        for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
            if (child->children[i] != SIZE_MAX) {
                return false;
            }
        }
    } else {
        for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
            if (!valid_reference(page_count, child->children[i])) {
                return false;
            }
        }
    }

    int64_t promoted = child->keys[1];
    int64_t left_key = child->keys[0];
    int64_t right_key = child->keys[2];
    size_t old_children[BTREE_MAX_CHILDREN];
    for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
        old_children[i] = child->children[i];
    }

    size_t old_key_count = parent->key_count;
    for (size_t i = old_key_count; i > child_slot; --i) {
        parent->keys[i] = parent->keys[i - 1];
    }
    for (size_t i = old_key_count + 1;
         i > child_slot + 1;
         --i) {
        parent->children[i] = parent->children[i - 1];
    }
    parent->keys[child_slot] = promoted;
    parent->children[child_slot] = child_index;
    parent->children[child_slot + 1] = right_index;
    ++parent->key_count;

    child->key_count = 1;
    child->keys[0] = left_key;
    if (child->leaf) {
        for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
            child->children[i] = SIZE_MAX;
        }
    } else {
        child->children[0] = old_children[0];
        child->children[1] = old_children[1];
        child->children[2] = SIZE_MAX;
        child->children[3] = SIZE_MAX;
    }

    BTreePage *right = &pages[right_index];
    right->leaf = child->leaf;
    right->key_count = 1;
    right->keys[0] = right_key;
    if (right->leaf) {
        for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
            right->children[i] = SIZE_MAX;
        }
    } else {
        right->children[0] = old_children[2];
        right->children[1] = old_children[3];
        right->children[2] = SIZE_MAX;
        right->children[3] = SIZE_MAX;
    }
    *out_promoted = promoted;
    return true;
}

typedef struct {
    bool has_leaf_depth;
    size_t leaf_depth;
} ValidationContext;

static bool validate_page(
    const BTreePage *pages,
    size_t page_count,
    size_t index,
    unsigned char *state,
    bool is_root,
    bool has_lower,
    int64_t lower,
    bool has_upper,
    int64_t upper,
    size_t depth,
    ValidationContext *context
) {
    if (!valid_reference(page_count, index) || state[index] != 0) {
        return false;
    }
    const BTreePage *page = &pages[index];
    if (page->key_count > BTREE_MAX_KEYS ||
        (!is_root && page->key_count == 0) ||
        (is_root && page->key_count == 0 && !page->leaf)) {
        return false;
    }
    for (size_t i = 0; i < page->key_count; ++i) {
        if ((i > 0 && page->keys[i - 1] >= page->keys[i]) ||
            (has_lower && page->keys[i] <= lower) ||
            (has_upper && page->keys[i] >= upper)) {
            return false;
        }
    }
    state[index] = 1;

    if (page->leaf) {
        for (size_t i = 0; i < BTREE_MAX_CHILDREN; ++i) {
            if (page->children[i] != SIZE_MAX) {
                return false;
            }
        }
        if (!context->has_leaf_depth) {
            context->has_leaf_depth = true;
            context->leaf_depth = depth;
        } else if (context->leaf_depth != depth) {
            return false;
        }
    } else {
        for (size_t i = 0; i <= page->key_count; ++i) {
            if (!valid_reference(page_count, page->children[i])) {
                return false;
            }
        }
        for (size_t i = page->key_count + 1;
             i < BTREE_MAX_CHILDREN;
             ++i) {
            if (page->children[i] != SIZE_MAX) {
                return false;
            }
        }
        if (depth == SIZE_MAX) {
            return false;
        }
        for (size_t i = 0; i <= page->key_count; ++i) {
            bool child_has_lower = has_lower;
            bool child_has_upper = has_upper;
            int64_t child_lower = lower;
            int64_t child_upper = upper;
            if (i > 0) {
                child_has_lower = true;
                child_lower = page->keys[i - 1];
            }
            if (i < page->key_count) {
                child_has_upper = true;
                child_upper = page->keys[i];
            }
            if (!validate_page(
                    pages, page_count, page->children[i], state,
                    false, child_has_lower, child_lower,
                    child_has_upper, child_upper, depth + 1,
                    context
                )) {
                return false;
            }
        }
    }
    state[index] = 2;
    return true;
}

bool btree_validate(
    const BTreePage *pages,
    size_t page_count,
    size_t root
) {
    if (pages == NULL || page_count == 0 || root >= page_count ||
        page_count > SIZE_MAX / sizeof(unsigned char)) {
        return false;
    }
    unsigned char *state = calloc(page_count, sizeof *state);
    if (state == NULL) {
        return false;
    }
    ValidationContext context = {false, 0};
    bool valid = validate_page(
        pages, page_count, root, state,
        true, false, 0, false, 0, 0, &context
    );
    if (valid) {
        for (size_t i = 0; i < page_count; ++i) {
            if (state[i] != 2) {
                valid = false;
                break;
            }
        }
    }
    free(state);
    return valid;
}

固定最小度数下，页分裂只移动常数个键和引用，为 $O(1)$；验证器每个页和引用只访问一次，为 $O(P)$，访问标记占用 $O(P)$ 空间。