Multiway Search Trees | Advanced Data Structures

LEARNING GOALS

🎯 Learning Objectives

After completing this topic, you should be able to:

Explain the order, minimum occupancy and height rules of a multiway search tree.
Search and traverse a node containing several sorted keys.
Insert into B-Trees using node splitting and median promotion.
Delete using predecessor/successor replacement, borrowing, merging and root contraction.
Explain why B+ Trees keep records in linked leaves and support efficient range queries.
Differentiate B-Trees, B+ Trees, 2–3 Trees and 2–3–4 Trees.
Trace complete C implementations and every balancing decision.

MORE KEYS, FEWER LEVELS

🧭 1. Why Multiway Search Trees?

A binary search tree stores one key and at most two children per node. A multiway tree stores several sorted keys, so one node can direct the search into many child ranges.

Binary Search Tree

One key divides the number line into two ranges.

Fan-out: at most 2

Multiway Search Tree

k sorted keys divide the number line into k + 1 ranges.

Fan-out: many children

1

Read Node

Load one disk-sized node containing several keys.

2

Find Interval

Locate the first key greater than or equal to the target.

3

Match or Descend

Return on equality or choose the corresponding child range.

4

Stay Balanced

Split overflow and repair underflow so all leaves remain level.

Main advantage: High fan-out produces a very small height, reducing expensive disk or SSD page reads in databases and file systems.

Order m

A node has at most m children and m − 1 keys.

Internal rule

A node with k keys has k + 1 children.

Sorted keys

Keys inside every node remain strictly ordered.

Balanced leaves

All leaves occur at the same depth.

COMPLETE PRACTICAL SET

🧰 2. Operations & Algorithms

Operation	Main action	Balancing event	Typical time
Search	Search keys inside a node, then choose one child interval	None	O(log n)
Insertion	Insert in a leaf or descend through non-full nodes	Split a full node and promote a separator	O(log n)
Deletion	Remove from leaf or replace an internal key	Borrow, rotate, merge and possibly contract root	O(log n)
Traversal	Visit children and keys in sorted order	None	O(n)
Range search	Find the first key, then scan consecutive leaves	Uses B+ leaf links	O(log n + k)
Bulk loading	Build leaves from sorted data, then build upper levels	Occupancy planned bottom-up	O(n)

➕ Insertion — Split and PromoteOpen algorithm

Top-Down B-Tree Insertion

If the root is full, create a new root and split the old root.
Within the current node, find the child range for the new key.
Before descending, split that child if it is full.
After promotion, choose the left or right split child.
Insert the key into the final non-full leaf in sorted order.

Why split before descending? It guarantees that insertion never enters a full node, so the algorithm finishes in one downward pass.

➖ Deletion — Complete CasesOpen algorithm

Leaf deletion

Remove the key directly if the node keeps the minimum number of keys.

Internal key

Replace with predecessor or successor when the corresponding child has spare keys.

Borrow / rotation

Move a parent separator down and a sibling key up.

Merge

Combine two minimum children with their parent separator.

Prepare before descent

Never descend into a minimum child; borrow or merge first.

Root contraction

If an internal root becomes empty, its only child becomes the new root.

Top-Down Deletion

Locate the key position in the current node.
If found in a leaf, remove it.
If found internally, use predecessor, successor or merge according to child occupancy.
If not found internally, ensure the chosen child has more than the minimum keys before descending.
Borrow from a rich sibling; otherwise merge with a sibling.
After deletion, replace an empty root by its only child.

🔎 Search, Traversal and Range SearchOpen algorithms

Search

Find the first key ≥ target. Return on equality; otherwise descend through child i.

Sorted traversal

Visit child 0, key 0, child 1, key 1, …, then the final child.

B+ exact search

Use internal separators only for routing; confirm the record in a leaf.

B+ range search

Find the first qualifying leaf, then follow next-leaf links until the upper bound is passed.

DATABASE-STYLE BALANCED INDEX

🌲 3. B-Tree

A B-Tree stores keys and records in both internal and leaf nodes. With minimum degree t, every non-root node has t − 1 to 2t − 1 keys, and every internal non-root node has t to 2t children.

Maximum keys

2t − 1

Minimum keys

t − 1 for every non-root node

Maximum children

2t

All leaves

At the same depth

