Here is an example for insertion into a 2-3+ tree. This example is driven by the data that would generate Figure 10.9 in the textbook. That 2-3 tree will be generated if the data are inserted in the order: 10 24 23 45 21 18 12 20 15 33 31 50 48 52 47 30.
I will now show what happens when we insert the records in the same order into a 2-3+ tree. It is important to understand that there is a difference between what is stored in the leaf nodes and what is stored in the internal nodes. Leaf nodes will store two pointers to records. Of course, what I show in the picture is a key value. But that key value really stands for the entire record. In contrast, internal nodes store 3 pointers (to base-class nodes) and two key values. So if you see "18" at a leaf node, that represents a pointer to a record with key value 18. If you see "18" in an internal node, that just means the value 18 is stored as a direction finder.
First we insert 10 and 24 into a single leaf node. The tree is initally:
/-----\ |10|24| \-----/
Inserting 23 causes this node to split. Now, in a 2-3 tree, we'd generate two leaf nodes that each store one record, and promote the middle record (23) to a new internal node. However, in the 2-3+ tree, while we still split the leaf, we also still keep all 3 records at the leaf nodes. So we have to decide how that split takes place. I will define splits to go 1/2. That means where there used to be one leaf node, there will now be two. The left leaf node contains one record and the right contains two. We also still promote something, the value of the lefmost of the two records in the right leaf. Since there is no parent for the leaf node being split, we generate a new root. The result is:
/-----\
|23| |
\-----/
/ \
/ \
/ \
/-----\ /-----\
|10| | |23|24|
\-----/ \-----/
Adding 45 causes the right leaf to split again. There is room in its parent for the new key that is promoted.
/-----\
|23|24|
\-----/
/ | \
---- | ----
/ | \
/-----\ /-----\ /-----\
|10| | |23| | |24|45|
\-----/ \-----/ \-----/
Now we add 21 (it just adds into the leaf holding 10).
/-----\
|23|24|
\-----/
/ | \
---- | ----
/ | \
/-----\ /-----\ /-----\
|10|21| |23| | |24|45|
\-----/ \-----/ \-----/
Adding 18 causes the leftmost leaf to split. The result is to promote key 18 (the middle value of 10, 18, 21). This causes the root to split in turn, which generates a new root. Note that splitting an internal node is a bit different from splitting a leaf node. When an internal node is split, now have two internal nodes where there was previously one. The left internal node holds the lowest of the three key values, the right internal node holds the greatest of the three key values, and the middle value gets promoted. The result is:
/-----\
|23| |
\-----/
/ \
---- ----
/ \
/-----\ /-----\
|18| | |24| |
\-----/ \-----/
/ \ / \
/ \ / \
| | | |
/-----\ /-----\ /-----\ /-----\
|10| | |18|21| |23| | |24|45|
\-----/ \-----/ \-----/ \-----/
Now we add 12 into the leftmost leaf. Then adding 20 (into the second leaf) causes a split. The key value 20 is promoted to its parent, which has room.
/-----\
|23| |
\-----/
/ \
----- ------
/ \
/-----\ /-----\
|18|20| |24| |
\-----/ \-----/
/ | \ / \
---- | ---- / \
/ | \ | |
/-----\ /-----\ /-----\ /-----\ /-----\
|10|12| |18| | |20|21| |23| | |24|45|
\-----/ \-----/ \-----/ \-----/ \-----/
Adding 15 causes the leftmost leaf node to split. This causes its parent to split, ultimately causing 18 to be promoted to the root.
/-----\
|18|23|
\-----/
/ | \
------------ | ------------
/ | \
/-----\ /-----\ /-----\
|12| | |20| | |24| |
\-----/ \-----/ \-----/
/ \ / \ / \
/ \ / \ / \
| | | | | |
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24|45|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/
Adding 33 causes the rightmost node to split, and the promoted value adds to its parent.
/-----\
|18|23|
\-----/
/ | \
------------ | ----------------
/ | \
/-----\ /-----\ /-----\
|12| | |20| | |24|33|
\-----/ \-----/ \-----/
/ \ / \ / | \
/ \ / \ ---- | ---
| | | | / | \
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24| | |33|45|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/
31 adds to the leaf node containing 24.
/-----\
|18|23|
\-----/
/ | \
------------ | ----------------
/ | \
/-----\ /-----\ /-----\
|12| | |20| | |24|33|
\-----/ \-----/ \-----/
/ \ / \ / | \
/ \ / \ ---- | ---
| | | | / | \
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24|31| |33|45|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/
Inserting 50 causes a split in the rightmost leaf node. This causes splits to cascade all the way up, eventually generating a new leaf node and adding a new level to the tree.
/-----\
|23| |
\-----/
/ \
----------- ------------
/ \
/-----\ /-----\
|18| | |33| |
\-----/ \-----/
/ \ / \
---- --- ---- ----
/ \ / \
/-----\ /-----\ /-----\ /-----\
|12| | |20| | |24| | |45| |
\-----/ \-----/ \-----/ \-----/
/ \ / \ / \ / \
/ \ / \ / \ / \
| | | | | | | |
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24|31| |33| | |45|50|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/
Inserting 48 causes the leftmost node to split again. Its parent absorbs the promotion.
/-----\
|23| |
\-----/
/ \
----------- --------------
/ \
/-----\ /-----\
|18| | |33| |
\-----/ \-----/
/ \ / \
---- --- ------ ------
/ \ / \
/-----\ /-----\ /-----\ /-----\
|12| | |20| | |24| | |45| |
\-----/ \-----/ \-----/ \-----/
/ \ / \ / \ / | \
/ \ / \ / \ ---- | ---
| | | | | | / | \
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24|31| |33| | |45| | |48|50|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/
Inserting 52 causes another split in the rightmost leaf node, which causes the parent to split (with the promotion being absorbed by the grandparent).
/-----\
|23| |
\-----/
/ \
--------------- -----------------
/ \
/-----\ /-----\
|18| | |33|48|
\-----/ \-----/
/ \ / | \
---- --- ------------- | ------------
/ \ / | \
/-----\ /-----\ /-----\ /-----\ /-----\
|12| | |20| | |24| | |45| | |50| |
\-----/ \-----/ \-----/ \-----/ \-----/
/ \ / \ / \ / \ / \
/ \ / \ / \ / \ / \
| | | | | | | | | |
/-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\ /-----\
|10| | |12|15| |18| | |20|21| |23| | |24|31| |33| | |45| | |48| | |50|52|
\-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/ \-----/
Finally, 47 is inserted into the leaf node containing 45, and 30 causes a split in the leaf node containing 24 and 31. The key value 30 is promoted to its parent, which can absorb it. I'll leave that final diagram for the reader.
Go to the CS2606 Homepage.