commit 5f0e5b3255b062a2abac37f37b7bd62657157379
parent c9dc60e53463fa292c47b54f79b18993a5e53ecd
Author: root <root>
Date: Thu, 20 Nov 2025 21:46:28 +0100
push new thing
Diffstat:
2 files changed, 179 insertions(+), 0 deletions(-)
diff --git a/awk/b_plus_tree.awk b/awk/b_plus_tree.awk
@@ -0,0 +1,179 @@
+#!/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);
+}
diff --git a/notes/sql/TODO.new b/notes/sql/TODO.new