Example with t = 2: every node holds 1 to 3 keys and at most 4 children. This special case is exactly a 2–3–4 Tree.

Search Algorithm

Scan keys until key[i] ≥ target or the node ends.
If key[i] equals target, return the node and position.
If the node is a leaf, return not found.
Otherwise continue with child[i].

💻 Complete C Program — B-Tree Insert, Search, Traverse and DeleteView program

#include <stdio.h>
#include <stdlib.h>

#define T 2
#define MAX_KEYS (2 * T - 1)
#define MAX_CHILDREN (2 * T)

typedef struct BTreeNode {
    int keys[MAX_KEYS];
    struct BTreeNode *child[MAX_CHILDREN];
    int count;
    int leaf;
} BTreeNode;

BTreeNode *createBTreeNode(int leaf) {
    BTreeNode *node = malloc(sizeof(BTreeNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->count = 0;
    node->leaf = leaf;
    for (int i = 0; i < MAX_CHILDREN; i++) node->child[i] = NULL;
    return node;
}

void traverseBTree(BTreeNode *node) {
    int i;
    for (i = 0; i < node->count; i++) {
        if (!node->leaf) traverseBTree(node->child[i]);
        printf("%d ", node->keys[i]); /* btree traverse */
    }
    if (!node->leaf) traverseBTree(node->child[i]);
}

BTreeNode *searchBTree(BTreeNode *node, int key) {
    int i = 0;
    while (i < node->count && key > node->keys[i]) i++; /* btree search loop */
    if (i < node->count && key == node->keys[i]) return node; /* btree search result */
    if (node->leaf) return NULL;
    return searchBTree(node->child[i], key);
}

void splitBTreeChild(BTreeNode *parent, int index) {
    BTreeNode *full = parent->child[index];
    BTreeNode *right = createBTreeNode(full->leaf);
    right->count = T - 1;
    for (int j = 0; j < T - 1; j++) right->keys[j] = full->keys[j + T];
    if (!full->leaf)
        for (int j = 0; j < T; j++) right->child[j] = full->child[j + T];
    full->count = T - 1;
    for (int j = parent->count; j >= index + 1; j--)
        parent->child[j + 1] = parent->child[j];
    parent->child[index + 1] = right;
    for (int j = parent->count - 1; j >= index; j--)
        parent->keys[j + 1] = parent->keys[j];
    parent->keys[index] = full->keys[T - 1]; /* btree promote median */
    parent->count++; /* btree split child */
}

void insertBTreeNonFull(BTreeNode *node, int key) {
    int i = node->count - 1;
    if (node->leaf) {
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->count++; /* btree insert leaf */
        return;
    }
    while (i >= 0 && key < node->keys[i]) i--;
    i++; /* btree choose child */
    if (node->child[i]->count == MAX_KEYS) {
        splitBTreeChild(node, i);
        if (key > node->keys[i]) i++;
    }
    insertBTreeNonFull(node->child[i], key);
}

void insertBTree(BTreeNode **root, int key) {
    if (searchBTree(*root, key) != NULL) return;
    if ((*root)->count == MAX_KEYS) {
        BTreeNode *newRoot = createBTreeNode(0);
        newRoot->child[0] = *root;
        splitBTreeChild(newRoot, 0); /* btree split root */
        *root = newRoot;
    }
    insertBTreeNonFull(*root, key); /* btree insert call */
}

int findKey(BTreeNode *node, int key) {
    int index = 0;
    while (index < node->count && node->keys[index] < key) index++;
    return index;
}

int predecessor(BTreeNode *node, int index) {
    BTreeNode *current = node->child[index];
    while (!current->leaf) current = current->child[current->count];
    return current->keys[current->count - 1];
}

int successor(BTreeNode *node, int index) {
    BTreeNode *current = node->child[index + 1];
    while (!current->leaf) current = current->child[0];
    return current->keys[0];
}

void removeBTreeKey(BTreeNode *node, int key);

void mergeBTreeChildren(BTreeNode *node, int index) {
    BTreeNode *left = node->child[index];
    BTreeNode *right = node->child[index + 1];
    left->keys[T - 1] = node->keys[index];
    for (int i = 0; i < right->count; i++) left->keys[i + T] = right->keys[i];
    if (!left->leaf)
        for (int i = 0; i <= right->count; i++) left->child[i + T] = right->child[i];
    for (int i = index + 1; i < node->count; i++) node->keys[i - 1] = node->keys[i];
    for (int i = index + 2; i <= node->count; i++) node->child[i - 1] = node->child[i];
    left->count += right->count + 1;
    node->count--;
    free(right); /* btree merge children */
}

void borrowBTreeLeft(BTreeNode *node, int index) {
    BTreeNode *child = node->child[index];
    BTreeNode *sibling = node->child[index - 1];
    for (int i = child->count - 1; i >= 0; i--) child->keys[i + 1] = child->keys[i];
    if (!child->leaf)
        for (int i = child->count; i >= 0; i--) child->child[i + 1] = child->child[i];
    child->keys[0] = node->keys[index - 1];
    if (!child->leaf) child->child[0] = sibling->child[sibling->count];
    node->keys[index - 1] = sibling->keys[sibling->count - 1];
    child->count++;
    sibling->count--; /* btree borrow left */
}

void borrowBTreeRight(BTreeNode *node, int index) {
    BTreeNode *child = node->child[index];
    BTreeNode *sibling = node->child[index + 1];
    child->keys[child->count] = node->keys[index];
    if (!child->leaf) child->child[child->count + 1] = sibling->child[0];
    node->keys[index] = sibling->keys[0];
    for (int i = 1; i < sibling->count; i++) sibling->keys[i - 1] = sibling->keys[i];
    if (!sibling->leaf)
        for (int i = 1; i <= sibling->count; i++) sibling->child[i - 1] = sibling->child[i];
    child->count++;
    sibling->count--; /* btree borrow right */
}

void prepareBTreeChild(BTreeNode *node, int index) {
    if (index > 0 && node->child[index - 1]->count >= T)
        borrowBTreeLeft(node, index);
    else if (index < node->count && node->child[index + 1]->count >= T)
        borrowBTreeRight(node, index);
    else if (index < node->count)
        mergeBTreeChildren(node, index);
    else
        mergeBTreeChildren(node, index - 1);
}

void removeBTreeKey(BTreeNode *node, int key) {
    int index = findKey(node, key); /* btree delete locate */
    if (index < node->count && node->keys[index] == key) {
        if (node->leaf) {
            for (int i = index + 1; i < node->count; i++) node->keys[i - 1] = node->keys[i];
            node->count--; /* btree delete leaf */
        } else if (node->child[index]->count >= T) {
            int value = predecessor(node, index);
            node->keys[index] = value; /* btree delete predecessor */
            removeBTreeKey(node->child[index], value);
        } else if (node->child[index + 1]->count >= T) {
            int value = successor(node, index);
            node->keys[index] = value; /* btree delete successor */
            removeBTreeKey(node->child[index + 1], value);
        } else {
            mergeBTreeChildren(node, index);
            removeBTreeKey(node->child[index], key);
        }
        return;
    }
    if (node->leaf) return;
    int last = (index == node->count);
    if (node->child[index]->count < T) prepareBTreeChild(node, index);
    if (last && index > node->count) removeBTreeKey(node->child[index - 1], key);
    else removeBTreeKey(node->child[index], key);
}

void deleteBTree(BTreeNode **root, int key) {
    removeBTreeKey(*root, key); /* btree delete call */
    if ((*root)->count == 0 && !(*root)->leaf) {
        BTreeNode *old = *root;
        *root = (*root)->child[0];
        free(old); /* btree contract root */
    }
}

int main(void) {
    int n, key, query, removeKey;
    BTreeNode *root = createBTreeNode(1); /* btree create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        insertBTree(&root, key);
    }
    scanf("%d%d", &query, &removeKey);
    printf("Search: %s\n", searchBTree(root, query) ? "Found" : "Not Found"); /* btree search call */
    deleteBTree(&root, removeKey);
    printf("After deletion: ");
    traverseBTree(root);
    printf("\n"); /* btree complete */ /* multiway complete */
    return 0;
}

Sample Input

10
10 20 5 6 12 30 7 17 3 25
17 6

Sample Output

Search: Found
After deletion: 3 5 7 10 12 17 20 25 30

RANGE-QUERY SPECIALIST

🍃 4. B+ Tree

A B+ Tree stores separator copies in internal nodes and keeps every actual record in leaves. Leaves are linked from left to right, making sequential and range access exceptionally efficient.

Internal Nodes

Contain only routing keys and child pointers, so fan-out is high.

Leaf Nodes

Contain all searchable records and a pointer to the next leaf.

Exact search

Always finishes at a leaf.

Range search

O(log n + k) using leaf links.

Leaf split

Copy the first key of the right leaf into the parent.

Internal split

Promote the middle separator and remove it from the children.

Range Search Algorithm

Search for the lower bound and reach its leaf.
Skip leaf keys smaller than the lower bound.
Output keys while they are within the upper bound.
Follow the next-leaf pointer when the current leaf ends.
Stop as soon as a key exceeds the upper bound.

💻 Complete C Program — B+ Tree Insert, Search and Range SearchView program

#include <stdio.h>
#include <stdlib.h>

#define ORDER 4
#define MAX_KEYS (ORDER - 1)

typedef struct BPlusNode {
    int keys[ORDER];
    struct BPlusNode *child[ORDER + 1];
    struct BPlusNode *next;
    int count;
    int leaf;
} BPlusNode;

typedef struct SplitResult {
    int split;
    int separator;
    BPlusNode *right;
} SplitResult;

BPlusNode *createBPlusNode(int leaf) {
    BPlusNode *node = malloc(sizeof(BPlusNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->count = 0;
    node->leaf = leaf;
    node->next = NULL;
    for (int i = 0; i <= ORDER; i++) node->child[i] = NULL;
    return node;
}

SplitResult insertBPlusRecursive(BPlusNode *node, int key) {
    SplitResult result = {0, 0, NULL};
    if (node->leaf) {
        int index = 0;
        while (index < node->count && node->keys[index] < key) index++;
        if (index < node->count && node->keys[index] == key) return result;
        for (int i = node->count; i > index; i--) node->keys[i] = node->keys[i - 1];
        node->keys[index] = key;
        node->count++; /* bplus insert leaf */
        if (node->count <= MAX_KEYS) return result;
        BPlusNode *right = createBPlusNode(1);
        int leftCount = node->count / 2;
        right->count = node->count - leftCount;
        for (int i = 0; i < right->count; i++) right->keys[i] = node->keys[leftCount + i];
        node->count = leftCount;
        right->next = node->next;
        node->next = right;
        result.split = 1;
        result.separator = right->keys[0];
        result.right = right; /* bplus split leaf */
        return result;
    }

    int index = 0;
    while (index < node->count && key >= node->keys[index]) index++; /* bplus choose child */
    SplitResult childResult = insertBPlusRecursive(node->child[index], key);
    if (!childResult.split) return result;
    for (int i = node->count; i > index; i--) node->keys[i] = node->keys[i - 1];
    for (int i = node->count + 1; i > index + 1; i--) node->child[i] = node->child[i - 1];
    node->keys[index] = childResult.separator;
    node->child[index + 1] = childResult.right;
    node->count++;
    if (node->count <= MAX_KEYS) return result;

    int middle = node->count / 2;
    BPlusNode *right = createBPlusNode(0);
    result.separator = node->keys[middle];
    right->count = node->count - middle - 1;
    for (int i = 0; i < right->count; i++) right->keys[i] = node->keys[middle + 1 + i];
    for (int i = 0; i <= right->count; i++) right->child[i] = node->child[middle + 1 + i];
    node->count = middle;
    result.split = 1;
    result.right = right; /* bplus split internal */
    return result;
}

void insertBPlus(BPlusNode **root, int key) {
    SplitResult result = insertBPlusRecursive(*root, key); /* bplus insert call */
    if (result.split) {
        BPlusNode *newRoot = createBPlusNode(0);
        newRoot->keys[0] = result.separator;
        newRoot->child[0] = *root;
        newRoot->child[1] = result.right;
        newRoot->count = 1;
        *root = newRoot; /* bplus new root */
    }
}

BPlusNode *findBPlusLeaf(BPlusNode *root, int key) {
    BPlusNode *node = root;
    while (!node->leaf) {
        int index = 0;
        while (index < node->count && key >= node->keys[index]) index++; /* bplus search loop */
        node = node->child[index];
    }
    return node;
}

int searchBPlus(BPlusNode *root, int key) {
    BPlusNode *leaf = findBPlusLeaf(root, key);
    for (int i = 0; i < leaf->count; i++)
        if (leaf->keys[i] == key) return 1; /* bplus search result */
    return 0;
}

void rangeBPlus(BPlusNode *root, int low, int high) {
    BPlusNode *leaf = findBPlusLeaf(root, low); /* bplus range call */
    while (leaf != NULL) {
        for (int i = 0; i < leaf->count; i++) {
            if (leaf->keys[i] > high) return;
            if (leaf->keys[i] >= low) printf("%d ", leaf->keys[i]); /* bplus range output */
        }
        leaf = leaf->next;
    }
}

int main(void) {
    int n, key, query, low, high;
    BPlusNode *root = createBPlusNode(1); /* bplus create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        insertBPlus(&root, key);
    }
    scanf("%d%d%d", &query, &low, &high);
    printf("Search: %s\n", searchBPlus(root, query) ? "Found" : "Not Found"); /* bplus search call */
    printf("Range: ");
    rangeBPlus(root, low, high);
    printf("\n"); /* bplus complete */ /* multiway complete */
    return 0;
}

Sample Input

10
5 10 15 20 25 30 35 40 45 50
25 18 42

Sample Output

Search: Found
Range: 20 25 30 35 40

TWO OR THREE CHILDREN

🌿 5. 2–3 Tree

Every internal node is either a 2-node containing one key and two children, or a 3-node containing two keys and three children. All leaves remain at the same level.

2-node

One key and two child ranges.

3-node

Two ordered keys and three child ranges.

Overflow

A temporary three-key node splits and promotes its middle key.

Underflow

Redistribute through the parent or merge with a sibling.

Bottom-Up Insertion

Search down to the appropriate leaf.
Insert the key in sorted order.
If the leaf now has three keys, promote the middle key.
Keep the smallest key in the left node and the largest in a new right node.
Repeat the split upward; create a new root if required.

💻 Complete C Program — 2–3 Tree Insert, Search and TraverseView program

#include <stdio.h>
#include <stdlib.h>

typedef struct TTNode {
    int keys[3];
    struct TTNode *child[4];
    struct TTNode *parent;
    int count;
    int leaf;
} TTNode;

TTNode *createTTNode(int leaf) {
    TTNode *node = malloc(sizeof(TTNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->count = 0;
    node->leaf = leaf;
    node->parent = NULL;
    for (int i = 0; i < 4; i++) node->child[i] = NULL;
    return node;
}

TTNode *searchTT(TTNode *node, int key) {
    while (node != NULL) {
        int index = 0;
        while (index < node->count && key > node->keys[index]) index++; /* tt search loop */
        if (index < node->count && key == node->keys[index]) return node; /* tt search result */
        if (node->leaf) return NULL;
        node = node->child[index];
    }
    return NULL;
}

void insertKeySorted(TTNode *node, int key) {
    int index = node->count;
    while (index > 0 && key < node->keys[index - 1]) {
        node->keys[index] = node->keys[index - 1];
        index--;
    }
    node->keys[index] = key;
    node->count++;
}

void insertPromoted(TTNode *parent, TTNode *left, int key, TTNode *right) {
    int childIndex = 0;
    while (childIndex <= parent->count && parent->child[childIndex] != left) childIndex++;
    for (int i = parent->count; i > childIndex; i--) parent->keys[i] = parent->keys[i - 1];
    for (int i = parent->count + 1; i > childIndex + 1; i--) parent->child[i] = parent->child[i - 1];
    parent->keys[childIndex] = key;
    parent->child[childIndex + 1] = right;
    right->parent = parent;
    parent->count++;
}

void splitTT(TTNode **root, TTNode *node) {
    while (node->count == 3) {
        int promoted = node->keys[1];
        TTNode *right = createTTNode(node->leaf);
        right->keys[0] = node->keys[2];
        right->count = 1;
        node->count = 1;
        if (!node->leaf) {
            right->child[0] = node->child[2];
            right->child[1] = node->child[3];
            right->child[0]->parent = right;
            right->child[1]->parent = right;
        }
        if (node->parent == NULL) {
            TTNode *newRoot = createTTNode(0);
            newRoot->keys[0] = promoted;
            newRoot->count = 1;
            newRoot->child[0] = node;
            newRoot->child[1] = right;
            node->parent = newRoot;
            right->parent = newRoot;
            *root = newRoot; /* tt new root */
            return;
        }
        TTNode *parent = node->parent;
        insertPromoted(parent, node, promoted, right); /* tt promote middle */
        node = parent;
    }
}

void insertTT(TTNode **root, int key) {
    if (searchTT(*root, key) != NULL) return;
    TTNode *node = *root;
    while (!node->leaf) {
        int index = 0;
        while (index < node->count && key > node->keys[index]) index++;
        node = node->child[index]; /* tt choose child */
    }
    insertKeySorted(node, key); /* tt insert leaf */
    splitTT(root, node); /* tt insert call */
}

void traverseTT(TTNode *node) {
    int i;
    for (i = 0; i < node->count; i++) {
        if (!node->leaf) traverseTT(node->child[i]);
        printf("%d ", node->keys[i]); /* tt traverse */
    }
    if (!node->leaf) traverseTT(node->child[i]);
}

int main(void) {
    int n, key, query;
    TTNode *root = createTTNode(1); /* tt create root */
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        insertTT(&root, key);
    }
    scanf("%d", &query);
    printf("Search: %s\n", searchTT(root, query) ? "Found" : "Not Found"); /* tt search call */
    printf("Sorted: ");
    traverseTT(root);
    printf("\n"); /* tt complete */ /* multiway complete */
    return 0;
}

Sample Input

9
20 10 30 5 15 25 35 12 18
25

Sample Output

Search: Found
Sorted: 5 10 12 15 18 20 25 30 35

B-TREE OF MINIMUM DEGREE TWO

🌴 6. 2–3–4 Tree

A 2–3–4 Tree permits 2-nodes, 3-nodes and 4-nodes. It is exactly a B-Tree with t = 2, so a node stores one, two or three keys and has two, three or four children.

2-node

1 key, 2 children

3-node

2 keys, 3 children

4-node

3 keys, 4 children

Red–Black relation

Each 3/4-node can be represented by linked red nodes.

Top-Down Insertion

Split every 4-node encountered before descending through it.
Promote the middle key into the parent.
Continue into the correct 2-node or 3-node child.
Insert the key into the non-full leaf.
If the root was a 4-node, split it and increase the height by one.

💻 C Program Note — 2–3–4 TreeView explanation

The complete B-Tree C program above uses T = 2; therefore, it is already a complete 2–3–4 Tree program supporting insertion, search, traversal and deletion. The visualizer provides a separate 2–3–4 selection so you can study the same rules using the familiar node names.

Exam connection: B-Tree with minimum degree 2 = 2–3–4 Tree. A 2–3–4 Tree can also be transformed into an equivalent Red–Black Tree.

CHOOSING THE STRUCTURE

⚖️ 7. Comparison

Structure	Keys per node	Where records live	Best strength	Common use
B-Tree	Many	Internal and leaves	General balanced disk index	File systems, storage engines
B+ Tree	Many	Leaves only	Range and sequential access	Database indexes
2–3 Tree	1 or 2	All nodes	Simple multiway balancing theory	Teaching and proofs
2–3–4 Tree	1, 2 or 3	All nodes	Connection to B-Trees and Red–Black Trees	Teaching balanced search trees

INTERACTIVE ALGORITHM VISUALIZATION

🎬 8. Premium Multiway Tree Visualizer

Choose a structure and operation, then follow node scans, child selection, median promotion, splitting, searching, deletion repair and range output step by step.

CodeBhavya

KeysSearch KeyStructureOperation

Choose a structure and operation, verify the input and click Load Visualizer.

SELECTABLE C PROGRAM TRACER

🔍 9. Program Tracing — Multiway Trees

Select a program. The matching complete C source appears with line numbers, live variables and the evolving multiway tree.

KeysSearch KeyProgram

Select a program and click Load Program Tracer.

DESIGN DECISION

🧠 10. Which One Should You Use?

General Disk Index

Use a B-Tree when records may be stored throughout the tree.

Database Range Queries

Use a B+ Tree because all records are in linked leaves.

Learn Multiway Balancing

Use a 2–3 Tree for the smallest clean split and underflow cases.

Connect to Red–Black Trees

Use a 2–3–4 Tree to understand how red links encode multi-key nodes.

DEBUGGING CHECKLIST

⚠️ 11. Common Mistakes

Wrong child interval

Child i contains keys between separator i − 1 and separator i.

Losing a child during split

An internal split must redistribute both keys and child pointers.

Copy vs promote confusion

B+ leaf split copies a separator; a B-Tree split moves the median.

Descending into a minimum child

Top-down deletion repairs the child before descent.

Forgetting root contraction

An empty internal root must be replaced by its only child.

Searching B+ internal keys as records

Internal separators route the search; records are confirmed in leaves.

CHECK YOUR UNDERSTANDING

✍️ 12. Practice Problems

Solve each problem first. Use Hint only when required, then open Show Answer to verify your reasoning.

1. If a multiway node contains k keys, how many children can it have?

2. What is the maximum number of keys in an order-m B-Tree node?

3. Why are B-Trees shallow?

4. In a B-Tree with t = 2, how many keys can a node hold?

5. Which key is promoted when a full node splits?

6. What happens when a full root splits?

7. Where are records stored in a B+ Tree?

8. Why are B+ leaves linked?

9. What is B+ range-search complexity when k keys are reported?

10. What is the difference between a B-Tree split and B+ leaf split?

11. What node types exist in a 2–3 Tree?

12. How is 2–3 Tree overflow repaired?

13. A 2–3–4 Tree is which B-Tree special case?

14. What deletion repair borrows through the parent?

15. When is merging required during deletion?

16. What is root contraction?

17. Does an internal separator prove a record exists in a B+ Tree?

18. What order does multiway in-order traversal produce?

19. Why are large node orders useful on disk?

20. Which structure is usually preferred for database indexes?

QUICK RECALL

📝 13. Quick Revision

A multiway node with k keys separates k + 1 child ranges.
All B-Tree-family leaves stay at the same depth.
Insertion repairs overflow by splitting and promoting a separator.
Deletion uses predecessor/successor replacement, borrowing, merging and root contraction.
B-Trees may store records in internal and leaf nodes.
B+ Trees store records in linked leaves and support O(log n + k) range search.
A 2–3 Tree contains only 2-nodes and 3-nodes.
A 2–3–4 Tree is a B-Tree with minimum degree t = 2.
High fan-out minimizes height and external-memory I/O.

🌳 Multiway Search Trees

🎯 Learning Objectives

🧭 1. Why Multiway Search Trees?

Binary Search Tree

Multiway Search Tree

Read Node

Find Interval

Match or Descend

Stay Balanced

🧰 2. Operations & Algorithms

Top-Down B-Tree Insertion

Top-Down Deletion

🌲 3. B-Tree

Search Algorithm

Sample Input

Sample Output

🍃 4. B+ Tree

Internal Nodes

Leaf Nodes

Range Search Algorithm

Sample Input

Sample Output

🌿 5. 2–3 Tree

Bottom-Up Insertion

Sample Input

Sample Output

🌴 6. 2–3–4 Tree

Top-Down Insertion

⚖️ 7. Comparison

🎬 8. Premium Multiway Tree Visualizer

🌳 Live Multiway Tree

🔍 9. Program Tracing — Multiway Trees

💻 C Program

🧠 What is happening?

📊 Live Variables

Multiway Tree State

Output

🧠 10. Which One Should You Use?

General Disk Index

Database Range Queries

Learn Multiway Balancing

Connect to Red–Black Trees

⚠️ 11. Common Mistakes

Wrong child interval

Losing a child during split

Copy vs promote confusion

Descending into a minimum child

Forgetting root contraction

Searching B+ internal keys as records

✍️ 12. Practice Problems

1. If a multiway node contains k keys, how many children can it have?

2. What is the maximum number of keys in an order-m B-Tree node?

3. Why are B-Trees shallow?

4. In a B-Tree with t = 2, how many keys can a node hold?

5. Which key is promoted when a full node splits?

6. What happens when a full root splits?

7. Where are records stored in a B+ Tree?

8. Why are B+ leaves linked?

9. What is B+ range-search complexity when k keys are reported?

10. What is the difference between a B-Tree split and B+ leaf split?

11. What node types exist in a 2–3 Tree?

12. How is 2–3 Tree overflow repaired?

13. A 2–3–4 Tree is which B-Tree special case?

14. What deletion repair borrows through the parent?

15. When is merging required during deletion?

16. What is root contraction?

17. Does an internal separator prove a record exists in a B+ Tree?

18. What order does multiway in-order traversal produce?

19. Why are large node orders useful on disk?

20. Which structure is usually preferred for database indexes?

📝 13. Quick Revision