Back (Current repo: scraps)

b_plus_tree.awk (4163B)

#!/usr/bin/awk -f

function new_node(leaf, id) {
    id = ++node_count;
    node[id]["leaf"] = leaf;
    node[id]["n"] = 0;
    node[id]["next"] = 0;
    return id;
}

function insert(r, key, s) {
    if (node[r]["n"] == 2 * order - 1) {
        s = new_node(0);
        node[s]["children"][1] = r;
        split_child(s, 1, r);
        insert_nonfull(s, key);
        root = s;
    } else {
        insert_nonfull(r, key);
    }
}

function insert_nonfull(x, k, i, c) {
    i = node[x]["n"]
    if (node[x]["leaf"]) {
        while (i >= 1 && k < node[x]["keys"][i]) {
            node[x]["keys"][i+1] = node[x]["keys"][i];
            i--;
        }
        node[x]["keys"][i+1] = k;
        node[x]["n"]++;
    } else {
        while (i >= 1 && k < node[x]["keys"][i]) i--
        i++;
        c = node[x]["children"][i];
        if (node[c]["n"] == 2 * order - 1) {
            split_child(x, i, c);
            if (k >= node[x]["keys"][i]) {
                i++;
            }
        }
        insert_nonfull(node[x]["children"][i], k);
    }
}

function split_child(p, i, y, z, t, j) {
    t = order;
    z = new_node(node[y]["leaf"]);

    if (node[y]["leaf"]) {
        for (j = 1; j <= t - 1; j++) {
            node[z]["keys"][j] = node[y]["keys"][j + t];
        }

        node[z]["n"] = t - 1;

        node[z]["next"] = node[y]["next"];
        node[y]["next"] = z;

        node[y]["n"] = t;

        promote_key = node[z]["keys"][1];

    } else {
        for (j = 1; j <= t - 1; j++) {
            node[z]["keys"][j] = node[y]["keys"][j + t];
        }

        for (j = 1; j <= t; j++) {
            node[z]["children"][j] = node[y]["children"][j + t];
        }

        node[z]["n"] = t - 1;
        node[y]["n"] = t - 1;

        promote_key = node[y]["keys"][t];
    }

    for (j = node[p]["n"]; j >= i; j--) {
        node[p]["keys"][j+1] = node[p]["keys"][j];
    }
    node[p]["keys"][i] = promote_key;

    for (j = node[p]["n"] + 1; j > i; j--) {
        node[p]["children"][j+1] = node[p]["children"][j];
    }
    node[p]["children"][i+1] = z;
    node[p]["n"]++;
}

function search(x, k, i, child) {
    if (node[x]["leaf"]) {
        for (i = 1; i <= node[x]["n"]; i++)
            if (node[x]["keys"][i] == k) {
                printf("Found %d in leaf node %d\n", k, x)
                return 1
            }
        printf("%d not found (reached leaf %d)\n", k, x)
        return 0
    }
    i = 1
    while (i <= node[x]["n"] && k >= node[x]["keys"][i]) i++
    child = node[x]["children"][i]
    return search(child, k)
}

function search_range(r, a, b, x, i) {
    x = r;
    while (!node[x]["leaf"]) {
        i = 1;
        while (i <= node[x]["n"] && a >= node[x]["keys"][i]) {
            i++;
        }
        x = node[x]["children"][i];
    }

    while (x) {
        for (i = 1; i <= node[x]["n"]; i++) {
            k = node[x]["keys"][i];
            if (k >= a && k <= b) {
                printf "%d ", k;
            }
            if (k > b) {
                print "";
                return;
            }
        }
        x = node[x]["next"];
    }
    print "";
}

function print_tree(x, depth,    i, pad) {
    pad = sprintf("%" (depth*4) "s", "");
    printf("%sNode %d: ", pad, x);
    for (i = 1; i <= node[x]["n"]; i++) {
        printf("%d ", node[x]["keys"][i]);
    }
    print (node[x]["leaf"] ? "(leaf)" : "");
    if (!node[x]["leaf"]) {
        for (i = 1; i <= node[x]["n"] + 1; i++) {
            print_tree(node[x]["children"][i], depth + 1);
        }
    }
}

function range_scan(r, x, i) {
    x = r;
    while (!node[x]["leaf"]) {
        x = node[x]["children"][1];
    }
    while (x) {
        for (i = 1; i <= node[x]["n"]; i++) {
            printf "%d ", node[x]["keys"][i];
        }
        x = node[x]["next"];
    }
    print "";
}

BEGIN{
    order = 3;
    root = new_node(1);

    for (i = 1; i <= 20; i++) {
        insert(root, i);
    }
    print "-----";
    print "Full tree:";
    print_tree(root, 0);

    print "\nSearch tests:";
    search(root, 5);
    search(root, 15);
    search(root, 25);

    print "\nRange search [8..17]:";
    search_range(root, 8, 17);
}