17.1. 2-3+ Trees¶
17.1.1. 2-3+ Trees¶
17.1.1.1. 2-3 Tree¶
- A 2-3 Tree has the following properties:
A node contains one or two keys
Every internal node has either two children (if it contains one key) or three children (if it contains two keys).
All leaves are at the same level in the tree, so the tree is always height balanced.
The 2-3 Tree has a search tree property analogous to the BST.
17.1.1.2. 2-3+ Tree¶
- Internal nodes of the 2-3+ Tree do not store records
They only store key values to guide the search.
Leaf nodes store records or pointers to records.
A leaf node may store more or less records than an internal node stores keys.
See this link for examples of operations.
See this link for an interactive visualization.
17.1.1.3. 2-3+ Tree Insert Rules¶
- If you have room in the node, add in the record.
You might need to update parent keys, but not parent structure
- If the node overflows, then split 1/2.
Promote the right node’s first key value to the parent.
This can cause a cascade of splits.
17.1.1.4. 2-3+ Tree Deletion Rules (1)¶
- If the node has enough records, simply remove this one.
Don’t bother to adjust key values of parents
- If the node underflows, attempt to borrow from a sibling.
Do not borrow from cousins.
Borrowing will require update of keys in parents, but not parent structure.
17.1.1.5. 2-3+ Tree Deletion Rules (2)¶
If borrowing is impossible, then that means something has to change structurally.
If this is a leaf node, then it goes away (no records left). Which means a deletion from the parent.
If this is an internal node that lost a child, then it is down to one child that must be merged with a sibling.
At a minimum, this means adjustment to other key values up the tree.
It could cause a cascade of merges up the tree. In the limit, the root might go away, making the tree become one level shorter.
17.1.1.6. Special Considerations for Project 2¶
The difference between Key and Value are slightly blurred.
The tree stores KVPairs, each record is a “track”.
We represent each track with TWO records: artist|song and song|artist
An artist with multiple songs appears as multiple KVPairs with the same “key” (artist), but different “values” (songs).
When searching, use the “value” to break ties in the “key”
