B-trees - Chapter 10 Flashcards
In a blank each node has one key and up to two children.
binary tree
A blank with order K is a tree where nodes can have up to K-1 keys and up to K children.
B-tree
The blank is the maximum number of children a node can have. Ex: In a B-tree with order 4, a node can have 1, 2, or 3 keys, and up to 4 children.
order
B-trees have the following 5 properties:
All keys in a B-tree must be distinct.
All leaf nodes must be at the same level.
An internal node with N keys must have N+1 children.
Keys in a node are stored in sorted order from smallest to largest.
Each key in a B-tree internal node has one left subtree and one right subtree. All left subtree keys are < that key, and all right subtree keys are > that key.
As the order of a B-trees blank, the maximum number of keys and children per node increases. An internal node must have one more child than keys. Each child of an internal node can have a different number of keys than the parent internal node. Ex: An internal node in an order 5 B-tree could have 1 child with 1 key, 2 children with 3 keys, and 2 children with 4 keys.
increases
A is an order 4 B-tree. Therefore, a 2-3-4 tree node contains 1, 2 or 3 keys. A leaf node in a 2-3-4 tree has no children.
2-3-4 tree
The keys and children in a 2-3-4 tree node are commonly referred to by blank. So keys are called key 0, key 1, and key 2, and children are called child 0, child 1, child 2, and child 3. If a node has one key, then keys 1 and 2 and children 2 and 3 are not used.
index.
If a node contains two keys, then key 2 and child 3 are not used. A 2-3-4 tree node containing three keys is said to be blank.
full
A node with one key is called a blank. A node with two keys is called a blank. A node with three keys is called a blank
2-node.
3-node
4-node.
Given a key, a blank algorithm returns the first node found matching that key, or returns null if a matching node is not found. Searching a 2-3-4 tree is a recursive process that starts with the root node. If the search key equals any of the keys in the node, then the node is returned. Otherwise, a recursive call is made on the appropriate child node. Which child node is used depends on the value of the search key in comparison to the node’s keys. The table below shows conditions, which are checked in order, and the corresponding child node
search
key < node’s A key Child node to search
left
node has only 1 key or key < node’s B key Child node to search
middle1
node has only 2 keys or key < node’s C key Child node to search
middle2
not - key < node’s A key or node has only 1 key or key < node’s B key or node has only 2 keys or key < node’s C key Child node to search
right
Given a new key, a 2-3-4 tree blank inserts the new key in the proper location such that all 2-3-4 tree properties are preserved. New keys are always inserted into leaf nodes in a 2-3-4 tree. Insertion returns the leaf node where the key was inserted, or null if the key was already in the tree.
insert operation
An important operation during insertion is the blank, which is done on every full node encountered during insertion traversal. The split operation moves the middle key from a child node into the child’s parent node. The first and last keys in the child node are moved into two separate nodes. The split operation returns the parent node that received the middle key from the child.
split operation
Splitting an internal node allocates blank, each with a single key, and the middle key from the split node moves up into the parent node. Splitting the root node allocates blank, each with a single key, and the root of the tree becomes a new node with a single key.
2 new nodes
3 new nodes
During a split operation, any blank may need to gain a key from a split child node. This key may have children on either side.
non-full internal node
A new key is always inserted into a blank node.
non-full leaf
2-3-4 tree non-full-leaf insertion cases - New key equals an existing key in node
No insertion takes place, and the node is not altered.
2-3-4 tree non-full-leaf insertion cases - New key is < node’s first key
Existing keys in node are shifted right, and the new key becomes node’s first key.
2-3-4 tree non-full-leaf insertion cases - Node has only 1 key or new key is < node’s middle key
Node’s middle key , if present, becomes last key, and new key becomes node’s middle key.
2-3-4 tree non-full-leaf insertion cases - Not (Node has only 1 key or new key is < node’s middle key or New key is < node’s first key or New key equals an existing key in node)
New key becomes node’s last key.
Multiple insertion schemes exist for 2-3-4 trees. The blank scheme always splits any full node encountered during insertion traversal. The preemptive split insertion scheme ensures that any time a full node is split, the parent node has room to accommodate the middle value from the child.
preemptive split insertion
Removing an item from a 2-3-4 tree may require rearranging keys to maintain tree properties. A blank is a rearrangement of keys between 3 nodes that maintains all 2-3-4 tree properties in the process. The 2-3-4 tree removal algorithm uses rotations to transfer keys between sibling nodes
rotation
A blank on a node causes the node to lose one key and the node’s right sibling to gain one key.
right rotation
A blank on a node causes the node to lose one key and the node’s left sibling to gain one key.
left rotation
Blank returns a pointer to the left sibling of a node or null if the node has no left sibling. BTreeGetLeftSibling returns null, left, middle1, or middle2 if the node is the left, middle1, middle2, or the right child of the parent, respectively. Since the parent node is required, a precondition of this function is that the node is not the root.
BTreeGetLeftSibling
Blank returns a pointer to the right sibling of a node or null if the node has no right sibling.
BTreeGetRightSibling
Blank takes a parent node and a child of the parent node as arguments, and returns the key in the parent that is immediately left of the child.
BTreeGetParentKeyLeftOfChild
Blank takes a parent node, a child of the parent node, and a key as arguments, and sets the key in the parent that is immediately left of the child.
BTreeSetParentKeyLeftOfChild
Blank operates on a non-full node, adding one new key and one new child to the node. The new key must be greater than all keys in the node, and all keys in the new child subtree must be greater than the new key. Ex: If the node has 1 key, the newly added key becomes key B in the node, and the child becomes the middle2 child. If the node has 2 keys, the newly added key becomes key C in the node, and the child becomes the right child.
BTreeAddKeyAndChild
Blank removes a key from a node using a key index in the range [0,2]. This process may require moving keys and children to fill the location left by removing the key.
BTreeRemoveKey
The blank operates on a node, causing a net decrease of 1 key in that node. The key removed from the node moves up into the parent node, displacing a key in the parent that is moved to a sibling. No new nodes are allocated, nor existing nodes deallocated during rotation. The code simply copies key and child pointers.
rotation algorithm
When rearranging values in a 2-3-4 tree during deletions, rotations are not an option for nodes that do not have a sibling with 2 or more keys. Blank provides an additional option for increasing the number of keys in a node. A fusion is a combination of 3 keys: 2 from adjacent sibling nodes that have 1 key each, and a third from the parent of the siblings.
Fusion
Fusion is the inverse operation of a blank. The key taken from the parent node must be the key that is between the 2 adjacent siblings. The parent node must have at least 2 keys, with the exception of the root.
split
Fusion of the blank is a special case that happens only when the root and the root’s 2 children each have 1 key. In this case, the 3 keys from the 3 nodes are combined into a single node that becomes the new root node.
root node
For the non-root case, fusion operates on blank that each have 1 key. The key in the parent node that is between the 2 adjacent siblings is combined with the 2 keys from the two siblings to make a single, fused node. The parent node must have at least 2 keys.
2 adjacent siblings
In the fusion algorithm below, the blank function returns an integer in the range [0,2] that indicates the index of the key within the node. The blank functions sets the left, middle1, middle2, or right child pointer based on an index value of 0, 1, 2, or 3, respectively.
BTreeGetKeyIndex
BTreeSetChild
A B-Tree blank operates on a node with 1 key and increases the node’s keys to 2 or 3 using either a rotation or fusion. A node’s 2 adjacent siblings are checked first during a merge, and if either has 2 or more keys, a key is transferred via a rotation. Such a rotation increases the number of keys in the merged node from 1 to 2. If all adjacent siblings of the node being merged have 1 key, then fusion is used to increase the number of keys in the node from 1 to 3. The merge operation can be performed on any node that has 1 key and a non-null parent node with at least 2 keys.
merge
Blank returns the minimum key in a subtree.
BTreeGetMinKey
Blank returns a pointer to a node’s left, middle1, middle2, or right child, if the childIndex argument is 0, 1, 2, or 3, respectively.
BTreeGetChild
blank returns the child of a node that would be visited next in the traversal to search for the specified key.
BTreeNextNode
Blank swaps one key with another in a subtree. The replacement key must be known to be a key that can be used as a replacement without violating any of the 2-3-4 tree rules.
BTreeKeySwap
Given a key, a 2-3-4 tree blank removes the first-found matching key, restructuring the tree to preserve all 2-3-4 tree rules. Each successful removal results in a key being removed from a leaf node. Two cases are possible when removing a key, the first being that the key resides in a leaf node, and the second being that the key resides in an internal node.
remove operation
A key can only be removed from a leaf node that has 2 or more keys. The blank removal scheme involves increasing the number of keys in all single-key, non-root nodes encountered during traversal. The merging always happens before any key removal is attempted. Preemptive merging ensures that any leaf node encountered during removal will have 2 or more keys, allowing a key to be removed from the leaf node without violating the 2-3-4 tree rules.
preemptive merge
To remove a key from an blank, the key to be removed is replaced with the minimum key in the right child subtree (known as the key’s successor), or the maximum key in the leftmost child subtree. First, the key chosen for replacement is stored in a temporary variable, then the chosen key is removed recursively, and lastly the temporary key replaces the key to be removed.
internal node
