Comparison and Construction of B-Trees and B+ Trees

Fundamentals of B-Tree Data Structures

• Definition and Node Composition:     * In a B-tree structure, both keys and data can be stored within internal nodes as well as leaf nodes.     * This architecture results in a specific utilization of storage: it is described as a system that "wastes space" relative to other optimized structures.

• Search Characteristics:     * Searching within a B-tree is identified as being more "difficult" compared to B+ trees because data is dispersed throughout both internal and leaf nodes.     * A defining feature of the B-tree is that it does not store redundant search keys; every key exists in exactly one location within the tree.

B-Tree Construction Example (Order 3)

• Objective: Create a B-tree of order $m = 3$ for the following data sequence: $20, 10, 30, 15, 12, 40, 50$. (Note: One referenced sequence also includes the value $140$, but the step-by-step procedure follows the previous list).

• Rule for Order 3: Each node can hold a maximum of $m - 1$, which equals $2$ key values.

• Step-by-Step Construction:     * Step 1: Insert $20, 10$         * The values are inserted in ascending order.         * Node state: $[10, 20]$.     * Step 2: Insert $30$         * The sequence becomes $(10, 20, 30)$.         * As only $2$ key values are permitted per node, the middle value ($20$) must move up to a new root level.         * Resulting Tree:             * Root: $[20]$             * Left Child: $[10]$             * Right Child: $[30]$     * Step 3: Insert $15$         * The value $15$ is placed in the left child following the value $10$.         * Tree State: Root $[20]$, Children $[10, 15]$ and $[30]$.     * Step 4: Insert $12$         * The sequence for the left child becomes $(10, 12, 15)$.         * The middle element ($12$) moves up to the root.         * Resulting Tree:             * Root: $[12, 20]$             * Left of 12: $[10]$             * Middle (between 12 and 20): $[15]$             * Right of 20: $[30]$     * Step 5: Insert $40$         * The value is placed in the right child node alongside $30$.         * Tree State: Root $[12, 20]$, Leaves $[10]$, $[15]$, and $[30, 40]$.     * Step 6: Insert $50$         * The sequence in the right leaf becomes $(30, 40, 50)$.         * The middle value ($40$) moves up to the root.         * This creates a root sequence of $(12, 20, 40)$. Because this exceeds the limit of $2$ keys, the middle value of this new root ($20$) must move up to become the new primary root.         * Final B-Tree Structure:             * New Root: $[20]$             * Level 1 Children: Left $[12]$, Right $[40]$             * Leaf Nodes (Level 2):                 * Under 12: $[10]$ and $[15]$                 * Under 40: $[30]$ and $[50]$

Fundamentals of B+ Tree Data Structures

• Storage Configuration:     * In a B+ tree, data must be stored exclusively in the leaf nodes.     * The internal nodes serve only as indexes (search keys) to guide the search process.

• Efficiency and Search:     * This structure does not waste space compared to a standard B-tree.     * Searching is simplified and "very easy" because all actual data is guaranteed to be found at the leaf level.     * A key distinction is that the B+ tree stores redundant search keys; a key appearing in an internal node will also appear in a leaf node.

B+ Tree Construction Example (Order 5 Pointers)

• Objective: Construct a B+ tree for the following data sequence: $30, 31, 23, 32, 22, 28, 24, 29$.

• Parameters:     * Number of pointers per node: $5$.     * Maximum key values allowed per node: $4$.

• Step-by-Step Construction:     * Step 1: Insert $30, 31, 23, 32$         * Insert keys in ascending order.         * Node state: $[23, 30, 31, 32]$.     * Step 2: Insert $22$         * The sequence becomes $(22, 23, 30, 31, 32)$.         * The middle key ($30$) moves up to the root level.         * In accordance with B+ tree rules, the middle key remains in the leaf as well.         * Resulting Tree:             * Root: $[30]$             * Left Leaf: $[22, 23]$             * Right Leaf: $[30, 31, 32]$     * Step 3: Insert $28, 24$         * The values are added to the left leaf in ascending order.         * Leaf state: $[22, 23, 24, 28]$.     * Step 4: Insert $29$         * The sequence for the left leaf becomes $(22, 23, 24, 28, 29)$.         * The middle key ($24$) moves up to join the root.         * Final B+ Tree Structure:             * Root Node: $[24, 30]$             * Leaf Nodes:                 * First Leaf: $[22, 23]$                 * Second Leaf: $[24, 28, 29]$                 * Third Leaf: $[30, 31, 32]$